c++ - 点列表中的最佳路径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

您正在描述一个被称为旅行商问题的NP-Hard问题。

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

如果您想要最佳 -可能需要蛮力搜索。

Answer 2

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