Supposons que vous disposiez d'un oracle capable de déterminer (en temps polynomial) s'il existe un chemin Hamilton dans un graphique donné. (Rappel: le problème du chemin Hamilton est dans le PNJ).Recherche d'un chemin Hamilton dans un temps polynomial à l'aide de la machine oracle
Décrire comment utiliser l'oracle afin de trouver un chemin de Hamilton dans un graphique, dans un temps polynomial.
Des idées?
Un chemin hamiltonien visite chaque sommet exactement une fois.
Si vous avez un oracle, vous pouvez tester le retrait de chaque bord à tour de rôle. Si l'oracle dit qu'il y a toujours un chemin, gardez le bord supprimé, sinon restaurez le bord et essayez le suivant.
Une fois que vous avez traversé tous les bords, tout ce qui restera sera le chemin hamiltonien.
Je ne suis pas sûr de comprendre. Quand vous dites que nous pouvons enlever chaque bord à son tour - comment puis-je savoir que je peux nécessairement enlever un bord du graphique que j'ai en main? Je veux dire, dans certains graphiques, il pourrait y avoir une chance que même si j'essaie de supprimer un bord, il n'y aura toujours pas de chemin Hamiltonien. Alors, pourquoi supprimons-nous les bords? – SKriheli
L'idée est que nous commençons avec un graphique avec beaucoup d'arêtes. L'oracle nous dit qu'il y a un chemin hamiltonien - mais pas où il est. Nous essayons de simplifier le graphique autant que possible en supprimant les bords tout en préservant le chemin. Une fois que nous aurons fini de supprimer les arêtes, nous aurons un graphe de chaîne très simple qui doit être égal au chemin hamiltonien. Vous avez raison de dire que le fait de supprimer un bord enlève parfois le chemin, mais dans ce cas, nous replaçons le bord et essayons un bord différent. –
Donc l'oracle obtient réellement un graphique avec beaucoup d'arêtes alors que nous savons avec certitude que ce graphique contient un chemin hamiltonien, mais nous ne savons pas où. Enlever les bords, comme vous l'avez décrit, ne quitte finalement le graphe qu'avec les arêtes qui font partie du chemin hamiltonien. Droite? – SKriheli
S'il y a n-1 arêtes dans le graphique, nous avons terminé (il doit s'agir d'une chaîne, sinon, il n'y a pas de chemin hamiltonien).
Sinon, nous pouvons supprimer certains bords. Let itérer sur tous les bords. S'il y a toujours un chemin dans un graphique sans bord fixe, nous pouvons l'enlever et continuer.
Cette solution nécessite des requêtes oracle O (m^2), donc cela fonctionne en temps polynomial.
Cela peut être mieux adapté à l'échange de pile informatique - il ne s'agit pas de * programmation *. –