8-Puzzle: Hamming und Manahttan Heuristik betrachten "Leerzeichen"?

Question

Ich habe eine sehr einfache Frage.

ich arbeite 8-Puzzle (8-Nummern (1 bis 8) + Rohling (= 0))

Wenn Hammingdistanz Berechnung (Zahlen in falscher Position) und Manhattan-Abstand (Abstand horizontal + vertikalen zwischen Start und Endposition) sollte ich "Leerzeichen" berücksichtigen, um das Ergebnis zu berechnen?

Zum Beispiel ..

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

mit Zielzustand

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

Was ist richtig?

• Hamming distance = 8 (jede Zahl an Ort und Stelle nicht) oder 9 (auch 0 = leer betrachtet)
• Manhattan-Abstand (Abstand (7), Abstand (2), Entfernung (4), .. .) = 3 (= 1 + 2) + 1 (= 1 + 0) + 2 (1 + 1) + 2 (2 + 0) + 0 (leer) + 3 (1 + 2) + 2 (2 + 0) + 3 (1 + 2) + 3 (2 + 1) -> ohne Berücksichtigung leer ist 18, mit Leerzeichen (+2) ist 20. Was ist richtig?

Danke

Answer 1

Wenn Sie die Heuristik für zulässig zu erklären wollen, dann sollten Sie nicht leere Zelle zählen.

zum Beispiel

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

die wirkliche Antwort 1 ist, aber Manhattan Abstand ist 2, wenn Sie die leere Kachel zählen. Das kann nicht die zulässige Heuristik sein.