Algoritmo A * no funciona correctamente

Question

Necesito ayuda con mi implementación de algoritmo A *. Cuando ejecuto el algoritmo, encuentra el objetivo, pero la ruta definitivamente no es la más corta :-P

Aquí está mi código, ayúdenme a detectar los errores. Creo que podría ser la ruta de reconstrucción que es mi problema, pero no estoy seguro.

public class Pathfinder { 

public List<Node> aStar(Node start, Node goal, WeightedGraph graph) { 
    Node x, y; 
    int tentative_g_score; 
    boolean tentative_is_better; 

    FScoreComparator comparator = new FScoreComparator(); 
    List<Node> closedset = new ArrayList<Node>(); 
    Queue<Node> openset = new PriorityQueue<Node>(10, comparator); 
    openset.add(start); 

    start.g_score = 0; 
    start.h_score = heuristic_cost_estimate(start, goal); 
    start.f_score = start.h_score; 

    while (!openset.isEmpty()) { 
     x = openset.peek(); 

     if (x == goal) { 
      return reconstruct_path(goal); 
     } 

     x = openset.remove(); 
     closedset.add(x); 

     for (Edge e : graph.adj(x)) { 

      if (e.v == x) { 
       y = e.w; 
      } else { 
       y = e.v; 
      } 

      if (closedset.contains(y) || y.illegal) { 
       continue; 
      } 

      tentative_g_score = x.g_score + e.weight; 

      if (!openset.contains(y)) { 
       openset.add(y); 
       tentative_is_better = true; 
      } else if (tentative_g_score < y.g_score) { 
       tentative_is_better = true; 
      } else { 
       tentative_is_better = false; 
      } 

      if (tentative_is_better) { 
       y.g_score = tentative_g_score; 
       y.h_score = heuristic_cost_estimate(y, goal); 
       y.f_score = y.g_score + y.h_score; 
       y.parent = x; 
      } 

     } 

    } 

    return null; 

} 

private int heuristic_cost_estimate(Node start, Node goal) { 
    return Math.abs(start.x - goal.x) + Math.abs(start.y - goal.y); 
} 

private List<Node> reconstruct_path(Node current_node) { 
    List<Node> result = new ArrayList<Node>(); 

    while (current_node != null) { 
     result.add(current_node); 
     current_node = current_node.parent; 
    } 

    return result; 
} 

private class FScoreComparator implements Comparator<Node> { 

    public int compare(Node n1, Node n2) { 
     if (n1.f_score < n2.f_score) { 
      return 1; 
     } else if (n1.f_score > n2.f_score) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

}

Gracias a todos por todas las grandes respuestas! ¡Mi algoritmo A * ahora funciona perfectamente gracias a ustedes! :-)

¡Esta fue mi primera publicación y este foro es realmente increíble!

Answer 1

Estás cambiando la prioridad de un elemento en la PriorityQueue después de haber insertado. Esto no es compatible, ya que la cola de prioridad no es consciente de que un objeto ha cambiado. Lo que puede hacer es eliminar y volver a agregar el objeto cuando cambie.

La prioridad se cambia en la línea: y.f_score = y.g_score + y.h_score;. Esta línea ocurre después de agregar y a la cola de prioridad. Tenga en cuenta que simplemente mover la línea openset.add(y); a después de calcular el costo no será suficiente, ya que y puede haber sido agregado en una iteración previa.

Tampoco está claro en su código si la heurística que utilizó es admissible. Si no lo es, también hará que obtenga rutas subóptimas.

Finalmente, una nota de rendimiento: El método contains en ArrayList y PriorityQueue lleva tiempo lineal en ejecutarse, lo que hará que el tiempo de ejecución de su implementación no sea óptimo. Puede mejorar esto agregando propiedades booleanas a los nodos para indicar si están en los conjuntos cerrados/abiertos, o usando una estructura de datos establecida.

Answer 2

La cola de prioridad no actualiza la posición del elemento cuando cambia su prioridad. Por lo tanto, la propiedad de montón no es válida. La prioridad modificada afecta las adiciones/eliminaciones de otros elementos, pero no repara la propiedad del montón.

por lo tanto, no obtiene el mejor artículo de abierto -> no encuentra la ruta más corta.

Puede: 1) escribir su propia pila y mantener el índice en que 2) añadir otro objeto en PQ y marcar el anterior como no válido (debe en lugar de nodo de poner algún objeto con el indicador de validez y la referencia a nodo en cola).

2) tienen un peor rendimiento y desaconsejo, pero algunos programas de navegación utilizan este enfoque (o al menos hace unos años atrás).

edit: La mejor práctica es, inserte inmutable (o al menos con partes imutable que significa prioridad) objetos en PriorityQueue