Discuter:Stable maximum
Un article de Wikipédia, l'encyclopédie libre.
Il faut revoir entièrement la partie suivante avant de l'incorporer...
La recherche d'un ensemble stable de poids maximum (ESPM, pour faire court) dans un graphe permet la résolution des problèmes de maximisation de fonction pseudo-booléennes et de partitionnement.
- Problème de partitionnement.
- Exemple :
- Chercher le minimum de 2x1 + 3x2 + 7x3 + 4x4 + 8x5 avec les contraintes :
- x4 + x5 = 1
- x2 + x3 + x4 = 1
- x3 + x4 = 1
- x1 + x2 + x4 = 1
- Le graphe généré est le suivant :
- Chercher le minimum de 2x1 + 3x2 + 7x3 + 4x4 + 8x5 avec les contraintes :
-
- L'ESPM trouvé est (1, 3, 5).
- La solution est
- x1 = 1
- x2 = 0
- x3 = 1
- x4 = 0
- x5 = 0
