最短の移動順序

Question

免責条項：この問題は私の過去のAI最終試験から生じたものです。そして私はそれが非常に興味深いと思ったが、私はそれを理解することができなかった。

説明があります： 迷路があると、隣接する白いセル間を自由に移動できますが、黒いセルはブロックされます。あなたは、上、下、左、右に移動しようとすることができます。その方向でブロックされていない場合、正常に移動します。ブロックされている場合は、同じ場所にいます。

a）どこで開始したかにかかわらず、Gで終わることを保証する移動の可能な限り短いシーケンスを見つけます。

Answer 1

任意の移動を行う前に、あなたはどの位置にあってもよいです。それぞれの移動の後、可能な位置のセットがシフトし、いくつかの可能な位置から移動すると壁に当たっても収縮することがあります。しかし、可能な位置の集合は決して大きくなることはありません。

発生する可能性のある位置のセットごとに頂点を持つ有向グラフ、各セットを左、右、上または下に移動することに続く4つのセットに接続する有向グラフを想定することができます。

あなたの仕事は、すべての位置のセットの頂点から、ターゲット位置のみを含むシングルトンセットの頂点までの最短経路を見つけることです。

最初に、適切な指標を使ってこのグラフにA *を実行します。しかし、可能なセットの数は非常に多いので、これが実現可能であるとは保証されません。私は人間の知性を使って、すぐに動く測定基準を選ぶことにしよう。

A *が妥当な時間内に完了し、A *がメトリックに置くルールに準拠するメトリックを選択できる場合は、見つかったパスが最短のメトリックであることが証明されます。

私の頭の上から離れて、私は最初に、セットの最も遠い位置からターゲットへの最短経路の長さを試してみるでしょう。たぶん空でない行と列の合計数と組み合わせて。

これは私がやることですが、私はAIの専門家ではありません。私はおそらく、あなたがこの手順を改善できるクラスで学んだことがあると推測しています。