关于非度量对称TSP与非对称TSP的最优多项式时间近似算法咨询

嘿，这个问题问得挺到位的——毕竟TSP的非度量版本可比度量型的棘手太多了！咱们分两种情况给你捋清楚：

• 非度量对称TSP：
  首先得给你泼个小冷水：除非P=NP，否则不存在具有常数近似比的多项式时间算法。为啥这么说？咱们可以用归约的思路来理解：把问题和经典的NP完全问题「哈密顿回路」挂钩——假设你有一个无向图，把图中存在的边权重设为1，不存在的边权重设一个极大的数（比如1000倍的节点数n）。如果真有一个常数因子α的近似算法，那当原图存在哈密顿回路时，算法给出的解总权重最多是α*n；如果不存在的话，解的权重至少是1000n，只要α<1000，就能直接区分这两种情况——这就意味着P=NP了，而目前学术界普遍认为P≠NP。
  当然，要是你研究的是某些特殊子类的非度量对称TSP，可能会有针对性的近似算法，但对于一般情况，确实没有常数因子的多项式近似方案。

• 非对称TSP（ATSP）：
  同样，一般情况下也不存在常数近似比的多项式时间算法，除非P=NP（归约逻辑类似，只是针对有向图的哈密顿回路问题）。不过这里有个值得一提的进展：目前已知的最优多项式时间近似算法能达到O(log n)的近似比。最早是Frieze、Galbiati和Maffioli在1982年提出的随机算法，后来也有了确定性的版本。这个算法的核心思路是先构造有向图的最小生成树变体，再通过分解、拼接的方式构造近似解，最终得到对数级的近似比。

备注：内容来源于stack exchange，提问作者slithy_tove