使用樹的多項式時間旅行推銷員[動態規劃]

Question

如果我們有N個城市，每個城市只有一棵二叉樹的葉子，有可能想出一個多項式時間的動態規劃解決方案嗎？我試圖找到所有城市之間的最小距離，只能先行深度。我的方法是自下而上並計算最深的內部節點的每個祖先的最佳行進路徑。因此，在這些運營中，將有4個城市將通過某種距離函數進行評估。距離（x，y）=距離（y，x）。如果每個操作有4個城市，那麼我們將有8個可能的解決方案。所有其他內部節點將導致較低節點的總和。根將基本上是其子女的總和。我在這裏面朝錯誤的方向走了嗎？

Answer 1

我假設你正試圖解決圖形碰巧是樹的TSP。這個問題的學術版似乎是在「有界樹寬」圖上解決TSP，這可能是一個很好的搜索術語。 http://www.cs.princeton.edu/~zdvir/apx11slides/erik-scribe.pdf包含參考文獻，「Frederic Dorn，Fedor V.Fomin和Dimitrios M.Thilikos.Tarmallan structures and dynamic programming in H-minor-free graphs.SODA'08：Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms，第631頁（640頁，SIAM，2008），這篇論文我懷疑是數學家比程序員更感興趣。

假設您獲得最佳旅遊。查看內部節點的兩個孩子，並計算此次遊覽穿過內部節點的次數。如果它跨越兩次以上，您可以通過快捷方式縮短巡視路線 - 打破其中兩個過境點，並將它們變爲每個子樹內的鏈接，而不是從子樹切換到子樹。因此，在最佳旅程中，在每個內部節點交叉的地方，我們有一條路徑訪問一個子樹中的所有城市，訪問另一個子樹，訪問該子樹中所有城市的路徑，然後返回連接參觀。

因此，一個可能效率低下但是多項式動態規劃方法是在每個內部節點處爲該內部節點內的每對城市計算從城市A到城市B的最佳旅程的費用，訪問所有其他城市在那個節點下面的城市（或者標記「城市在同一邊 - 不要這樣做」）。您可以使用從其孩子計算的信息爲每個室內節點制定這個計劃，並且在最上方考慮所有提供的最佳路徑和剩餘鏈接的成本，這使得旅程能夠實現最短的旅程。