-1

nxn グリッドに n 台の車両があります。最初は上の行 1 に並べられています。(1,n) の車両が (n, n − i + 1) に到達するように、車両は一番下の行に到達する必要があります。各タイム ステップで、各車両は上下左右に 1 マスずつ移動するか、そのままの状態で移動できます。ビークルが動かない場合、隣接する 1 台のビークル (ただし 1 台を超えることはできません) が飛び越えることができます。2 台の車両が同じマスを占有することはできません。次のヒューリスティックのうち、すべての車両を目的地に移動させる問題で許容できるものはどれですか?

私。1 から n までの合計 (h1 ... hn)

ii. max(h1 ... hn)

iii. min(h1 ...hn)

iii だけが正しいと思いますが、その理由をどのように定式化すればよいかわかりません。

4

1 に答える 1

5

誰かが非常に詳細な回答をしてくれると確信していますが、私のように AI のすべてに少し圧倒される可能性がある人への好意として、許容できるヒューリスティックは非常に単純です。

目標に到達するための真のコストを決して過大評価しないヒューリスティック

あまりにも無慈悲に聞こえるかもしれませんが、あなたが投稿した問題は、宿題の問題または課題からのものであるかのように聞こえます. これら 3 つのヒューリスティックのうちどれが許容され、どれが許容されないかを正確に調べる楽しみを台無しにしたくはありませんが、1 つの文の定義が役立つことを願っています。

混乱した場合は、覚えておいてください。車両が両方とも目標に到達した後、実際のコストがヒューリスティックが想定したものよりも少ないことがわかった場合、それは容認できません。

于 2013-01-28T23:52:09.940 に答える