私の経路探索エリアの周りに境界線を置くことは許容されますか？

Question

私は現在、無限グリッド上のパスを計算するためにA *経路探索アルゴリズムを使用しています（GridWorldのUnboundedGrid、AP CSのケーススタディ、誰にも役立つ場合）。エンドノードが完全に壁に囲まれているため、有効なパスが存在しない場合を除いて、すべてが素晴らしく機能します。予想どおり、アルゴリズムは無限に探索を続け、エンドノードを見つけることはありません。

可能な解決策は、開始ノード、終了ノード、およびすべての壁を確認しながら、不可視（ユーザーは表示されていませんがアルゴリズムはそうしているように）、経路探索領域全体の壁を配置することですノードはこれらの壁の中にあり、2〜3個のスペースが埋められています。ような何か：

_________________________________ 
|        | 
|    S |    | 
|   _____| _____  | 
|      | E |  | 
|      |___|  | 
|_______________________________| 

...最終的にすべてのノードがclosedlistに追加されますアイデアビーイングは、openlistは空になり、その時点で私は有効なパスが存在しないことを知っているだろう。

これは問題の妥当な解決策のようですか？これが潜在的に間違っている可能性のある方法はありますか？私は別の解決策は、終わりから後方へ同時に進路を見つけることであると理解していますが、特にエンドノードがきつく囲まれていない場合には、コストがかかる可能性があります。

Answer 1

エンドノードがどこにあるのか正確に分かりませんか？そうする場合は、アルゴリズムを実行する前に囲まれているかどうかを確認してください。

Answer 2

あなたの質問にも私のコメントも見てください。入力後、私は素晴らしい解決策を思いつきました。これは、あなたがあなたのエンドノードを知らず、上記のようにあなたのエンドノードの位置で何もできない場合です。

あなたは可能性もの線に沿って何か：「私はパスがないと言う、とを更新することができのy％ propability持つので、私はX時間後、私の分野で密閉箱なしのパスを発見しましたYの時間をかけて増加する％が、100％に達することはありません。

は、探索領域の境界と何もしないの真ん中にある素敵な解決策になるかもしれません。

Answer 3

私は同様の問題を抱えていたし、ここで何私はですした：

B.探しAから始まる N反復、0

1. 実行アルゴリズム
2. 実行アルゴリズムA.

探しBから始まるN反復のためにいずれかの実行が判断した場合に1つまたはもう1つは完全に分離された領域にあります（これ以上ノードがオープンしていない場合）、検索は失敗します。そうでなければ、通常通り検索が行われます。

ここでのトリックは、もちろん、nの良い値を思い付くことです。 nが増えて複数のパスを実行し、結果をキャッシュしました（私のグラフはあまり変化しませんでした）。

Answer 4

あなたはA *を使用しているので、地形ノードにコストをかけて重み付けすることができます。壁のノードに非常に高いコストをかける。可能なパスの合計コストより大きくなければなりません。パスの終了コストがその境界コストより大きい場合、パスを見つけるために壁を渡さなければならないため、無効です。A *アルゴリズムはコストの高いノードの周りをルーティングするため、必要でない限り壁を経由しません。