Polynomische Zeit Reisende Verkäufer mit einem Baum [Dynamische Programmierung]

Question

Wenn wir N Städte haben, wo jede Stadt nur ein Blatt eines binären Baumes ist, ist es möglich, mit einer dynamischen Programmierlösung zu kommen, die Polynomzeit ist? Ich versuche, den minimalen Abstand zwischen allen Städten zu finden, mit dem Zwang, nur in der Tiefe reisen zu können. Mein Ansatz besteht darin, von unten nach oben zu gehen und den optimalen Weg für jeden Vorfahren der tiefsten inneren Knoten zu berechnen. Es wird also 4 Städte geben, die während jeder dieser Operationen durch eine Entfernungsfunktion bewertet werden. Abstand (x, y) = Abstand (y, x). Wenn es bei jeder Operation 4 Städte gibt, haben wir 8 mögliche Lösungen. Alle anderen internen Knoten führen zur Summierung der unteren Knoten. Die Wurzel wird im Grunde die Summe ihrer Kinder sein. Gehe ich hier in die falsche Richtung oder was?

Answer 1

Ich gehe davon aus, dass Sie versuchen, das TSP auf einem Diagramm zu lösen, das zufällig ein Baum ist. Die akademische Version dieses Problems scheint zu sein, die TSP auf Graphen der "begrenzten Baumbreite" zu lösen, die wahrscheinlich ein guter Suchbegriff ist. http://www.cs.princeton.edu/~zdvir/apx11slides/erik-scribe.pdf enthält eine Referenz, "Frederic Dorn, Fedor V. Fomin und Dimitrios M. Thilikos. Katalanische Strukturen und dynamische Programmierung in H-Moll-freien Grafiken. In SODA '08: Proceedings des 19. jährlichen ACM-SIAM Symposium auf Discrete Algorithms, S. 631 {640. SIAM, 2008. ", zu einem Papier, von dem ich vermute, dass es eher für Mathematiker als für Programmierer von Interesse ist.

Angenommen, Sie erhalten eine optimale Tour. Betrachten Sie zwei Kinder eines inneren Knotens und zählen Sie, wie oft diese Tour den inneren Knoten kreuzt. Wenn es mehr als zweimal überquert wird, können Sie die Tour verkürzen, indem Sie eine Abkürzung nehmen - zwei dieser Kreuzungen brechen und sie in Links innerhalb jedes Teilbaums verwandeln, anstatt von Teilbaum zu Teilbaum zu gehen. In einer optimalen Tour, an jedem gekreuzten inneren Knoten, haben wir einen Pfad, der alle Städte in einem Teilbaum besucht, einen Ausflug zum anderen Teilbaum, einen Pfad, der alle Städte in diesem Teilbaum besucht, und dann einen Rückweg zur Verbindung die Tour hinauf. Ein möglicherweise ineffizienter, aber polynomialer dynamischer Programmieransatz besteht daher darin, an jedem inneren Knoten für jedes Städtepaar innerhalb dieses inneren Knotens die Kosten für die beste Fahrt von Stadt A nach Stadt B zu berechnen und alle anderen zu besuchen Städte unter diesem Knoten (oder eine Markierung, die besagt "Städte auf derselben Seite - tun Sie das nicht"). Sie können dies für jeden inneren Knoten mit den von seinen Kindern berechneten Informationen durchführen, und ganz oben die besten verfügbaren Wege und die Kosten des verbleibenden Links, der eine Tour zur Ausarbeitung der kürzesten Tour macht, in Betracht ziehen.