10点あるとします。各ポイント間の距離を知っています。
すべてのポイントを通る最短ルートを見つける必要があります。
いくつかのアルゴリズム (Dijkstra、Floyd Warshall など) を試してみましたが、それらはすべて開始点と終了点の間の最短経路を提供してくれますが、すべてのポイントを含むルートを作成するわけではありません。
順列は問題なく機能しますが、リソースを大量に消費します。
この問題を調べるために、どのアルゴリズムをアドバイスしてもらえますか? または、上記のアルゴリズムでこれを行う文書化された方法はありますか?
巡回セールスマン問題を見てください。
いくつかのヒューリスティック ソリューションを調べることをお勧めします。彼らはあなたに 100% 正確な結果を与えることはできないかもしれませんが、多くの場合、妥当な時間内に十分な解決策 (最適な解決策から 2 ～ 3% 離れたもの) を見つけることができます。
これは明らかに巡回セールスマン問題です。具体的には、単純なアルゴリズムをN=10試すか、動的計画法を使用して、スペースを交換することでこれを に減らすことができます。O(N!)O(n^2 2^n)
さらに、これは NP 困難な問題であるため、通常の警告を考慮して、近似またはヒューリスティックを期待することしかできません。
他の人が述べたように、これは TSP のインスタンスです。ジョージア工科大学で開発されたConcordが現在の最先端のソルバーだと思います。数秒で 10,000 ポイント以上を処理できます。また、操作が簡単な API も備えています。
実際、これがあなたが探しているものだと思います：
コンピューター サイエンスでは、Floyd-Warshall アルゴリズム (WFI アルゴリズム [明確化が必要]、Roy-Floyd アルゴリズム、または単に Floyd のアルゴリズムとも呼ばれる) は、加重グラフ (正または負のエッジの重みを持つ) で最短経路を見つけるためのグラフ分析アルゴリズムです。 ）。アルゴリズムを 1 回実行すると、頂点のすべてのペア間の最短経路の長さ (重みの合計) が検出されますが、経路自体の詳細は返されません。
「パスの再構築」サブセクションでは、「パス」を保存するために必要なデータ構造について説明します (実際には、次に移動するノードを保存し、必要に応じて必要なパスを簡単に再構築します)。