長方形の海があるとしましょう。それはかなり大きいです - 10000x20000。
島もあります。簡単にするために、それらも長方形であると仮定しましょう。私たちは彼らの正確な場所（座標）を知っています。
地図上のどこかに船がある場合、(x1, y1)、どの島も越えずに地図上の別の地点 (x2, y2) への最短経路を見つけるにはどうすればよいでしょうか?
更新:これまでのところ、船または海の制約はありません。いくつか追加することで物事を単純化 (および高速化) できれば、これは大歓迎です。
パスは最高である必要はありません。たとえば、10% オフにすることもできます。完全に受け入れられます。
このようなグラフは 10000x20000 グリッドよりはるかに小さく、より現実的なパスをより適切な時間で見つけることができます
更新: 島が大きくない場合は、船を終点の方向に移動し、左または右の境界で島を迂回することができます
グリッドをグラフとして表現し、ダイクストラ アルゴリズムを実行してみます。
グラフはおそらく 1G またはそれ以上かかりますが、最新のコンピューターの RAM に収まります。
アルゴリズムの複雑さは O(E + V*log(V))、つまり O(グリッドのサイズ) です。〜10 ^ 8ノードがあるので、それは実現可能であるに違いないと思います。ノードあたり最大 1000 の CPU ティックがあるとします。4G CPU の場合、1 ティックは 2.5*10^-10 秒、つまり 2.5*10-7 秒です。ノードごと。2*10^8 ノードの場合、約 1 分かかります。
大きなシーで島が比較的まばらである場合は、昨年実装したアルゴリズムを使用して、回避するオブジェクトのある環境でロボットが動くボールを追いかけることができます。
私がしたことは、ロボット、ボール、障害物の周囲にグリッド ポイントを定義し、環境全体にまばらな均一グリッドを追加することでした。2 つのグリッドポイント間のエッジのコストは、障害物がこのエッジにどれだけ近いかによって異なります (エッジが障害物を通過する場合、コストは無限になります)。次に、A* を使用して最適なルートを計算します。これは、Java でプログラムされた古いラップトップで毎秒 40 回実行されます。
Tiendil の提案に関連して、LaValle の計画アルゴリズムの本には、島が 2D ポリゴンである場合に最短経路検索のグラフにどのエッジを含めるかについての議論があります。