Chemin non cyclique vers tous les nœuds

Question

Existe-t-il un algorithme ou un ensemble d'algorithmes qui vous permet de trouver la distance de marche la plus courte d'un nœud de départ arbitraire afin que chaque nœud soit visité dans un graphe non orienté? Ce n'est pas tout à fait un vendeur ambulant, car je me fiche qu'un nœud soit visité plus d'une fois. (Cela n'a même pas d'importance si vous revenez au début - le marcheur peut se retrouver dans un nœud lointain tant qu'il est le dernier à visiter tous les nœuds.) Ce n'est pas tout à fait le spanning tree minimum, car il se peut que aller A -> B -> C -> A -> D est un chemin (non unique) le plus court pour visiter A, B, C et D. Mon intuition dit que ce n'est pas le cas. C'est plutôt un problème NP, car il n'a pas les restrictions qui rendent les problèmes NP si difficiles. Je pourrais, bien sûr, avoir complètement tort.

Answer 1

de l'article de Wikipédia sur Travelling Salesman Problem:

Retrait de la condition de visiter chaque ville « une seule fois » ne supprime pas le NP-dureté, car il est facile de voir que dans le cas planaire il y a une visite optimale qui ne visite chaque ville qu'une seule fois (sinon, par l'inégalité du triangle, un raccourci qui saute une visite répétée n'augmenterait pas la durée du tour).

Answer 2

Vous ne savez pas exactement ce que l'étiquette est pour ajouter une réponse à une question avec une réponse déjà acceptée.

J'ajoute cette réponse juste pour ne pas avoir à sauter à une autre page, pour ne pas avoir à faire face aux graphes planaires et à l'inégalité triangulaire et le fait que c'est simple et probablement plus facile à comprendre.

problème hamiltonien Path peut être réduit à ceci:

Supposons que nous ayons un algorithme polynomial pour résoudre notre problème de trouver un moins à pied de poids qui rend visite à tous les sommets. Étant donné un graphique dont nous devons décider si un chemin hamiltonien existe ou non, nous l'alimentons tel quel, à l'algorithme du problème, en définissant des poids de bord = 1. Si l'algorithme renvoie une valeur> n- 1, alors il n'y a pas de chemin hamiltonien dans le graphe original, sinon il y en a.

Ce problème est donc NP-difficile.