algorithm - 検索アルゴリズムと動的に動作する障害物

Question

ドア、鍵、壁だけを含む環境に関心があります。キーが「拾われた」場合（つまり、キーを含むノードが訪問された場合）、ドアを通過できます。

問題は、与えられた点 A と B の間の経路を見つけることです。最適解は必要ありません。

ドアを「D」、キーを「K」、壁を「#」で表現してみましょう。次に、以下の環境を考えてみましょう。ゴールはB、原点はAです。空のマスは「.」で表します。

###..........K
#BD...A.......
###...........

さて、明らかにこの場合、ゴール B に向かう前に K を含むノードを訪問する必要があります。このアプローチは、大量のメモリと時間を消費するため苦労します。

この特定の問題に最も適していると思われるアルゴリズムを知りたいです。または、私のアルゴリズムの選択は正しいが、ヒューリスティックは貧弱ですか? アドバイスしてください。私は新しいので、できるだけ説明してください。

乾杯。

Answer 1

私はこれを 2 段階の問題として扱います。第 1 段階では、自動化された計画アルゴリズムを使用して、イベントがキー/ドア/ポイント B を訪れている場合の実行可能な一連のイベントを決定します。互いに素な集合のデータ構造は、2 つの場所が空きスペースを介して接続されているかどうかを時間の経過とともに判断するのに役立ちます。およびロック解除されたドア。第 2 段階では、A* を使用して計画を実現します。