旅行商问题|集1（朴素和动态规划）

旅行推销员问题（TSP）： 给定一组城市和每对城市之间的距离，问题是找到一条尽可能短的路线，该路线只访问每个城市一次，然后返回起点。 请注意 哈密顿循环 还有TSP。哈密顿循环的问题是，是否存在一个旅游团，每个城市只访问一次。这里我们知道哈密顿圈是存在的（因为图是完整的），事实上存在很多这样的圈，问题是找到一个最小权哈密顿圈。

例如，考虑图右边所示的曲线图。图中的TSP旅行是1-2-4-3-1。旅行的费用是10+25+30+15，也就是80。

这是一个著名的问题 NP难 问题这个问题没有多项式时间解。

以下是旅行推销员问题的不同解决方案。

天真的解决方案： 1）以城市1为出发点和落脚点。 2） 生成所有（n-1）！ 排列 城市。 3） 计算每个排列的成本，并跟踪最小成本排列。 4） 以最低成本返回排列。

时间复杂度：Θ（n！）

动态规划： 设给定的顶点集为{1,2,3,4，….n}。让我们考虑1作为输出的开始和结束点。对于每一个顶点i（除1之外），我们找到最小代价路径，以1为起点，i为终点，所有顶点只出现一次。假设该路径的成本为成本（i），相应循环的成本为成本（i）+dist（i，1），其中dist（i，1）是从i到1的距离。最后，我们返回所有[cost（i）+dist（i，1）]值中的最小值。到目前为止，这看起来很简单。现在的问题是如何获得成本（i）？ 为了使用动态规划计算成本（i），我们需要在子问题方面有一些递归关系。让我们定义一个术语 C（S，i）是最小代价路径访问集合S中每个顶点一次的代价，从1开始，到i结束 . 我们从大小为2的所有子集开始，计算所有子集的C（S，i），其中S是子集，然后计算大小为3的所有子集的C（S，i），依此类推。请注意，每个子集中必须有1。

If size of S is 2, then S must be {1, i},
 C(S, i) = dist(1, i) 
Else if size of S is greater than 2.
 C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.

对于一组大小n，我们考虑n-2子集的大小n-1，使得所有子集在它们中不具有n次。 利用上述递推关系，我们可以写出基于动态规划的解。最多有O（n*2） ^N )子问题，每个问题都需要线性时间来解决。因此，总运行时间为O（n ^2. *2 ^N ).时间复杂度远小于O（n！），但仍然是指数型的。所需的空间也是指数级的。因此，即使顶点数量稍高，这种方法也不可行。

我们将很快讨论旅行推销员问题的近似算法。

下一篇文章： 旅行推销员问题|集2

参考资料： http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog。pdf http://www.cs.berkeley.edu/~vazirani/算法/第6章。pdf

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论