使用树的多项式时间旅行推销员[动态规划]

Question

如果我们有N个城市，其中每个城市只是二叉树的一个叶子，那么有可能得到一个多项式时间的动态规划解决方案吗？我正在尝试寻找所有城市之间的最小距离，但限制条件是只能先旅行深度。我的方法是从下往上开始，计算最深内部节点的每个祖先的最优路径。因此，将有4个城市将在每个操作期间通过一些距离函数进行评估。Distance(x，y) = Distance (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。H-minor-free图中的加泰罗尼亚结构和动态编程。在SODA '08:第19届年度ACM-SIAM离散算法研讨会论文集，第631页{640。SIAM，2008。“，我怀疑数学家比程序员更感兴趣的论文。

假设你得到了一个最优的旅行。查看内部节点的两个子节点，并计算此遍历穿过内部节点的次数。如果它跨越两次以上，您可以通过缩短行程-中断其中的两个交叉，并将它们转换为每个子树中的链接，而不是从一个子树到另一个子树。因此，在最优路径中，在每个相交的内部节点，我们有一条路径访问一个子树中的所有城市，一次到另一棵子树的旅行，一条访问该子树中所有城市的路径，然后一次返回以连接旅行。

因此，一种可能低效但多项式的动态规划方法是，在每个内部节点上，为该内部节点内的每一对城市计算从城市A到城市B的最佳旅行的成本，访问该节点下的所有其他城市(或者标记为“同一边的城市-不要这样做”)。您可以使用从子节点计算出的信息为每个内部节点计算出这一点，并且在最上面只考虑提供的所有最佳路径以及构成巡视的剩余链路的成本，以计算出最短的巡视。