0

私は、2Dグリッドで最も近い（多くの）ゴールノードへのパスを見つける必要があるプロジェクトに取り組んでいます（任意のノードで8つの接続：N、S、W、E、NW、NE、SW、SE）。途中で壁が道を塞いでいる場合があります。1 つのゴール ノードへのパスを見つけることに関しては問題ありませんが、どのゴールが最も近いかを合理的な時間内に見つけるにはどうすればよいでしょうか? すべてのゴール ノードに対して A* を実行し、見つかったすべてのパスの長さを比較することは合理的な方法だとは思いません。

A* は何らかの形で最も近いノードへのパスを見つけることができますか、それとも最も近いゴールを別の方法で見つけてから、唯一のゴールとして A* に渡す必要がありますか?

ここに画像の説明を入力

伝説：

ホワイト - 歩きやすい

灰色 - 壁

青 - 自分

緑 - ゴール

赤 - 敵 (X SQM で敵との距離を保つ予定です)

4

2 に答える 2

2

はい、EstimatedDistanceToEnd（別名h(x)）をすべてのエンドノードの最小推定値に設定するだけです。次に、終了ノードに到達したときに検索を停止します。

于 2013-03-13T00:34:59.663 に答える
1

A* は、目標状態以外のデータがある情報に基づいた検索用です...あなたの質問によると、関連するデータがないようで、目標状態が何であるかを知っているだけです。その場合は、単純にBFSを適用できます。

于 2013-03-10T20:18:38.690 に答える