从点列表的最佳路径C++

Question

我有这个要求： 我有一个点的列表，并为每个这些我有X，Y坐标。

我的目标是找到这些点之间的最佳路径（我必须使用所有点）。 例如：

A（XA，YA），B（XB，YB），C（XC，YC），d（XD，YD），E（X，Y） 我使用欧几里德计算两点

我的最优路径之间的距离例如：d，E，A，C，B

我该怎么做呢？

Answer 1

您正在描述一个被称为Traveling Salesman Problem的NP-Hard问题。

有没有已知的多项式解决方案这个问题，但有一些启发式的，它是在多项式时间运行，但不能保证找到最佳路径。

如果您想要最优化 - 可能需要一个brute force search。

Answer 2

问题确实是NP-Hard，但对于在欧几里得空间中有点并且使用欧几里得度量来测量距离的特殊情况，存在可以任意接近最优解的多项式时间逼近方案。查看this论文（欧几里德旅行推销员问题的一个比较着名的近似算法）。