Die Manhattan-Distanz ist überschätzt und macht mich verrückt

Ich implementiere ein Sternalgorithmus mit Manhattan-Distanz die zu lösen 8-Puzzle (in C). Es scheint sehr gut zu funktionieren und besteht viele Unit-Tests, findet aber in einem Fall nicht den kürzesten Pfad (es findet 27 Schritte statt 25).

Wenn ich die heuristische Funktion auf ändere Hamming-Distanz es findet in 25 Schritten. Auch findet in 25 Schritten, wenn ich die Manhattan-Distanzfunktion mache, die Hälfte der eigentlichen Kosten zurück.

Deshalb glaube ich, dass das Problem irgendwo in der Manhattan-Entfernungsfunktion liegt und die Kosten überschätzt werden (daher unzulässig). Ich dachte, vielleicht läuft etwas anderes im C-Programm schief, also habe ich ein kleines Python-Skript geschrieben, um nur die Ausgabe der Manhattan-Distanzfunktion zu testen und zu verifizieren, und beide erzeugen genau das gleiche Ergebnis.

Ich bin wirklich verwirrt, weil die heuristische Funktion der einzige Fehlerpunkt zu sein scheint und gleichzeitig richtig zu sein scheint.

Du kannst es versuchen dieser Löser und geben Sie die Kachelreihenfolge wie “2,6,1,0,7,8,3,5,4” ein. Wählen Sie den Algorithmus Manhattan-Distanz und es findet in 25 Schritten. Ändern Sie es jetzt in Manhattan-Distanz + linearer Konflikt und es findet 27 Schritte.

Aber meine Manhattan-Distanz (ohne linearen Konflikt) findet in 27 Schritten statt.

Hier ist mein allgemeiner Algorithmus:

manhattan_distance = 0
iterate over all tiles
if the tile is not the blank tile:
find the coordinates of this tile on the goal board
manhattan_distance += abs(x - goal_x) + abs(y - goal_y)

Ich denke, wenn mit einem wichtigen Teil etwas sehr falsch wäre, würde es nicht alle über 25 vorherigen Tests bestehen, also könnte dies eine Art Grenzfall sein.

Hier ist die kommentierte Manhattan-Distanzfunktion in C:

int ManhattanDistance(Puzzle p, State b){
   State goal = getFinalState(p);
   int size = getSize(b);
   int distance = 0;
   if (getSize(goal) == size){ // both states are the same size
      int i, j;
      for(i=0; i<size; i++){
         for(j=0; j<size; j++){ // iterate over all tiles
            int a = getStateValue(b, i, j); // what is the number on this tile?
            if (a != 'B'){ // if it's not the blank tile
               int final_cordinates[2];
               getTileCoords(goal, a, final_cordinates); // find the coordinates on the other board
               int final_i = final_cordinates[0];
               int final_j = final_cordinates[1];
               distance +=  abs(i - final_i) + abs(j - final_j);
            }
         }
      }
   }
   return distance;
}

Bitte hilf mir.

BEARBEITEN: Wie in den Kommentaren besprochen, kann der zum Öffnen von Knoten bereitgestellte Code gefunden werden hier

Das Problem scheint nicht in Ihrer heuristischen Funktion zu liegen, sondern im Algorithmus selbst. Aufgrund Ihrer Beschreibung des Problems und der Tatsache, dass es nur in einigen bestimmten Fällen auftritt, glaube ich, dass es mit dem erneuten Öffnen eines geschlossenen Scheitelpunkts zu tun hat, sobald Sie einen besseren Weg dorthin gefunden haben.

Beim Lesen des von Ihnen bereitgestellten Codes [in comments]ich glaube, ich habe verstanden, wo das Problem liegt, in Zeile 20:

if(getG(current) + 1 < getG(children[i])){

Das ist falsch! Sie prüfen, ob g(current) + 1 < g(children[i])möchten Sie eigentlich nach Folgendem suchen: f(current) + 1 + h(children[i]) < g(children[i])da Sie diesen Wert mit der heuristischen Funktion von überprüfen möchten children[i]und nicht von current!

Beachten Sie, dass es mit set identisch ist f(children[i]) = min{f(children[i]),f(current)+1}und dann hinzufügen h(children[i]) um das zu bekommen g Wert.