Implementación A * en validación de PHP

Question

Este es un código que obtuve del sitio here y me gustaría saber si esta implementación de A * es correcta. Lo he visto y lo comparo con la página de wikipedia y parece válido. La razón por la que pregunto es porque en el sitio dice que todavía hay un error en este código, intenté encontrarlo pero no pude encontrar ninguno. Quiero cambiarlo, aunque por lo que se necesita un origen y de destino como parámetro de entrada

<?php 

class AStarSolver 
{ 
    function solve(&$s) 
    { 
     include_once('PQueue.class.php'); 
     $o = new PQueue(); 
     $l = array(); 
     $c = array(); 
     $p = array(); 
     $a = $s->getStartIndex(); 
     $z = $s->getGoalIndex(); 
     $d = $s->goalDistance($a); 

     $n0 = array('g'=>0, 'h'=>$d, 'i'=>$a, 'p'=>NULL, 'f'=>$d); 
     $o->push($n0, -$d); 
     $l[$a] = TRUE; 

     while (! $o->isEmpty()) 
     { 
      $n = $o->pop(); 

      if ($n['i'] == $z) 
      { 
       while ($n) 
       { 
        $p[] = $n['i']; 
        $n = $n['p']; 
       } 
       break; 
      } 

      foreach ($s->getNeighbors($n['i']) as $j => $w) 
      { 
       if ((isset($l[$j]) || isset($c[$j])) && isset($m) && $m['g'] <= $n['g']+$w) 
        continue; 

       $d = $s->goalDistance($j); 
       $m = array('g'=>$n['g']+$w, 'h'=>$d, 'i'=>$j, 'p'=>$n, 'f'=>$n['g']+$w+$d); 

       if (isset($c[$j])) 
        unset($c[$j]); 

       if (! isset($l[$j])) 
       { 
        $o->push($m, -$m['f']); 
        $l[$j] = TRUE; 
       } 
      } 
      $c[$n['i']] = $n; 
     } 
     return $p; 
    } 

} 

?> 

El código para el Pqueue se puede encontrar here

Answer 1

El sitio sugiere que el fallo podría estar en la clase PQueue.

En PQueue::pop este

$j+1 < $m 

es una prueba de si el nodo montón en $i tiene un hijo (a $j) o dos (en $j y $j+1).

Pero $m aquí es count($h) solo en la primera iteración a través del bucle, ya que el --$m en el bucle se evalúa todas las veces.

Mueva ese --$m junto al array_pop donde pertenece, y ese será un error menos.

---

Ahora para AStarSolver.

Las variables son (en relación con Wikipedia pseudocode):

• $o - conjunto abierto como cola de prioridad;
• $l - conjunto abierto como mapa codificado por índice;
• $c - conjunto cerrado como mapa por índice;
• $n - nodo actual (x x);
• $m - nodo vecino (y)??
• $j - índice de nodo vecino.

problemas que veo:

• $n = $o->pop() no es seguida por unset($l[$n['i']]). Como ambos $o y $l representan el mismo conjunto, deben mantenerse sincronizados.

• Según Wikipedia el conjunto cerrado sólo se utiliza si la heurística es monótona (y creo que una heurística distancia es monótona), y en ese caso, una vez que se añade un nodo al conjunto cerrado, nunca es visitado de nuevo. Este código parece implementar algunos other pseudocode, que elimina los nodos del conjunto cerrado.Creo que esto contradice el objetivo del conjunto cerrado, y la primera condición en el bucle interno debería ser

  if (isset($c[$j]) || isset($l[$j]) && isset($m) && $m['g'] <= $n['g']+$w)

  entonces podemos eliminar el unset($c[$j]).

• $m['g'] en esta condición debería ser el g-score de la colindante corriente indexada por $j. Pero $m tiene cualquier valor restante del bucle anterior: el nodo correspondiente a $j en una iteración anterior.

  Lo que necesitamos es una forma de encontrar un nodo y su g -sin índice por nodo. Podemos almacenar el nodo de la matriz $l: en lugar de $l[$j] = TRUE hacemos $l[$j] = $m y la condición anterior se convierte en

  if (isset($c[$j]) || isset($l[$j]) && $l[$j]['g'] <= $n['g']+$w)

• Ahora el truco. Si el nodo que acabamos de encontrar no está en el conjunto abierto, lo agregamos allí (ese es el $o->push y $l[$j] =).

  Sin embargo, si está en el conjunto abierto, encontramos un camino mejor hacia él, por lo que debemos actualizarlo. El código no hace esto y es complicado porque la cola de prioridad no proporciona una rutina para aumentar la prioridad de un elemento. Sin embargo, podemos reconstruir la cola de prioridad por completo y el último bit de código en el bucle interno se convierte en

  if (! isset($l[$j])) {
   $o->push($m, -$m['f']);
   $l[$j] = $m; // add a new element
} else {
   $l[$j] = $m; // replace existing element
   $o = new PQueue();
   foreach ($l as $m)
      $o->push($m, -$m['f']);
}

  Esto no es terriblemente eficiente, pero es un punto de partida. Cambiar un elemento en una cola de prioridad no es eficiente de todos modos, porque primero tiene que encontrar.

---

Incluso sin estos cambios el algoritmo encontrar un camino, simplemente no es el mejor camino. Se puede ver en los laberintos mencionados:

• En el crazy laberinto en el tercer circuito interno: el camino superior tomada alrededor es ligeramente más largo que el camino inferior habría sido debido a los obstáculos a la izquierda.

• En el laberinto big en la parte superior derecha de la ruta hay un bucle innecesario.

---

Dado que este estaba en mi mente, he implementado mi propia versión del algoritmo y lo publicó en una respuesta a su previous question.