问旅行推销员-为什么贪婪的算法不能保证给出最优解决方案？

EN

简而言之，旅行商问题不满足证明贪婪算法正确性所需的性质。为了使贪婪算法正确，它必须同时满足贪婪选择属性(算法中的第一个选择可以始终是最优解)和最优子结构属性(问题的最优解包含每个子问题的最优解)。

虽然旅行推销员确实满足最优子结构性质，但该问题的任何算法都不能满足贪婪选择性质。贪婪算法需要丢弃每个子问题的其他潜在解决方案，而Traveling Salesman太复杂了。

旅行推销员的一般算法是选择一个起点，生成所有(n-1)！访问城市的排列，计算每个城市的费用，然后返回最便宜的排列。该算法的运行时间为Θ(n!)。

旅行商问题的决策版本是一个NP完全问题(在此版本中，给定长度X，给定的城市列表是否具有小于或等于X的距离)。NP是“非确定性多项式”的缩写，NP中的问题意味着，给定问题的答案，您可以在多项式时间内验证证书是否正确。NP -完全问题是NP中最困难的一类问题，任何NP-完全问题都不能在多项式时间内求解。