如果使用动态编程方法解决旅行商问题，它是否会提供比贪婪方法更好的可行解决方案？
我知道，就最优解而言，贪婪算法用于求解TSP，但是当顶点数（即城市）非常大时，它变得更复杂并且需要指数时间。
那么，到底哪种方法会更好？
贪婪的方法并不总能为旅行商问题提供最佳解决方案。
示例：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，较短。
动态解决方案要慢得多，但始终能提供最佳解决方案。
精确算法和启发式算法之间存在重要区别。确保精确算法找到确切的最优解。启发式不是，但它旨在快速运行。
DP是一种精确算法，至少通常使用它。 TSP有DP算法。因此，这些算法将准确地解决问题。
使用贪婪方法无法精确解决TSP，因此任何贪婪方法都是启发式方法。因此，根据定义，对于TSP的任何实例，DP总是会找到比贪婪启发式更好（或者更糟）的可行解决方案。
但请注意，DP不是解决TSP的主要方法。存在许多其他更有效的算法。关于TSP的一些原始论文使用了DP，它通常被表述为一个说明性的例子，但它并不是TSP通常在实践中解决的方式。
要纠正OP中的某些内容：
我知道，就最优解而言，贪婪算法用于求解TSP，但是当顶点数（即城市）非常大时，它变得更复杂并且需要指数时间。
贪婪启发式有时用于解决TSP问题。 （它们具有最近邻，最便宜的插入等名称）随着顶点数量的增加，这些启发式的运行时间也会增长，但它不会呈指数增长。这些启发式算法中的大多数具有低阶多项式复杂度的运行时间，例如O（n ^ 2）。
另一方面，由于TSP是NP难的，所有已知的精确算法都将具有最坏情况的复杂度，其在顶点数量上呈指数关系。 （请注意，我说最坏情况的复杂性 - 实际运行时间对于许多实例来说可能是非常合理的，但在最坏的情况下只是指数级。）