Temps polynomial Voyageur utilisant un arbre [Programmation dynamique]

Question

Si nous avons N villes, où chaque ville n'est qu'une feuille d'un arbre binaire, est-il possible de trouver une solution de programmation dynamique qui est le temps polynomial? J'essaie de trouver la distance minimale entre toutes les villes avec la contrainte de ne pouvoir voyager que la profondeur en premier. Mon approche est de commencer par le bas et calculer le chemin optimal pour voyager pour chaque ancêtre des nœuds internes les plus profonds. Il y aura donc 4 villes qui seront évaluées au cours de chacune de ces opérations par une fonction de distance. Distance (x, y) = Distance (y, x). S'il y a 4 villes à chaque opération, nous aurons 8 solutions possibles. Tous les autres nœuds internes entraîneront la sommation des nœuds inférieurs. La racine sera essentiellement la somme de ses enfants. Suis-je dirigé dans la mauvaise direction ici ou quoi?

Answer 1

Je suppose que vous essayez de résoudre le TSP sur un graphique qui se trouve être un arbre. La version académique de ce problème semble être de résoudre le TSP sur les graphiques de "bounded treewidth" qui est probablement un bon terme de recherche. http://www.cs.princeton.edu/~zdvir/apx11slides/erik-scribe.pdf contient une référence, "Frederic Dorn, Fedor V. Fomin, et Dimitrios M. Thilikos." Structures catalanes et programmation dynamique dans des graphes sans mineur H. Dans SODA '08: Actes du 19ème Symposium annuel ACM-SIAM sur le thème Discrete Algorithms, pages 631 {640. SIAM, 2008. ", sur un article qui, selon moi, intéresse plus les mathématiciens que les programmeurs.

Supposons que vous ayez une visite optimale. Regardez deux enfants d'un nœud intérieur et comptez le nombre de fois que ce tour a traversé le nœud intérieur. Si vous le traversez plus de deux fois, vous pouvez raccourcir la visite en prenant un raccourci pour couper deux de ces croisements et les transformer en liens dans chaque sous-arbre au lieu d'aller de sous-arbre à sous-arbre. Donc, dans un tour optimal, à chaque nœud intérieur croisé, nous avons un chemin qui visite toutes les villes dans un sous-arbre, un voyage dans l'autre sous-arbre, un chemin qui visite toutes les villes de ce sous-arbre, puis un retour jusqu'à la tournée. Une approche de programmation dynamique potentiellement inefficace mais polynomiale consiste donc à calculer, à chaque noeud intérieur, pour chaque paire de villes dans ce noeud intérieur, le coût du meilleur trajet de la ville A à la ville B, en visitant tous les autres villes sous ce nœud (ou un marqueur qui dit «villes du même côté - ne le faites pas»). Vous pouvez le faire pour chaque nœud intérieur en utilisant les informations calculées par ses enfants, et tout en haut, il suffit de considérer tous les meilleurs chemins proposés et le coût du lien restant qui fait un tour pour élaborer le tour le plus court.