algorithm - 検索パスはほとんど空の加重グリッドです

Question

A から B へのパスを 8 連結グリッド (上下左右および対角線) で見つける必要があります。問題は、このグリッドのほとんど (25 ～ 60%) が空ですが、通過する必要がある可能性がある高い加重値 (空のタイルの重さの約 20 倍) を持つ特定のスポットがあることです。RSR と JPS で A* のようなものを見てきましたが、それらは重み付けされていないグリッドのみのようです。今、私は A* の実装を進めましたが、思ったより遅いです。完全に最適化されたアルゴリズムさえ必要ありません。それに近いものだけです。

Answer 1

JPSは、障害のある均一なグリッドに対して定式化および分析されました。障害物を扱うように「異常な」タイルを扱うと、JPS が機能すると思います (つまり、均一な領域を高速で移動できます)。JPS の著者は、彼のJPS ブログ投稿へのコメントで次のように推測しています(そして、それはかなり明白なようです)。

単純に、現在のノードとは異なる地形タイプの隣接ノードを強制として扱います。これにより、均一コストのリージョンをすばやく検索し、別のリージョンに移動するときにノードの展開を停止し、反対側でジャンプを続けることができます。

ただし、グリッドが不均一であるだけでなく、ペナルティ タイルに加えてボーナス タイルもあると暗示しているようです。それらにも対処する必要があります (たとえば、すべてのグリッドの重みをバイアスして、負の重みを回避します)。

Answer 2

速度が問題になる場合は、グラフィック ハードウェア (CUDA や OpenCL など) の使用を検討してください。 この論文では、3D グリッド上で回転する 2D ロボットのパスを見つけるための「ブラシファイア」アルゴリズムについて説明します。あなたは2次元ですが、それはあなたの問題とほぼ同じです。