私は難しい問題に直面しています:
セルの巨大な行列で表された国全体の地図があるとします。各セルは、1 平方メートルの領域を表します。各セルはdouble、セルを通過するコストを表す 0 ～ 1 の値として表されます。
マップは明らかにメモリに収まりません。
始点から終点までのロボットの最適な経路を計算する方法に頭を悩ませようとしています。私が最初に思いついたのは、TCP のような移動ウィンドウを作成し、移動ロボットの周りに実際のマップのミニマップを配置し、その中で A* アルゴリズムを実行することでしたが、巨大な壁のあるマップでいくつかの問題に直面しています。パスファインディングなど...
A* のようなアルゴリズムに関する文献を検索していますが、この問題の適切な解決策を視覚化できませんでした。
誰かが同様の問題に直面したか、解決策のアイデアを手伝ってくれるかどうか疑問に思っています!
前もって感謝します ：）
私は正確なデータを知らないので、ここに役立つかもしれないいくつかの情報があります：
最短経路の部分経路は、それ自体が最短経路です。つまり、行列を部分行列に分割し、そこに（すべての）最短経路を見つけることができます。すべての結果を保存する必要はないことに注意してください。たとえば、完全なパスを保存せずに、情報だけを保存することでメモリを節約できます。パスはからAになりBます。中間ノードは、後で再度計算されるか、後で使用するためにファイルに保存される場合があります。特定の領域の最短経路を事前に計算できる場合もあります。
もう1つのアプローチは、何らかの方法でマトリックスを圧縮できる可能性があることです。つまり、1つの同じ数だけで構成される大きな領域がある場合は、その数とその領域の寸法だけを格納するとよい場合があります。
別のアプローチ（いくつかの最短経路の事前計算に関連して）は、マップのさまざまなレベルの詳細を生成することです。米国の地図を考えると、これは次のようになります。最も粗いレベルの詳細には、ニューヨーク、ロサンゼルス、シカゴ、ダラス、フィラデルフィア、ヒューストン、フェニックスの都市だけが含まれます。レベルが細かいほど、含まれる都市は多くなりますが、一方で、マップ全体の小さな領域が表示されます。
ここにいくつかのアイデアがあります
パスを区分線形曲線としてモデル化できます。31 個の線分がある場合、曲線は 60 個の数字で完全に記述されます。考えられる各曲線にはコストがあるため、コストは次の形式の関数です。
cost(x1, x2, x3 ..... x60)
ここでの問題は、60 変数の関数の大域的最適解を見つけることです。これを行うには、標準的な方法を使用できます。1 つのアイデアは、遺伝的アルゴリズムを使用することです。別のアイデアは、パラレルテンパリングなどのモンテカルロ法を使用することです
http://en.wikipedia.org/wiki/Parallel_tempering
有望なパスがある場合はいつでも、それを開始点として使用して、コスト関数の局所的最小値を見つけることができます。補間を使用して、コスト関数を微分可能にすることができます。次に、ニュートン法（またはBFGS）を使用して、コスト関数の局所最小値を見つけることができます。
http://en.wikipedia.org/wiki/Local_minimum
http://en.wikipedia.org/wiki/BFGS
あなたの問題は、化学系の反応経路を見つける問題に多少似ています。Davis Wales の著書「Energy Landscapes」からインスピレーションを得ることができるかもしれません。
しかし、いくつか質問があります：
問題に特別な構造がありますか。たとえば、三角形の不等式が成り立つか、最短経路が往復しないことを保証できますか? クエリを何度も実行しますか? （そうであれば、複数のクエリで償却する前処理を行うことができます。）正確な最小解が必要ですか、それともイプシロン係数内の何かで問題ありませんか？
1 つの考えは、マトリックスを粗くすることができるというものでした。つまり、100 メートル x 100 メートルの正方形を形成し、100 × 100 の正方形を通る最短経路距離を決定します。これでメモリ (約 1 ギガバイト) に収まります。Dijkstra を実行してから、各ステップを 100 \times 100 平方に展開します。
また、ダイクストラのアルゴリズムの前方後方バージョンを実行してみましたか? つまり、ソースから拡張し、同時にシンクを検索し、交差点で停止します。
ついでに言うと、なぜこのような細かいレベルの粒度が必要なのですか?