複数の場所の間の最短経路を見つけます。C＃

Question

私はそれらの座標と現在の位置もlatの長さのリストを持っています。 私の場所のリスト（lat-longs）に基づいて最短ルートを見つけたい

ちょうど私は、ルートに沿って位置をソートする必要があります。

ご協力いただければ幸いです。

Answer 1

ちょっとした背景。 "セールスマン"の問題を解決しようとしているようです。すなわち、セールスマンがすべての顧客を訪問する（またはすべての場所に旅行する）最善のルートは何ですか？

この中で最も有名なアルゴリズムはDjikstra's algorithm です。これは基本的にグラフ内のすべてのノード間の最短経路を見つけるアルゴリズムです。

グラフデータ構造内で場所を表すことができれば、おそらくDjikstrasアルゴリズムを使用して問題を解決できます。

ただし、グラフにノードが多すぎる（場所が多すぎる）場合、このアルゴリズムを使用して最短距離を取得することはできません。これは、アルゴリズムが非常に時間が複雑でグラフのノードが多いほど、答えを計算するのにかかる時間が長くなるためです。これが当てはまる場合は、他のアルゴリズムを使用して最短経路を近似する必要があります。これはあなたに実際の最短経路を与える可能性は低いですが、それはあなたにかなり良い道を与えるはずです。このアプローチのアルゴリズムはSimulated annealingです。アプリケーションごとに特定の変数を微調整する必要があるため、かなり複雑です。