從點列表的最佳路徑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論文（歐幾里德旅行推銷員問題的一個比較着名的近似算法）。