问旅行业务员的贪婪法与动态规划法

EN

精确算法和启发式有一个重要的区别。保证了一个精确的算法来找到精确的最优解。启发式不是，但它被设计为快速运行。

DP是一种精确的算法，至少与通常使用的算法一样。TSP有DP算法。因此，这些算法将准确地解决这个问题。

TSP不能用贪婪方法精确求解，因此任何贪心方法都是启发式的。因此，根据定义，对于TSP的任何实例，DP总是会找到比贪婪的启发式方法更好(或不更糟)的可行解决方案。

但是，请注意，DP并不是解决TSP的主要方法。还有许多其他的算法，效率要高得多。一些关于TSP的原始论文使用了DP，它通常是作为一个说明性的例子，但它并不是TSP在实践中通常被解决的方法。

若要更正OP中的某些内容：

我知道，在最优解方面，贪婪算法被用来求解TSP，但是当顶点数(即城市)非常大时，它变得更加复杂，并且需要指数时间。

贪婪启发式有时用于解决TSP。(它们有最近的邻居、最便宜的插入等名称)随着顶点数量的增加，这些启发式算法的运行时间也会增加，但不会以指数方式增长。这些启发式算法大多具有低次多项式复杂度的运行时间，例如O(n^2)。

另一方面，由于TSP是NP硬的，所有已知的精确算法都有最坏的情况复杂度，即顶点数的指数。(请注意，我说最坏情况的复杂性-实际运行时间在许多情况下可能是相当合理的，但在最坏情况下则是指数级的。)

贪婪方法并不总是给出旅行商问题的最优解。

例子: A(0,0)，B(0,1)，C(2,0)，D(3,1)

推销员从A开始，B是1，C是2，D是3.16。

推销员走到最近的B，然后C是2.24，D是3。

推销员去的C是最近的，然后是D，这是最后一个未去过的城市，然后返回到A。

总行程A-B-C-D-A为7.81 .行程A-B-D-C-A长7.41，短.

动态解要慢得多，但总是给出最优解。