1

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

これに対する可能な解決策は、パスファインディング領域全体の周りに非表示の（ユーザーには表示されないがアルゴリズムには表示される）壁を配置し、開始ノード、終了ノード、およびすべての壁ノードがこれらの範囲内にあることを確認することです。壁、2〜3スペースのパディングなど。何かのようなもの：

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

...最終的にすべてのノードがクローズドリストに追加され、オープンリストが空になり、その時点で有効なパスが存在しないことがわかります。

これは問題の合理的な解決策のように見えますか？これがうまくいかない可能性がある方法はありますか？別の解決策は、同時にエンドから逆方向にパスファインドすることであることを理解していますが、これは、特にエンドノードがそれほど緊密に囲まれていない場合、潜在的にコストがかかる可能性があるようです。

4

4 に答える 4

2

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

于 2010-12-29T08:20:18.040 に答える
1

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

また、次のようなこともできます。「フィールドに閉じたボックスがあり、x時間後にパスがないため、y％の確率でパスがないと言え、y％を更新して時間の経過とともに増加しますが、決して100％に達します。

検索領域を制限し、何もしないことの真っ只中にある素晴らしい解決策かもしれません。

于 2010-12-29T08:34:51.703 に答える
0

私も同様の問題を抱えていました。これが私がしたことです。

  1. AからBを検索して、n回の反復でアルゴリズムを実行します。
  2. Bから始めてAを検索し、n回の反復でアルゴリズムを実行します。

どちらかの実行で、どちらかが完全に分離された領域にある（開いているノードがない）と判断された場合、検索は失敗します。それ以外の場合、検索は通常どおりに行われます。

ここでの秘訣は、もちろん、 nの適切な値を考え出すことです。nを増やしながら複数のパスを実行し、結果をキャッシュしました（グラフはあまり変化しませんでした）。

于 2012-01-31T14:07:25.863 に答える
0

A *を使用しているので、コストで地形ノードに重みを付けることができるはずです。壁のノードにめちゃくちゃ高いコストをかけます。これは、可能なパスの合計コストよりも大きくなければなりません。パスの最終コストがその境界コストよりも大きい場合、パスを見つけるために壁を通過する必要があったため、無効です。A *アルゴリズムは高コストのノードを迂回するため、必要がない限り壁を迂回することはありません。

于 2012-01-31T14:23:21.023 に答える