旅行商问题| 动态规划

使用贪婪方法的旅行推销员已在上面的同一教程中讨论过。要了解更多信息，请点击此处。

旅行商问题是最臭名昭著的计算问题。我们可以使用蛮力方法来评估每一个可能的旅行并选择最好的一个。对于图中的 n 个顶点，有(n−1) 个！可能性的数量。因此，保持了较高的复杂度。

然而，尽管没有多项式时间算法，但使用动态规划方法可以在更短的时间内获得解决方案，而不是使用暴力。

旅行商动态规划算法

让我们考虑一个图G = (V,E)，其中V是一组城市，E 是一组加权边。边e(u,v)表示顶点u和v相连。顶点u和v之间的距离是d(u, v)，它应该是非负的。

假设我们从城市1开始，在访问了一些城市之后，现在我们在城市j。因此，这是一次部分游览。我们当然需要知道j，因为这将决定接下来访问哪些城市最方便。我们还需要知道到目前为止访问过的所有城市，这样我们就不会重复其中任何一个。因此，这是一个适当的子问题。

对于包含1和j $\epsilon$ S 的城市子集S $\epsilon$ {1,2,3,...,n} ，令 C(S, j)为访问的最短路径的长度S 中的每个节点恰好一次，从 1 开始，到j结束。

当|S|> 1时，我们定义