informatique (MP2I/MPI) · Chapitre 25 · Exercice de TD
Décision, optimisation, instance
Algorithmes probabilistes, approximation, séparation et évaluation · niveau 2
Énoncé
Pour chacun des trois problèmes suivants, énoncer la version décision et la version optimisation, dire quelle est la fonction de coût, et donner une instance.
- La couverture des sommets d'un graphe.
- Le sac à dos.
- Le couplage dans un graphe biparti.
Corrigé
| Problème | Décision | Optimisation |
|---|---|---|
| Couverture | « Existe-t-il une couverture de taille ? » | « Quelle est la plus petite couverture ? » |
| [2pt] Sac à dos | « Peut-on atteindre une valeur sans dépasser la capacité ? » | « Quelle est la valeur maximale ? » |
| [2pt] Couplage | « Existe-t-il un couplage de cardinal ? » | « Quel est le cardinal maximum ? » |
Les fonctions de coût : le nombre de sommets pris (à minimiser) ; la valeur totale des objets (à maximiser) ; le cardinal du couplage (à maximiser).
Les instances — une instance est une donnée, pas un problème : le triangle avec ; les objets de poids et de valeurs avec ; le graphe biparti avec .
Pourquoi la distinction compte. Les deux versions ont exactement la même difficulté à un facteur logarithmique près : si l'on sait décider, on trouve l'optimum par dichotomie sur , en appels. La théorie de la complexité — chapitre chap:decidabilite — se formule sur les problèmes de décision, parce qu'une réponse par oui ou non se compare plus commodément ; mais c'est l'optimisation qui intéresse le praticien.
Et c'est la version optimisation qui donne un sens à l'approximation : « rendre une couverture au plus deux fois trop grande » a un sens, « répondre oui deux fois trop » n'en a aucun. Une approximation n'existe que pour un problème d'optimisation.
