C++経路探索、最適化

Question

イム私は私の経路探索コードはビットを最適化することができれば疑問には、このマップを見てみましょう囲まれている...しかし、Aスターは可能性のある道路がないことを確認するためにすべてのフィールドをチェックしなければならない。まあ、それは小さな地図では問題ではありません。しかし、私は256x265の地図を持っていると、すべての点をチェックするのに多くの時間がかかります。

+ - wall, . - free, S - start, F - finish, X - closed node 
.S............. 
.........XXXXX. 
.........X+++X. 
.........X+F+X. 
.........X+++X. 
.........XXXXX. 

そして、私は（仕上げの「部屋」への入り口はありません）このような状況で終了したい：私は私が意味する、フィニッシュarroundの閉じられたノードが存在している間、私は検索を停止することができると思います。私はhをチェックすると思っていましたが、開いているノードはどれも近づいていませんでしたが、終了しました...しかし、もしokかどうかわからない場合は、もっと良い方法がありますか？

任意の応答のためのThanx。

Answer 1

まず、この問題はbreadth-first searchで解決できますが、代わりにa-starを使用する理由があると思います。ただし、何らかの検索（幅優先または深さ優先検索）でSとFの間の接続性を最初に確認することをお勧めします。これは私たちの問題を解決します。

Answer 2

マップが変更されないと仮定すると、それをconnected componentsに分割して前処理することができます。それは速くdisjoint set data structureで行うことができます。その後、A *を起動する前に、ソースとデスティネーションが同じコンポーネントに属することを一定時間チェックします。パスがない場合は、パスを見つけるためにA *を実行します。

欠点は、接続されたコンポーネントの数をCとすると、n = ceil（logC）のセルあたり追加のnビットが必要になることです。あなたは十分なメモリがあり、それを買う余裕があるなら、それは問題ありません。

編集：nを小さく（たとえば1バイト）固定し、その数より多くのコンポーネントを持つ場合（たとえば、8ビットnの場合は256以上）、複数のコンポーネントに同じ番号を割り当てることができます。最良の結果を得るには、各component-idに割り当てられているセルの数がほぼ同じであることを確認します。