tren - metro nueva york precio

La distancia de Manhattan es sobre estimar y volverme loco

Question

Estoy implementando el algoritmo a -star con la distancia de Manhattan para resolver el 8-puzzle (en C). Parece funcionar muy bien y pasa muchas pruebas unitarias, pero no encuentra el camino más corto en un caso (encuentra 27 pasos en lugar de 25).

Cuando cambio la función heurística a la distancia de Hamming, se encuentra en 25 pasos. También se encuentra en 25 pasos cuando hago la función de distancia de Manhattan para devolver la mitad del costo real.

Por eso creo que el problema se encuentra en algún lugar de la función de distancia de Manhattan y está sobre estimando el costo (por lo tanto, inadmisible). Pensé que tal vez algo anda mal en el programa C, así que escribí un pequeño script Python para probar y verificar la salida de la función de distancia de Manhattan solamente y ambas producen exactamente el mismo resultado.

Estoy realmente confundido porque la función heurística parece ser el único punto de falla y al mismo tiempo parece ser correcta.

Puede probar este solucionador y colocar el orden de mosaico como "2,6,1,0,7,8,3,5,4". Elija el algoritmo de distancia de Manhattan y lo encontrará en 25 pasos. Ahora cámbiala a la distancia de Manhattan + conflicto lineal y encuentra 27 pasos.

Pero mi distancia de Manhattan (sin conflicto lineal) se encuentra en 27 pasos.

Aquí está mi algoritmo general:

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)

Creo que si hubiera algo muy malo con alguna parte importante, no pasaría las más de 25 pruebas anteriores, por lo que este podría ser un caso de ventaja.

Aquí se comenta la función de distancia de Manhattan en 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;
}

Por favor, ayúdame.

EDITAR: Como se comentó en los comentarios, el código proporcionado para los nodos de apertura se puede encontrar here

Answer 1

El problema parece no estar en su función heurística, sino en el algoritmo mismo. Desde su descripción del problema, y ​​el hecho de que ocurre solo en algunos casos específicos, creo que tiene que ver con la reapertura de un vértice cerrado, una vez que encuentre un mejor camino hacia él.

Al leer el código que ha proporcionado [en comentarios], creo que entendí dónde se encuentra el problema, en la línea 20:

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

¡Esto está mal! Está comprobando si g(current) + 1 < g(children[i]) , en realidad desea verificar: f(current) + 1 + h(children[i]) < g(children[i]) , ya que desea comprobar este valor con la función heurística de los children[i] , y no de la current !
Tenga en cuenta que es idéntico a establecer f(children[i]) = min{f(children[i]),f(current)+1} , y luego agregar h(children[i]) para obtener el valor de g .