3

とても簡単な質問があります。

私は 8 パズル (8 つの数字 (1 から 8) + 空白 (=0) ) に取り組んでいます。

ハミング距離 (間違った位置にある数字) とマンハッタン距離 (開始位置と最終位置の間の水平方向と垂直方向の距離) を計算するとき、結果を計算するために「空白」スペースを考慮する必要がありますか?

例えば..

 |7 2 4|
 |5 _ 6|
 |8 3 1|

ゴール状態で

 |_ 1 2|
 |3 4 5|
 |6 7 8|

何が正しいですか？

  • ハミング距離 = 8 (配置されていないすべての数字) または 9 (0 = 空白も考慮される)
  • マンハッタン距離 (距離(7)、距離(2)、距離(4)、...) = 3 (=1+2) + 1 (=1+0) + 2 (1+1) + 2 (2+ 0) + 0 (空白) + 3 (1+2) + 2 (2+0) + 3 (1+2) + 3 (2+1) --> 空白を考慮しない場合は 18 、空白あり (+2)は 20 です。何が正しいですか。

ありがとうございました

4

1 に答える 1

4

ヒューリスティックを許容できるようにする場合は、空白のタイルをカウントしないでください。

例えば

|1 _ 2|  
|3 4 5|  
|6 7 8|

本当の答えは 1 ですが、空のタイルを数えるとマンハッタン距離は 2 です。それは許容できるヒューリスティックではありません。

于 2012-10-29T03:46:42.957 に答える