c++ - ポイントC ++のリストからの最適パス

Question

私はこの要求を持っています:私は点のリストを持っていて、これらのそれぞれについて私はX、Y座標を持っています。

私の目標は、これらのポイント間の最適なパスを見つけることです (すべてのポイントを使用する必要があります)。例えば：

A (xa, ya), B (xb, yb), C (xc, yc), D (xd, yd), E (x, y) 2 点間のユークリッド距離の計算を使用します

私の最適なパスは、たとえば、D、E、A、C、B です。

どうすればこれを作ることができますか?

Answer 1

あなたは巡回セールスマン問題として知られているNP困難な問題を説明しています。

この問題に対する既知の多項式の解決策はありませんが、多項式時間で実行されているヒューリスティックがいくつかありますが、最適なパスを見つけることが保証されていません。

最適なものが必要な場合は、ブルートフォース検索が必要になる場合があります。

Answer 2

問題は確かに NP 困難ですが、ユークリッド空間に点があり、距離を測定するためにユークリッド メトリックを使用する特殊なケースでは、最適解に任意に近づくことができる多項式時間近似スキームがあります。この論文 (ユークリッド巡回セールスマン問題の比較的有名な近似アルゴリズム) を確認してください。