Una cola de prioridad (PQ) es una estructura de datos abstracta (ADS). Hay muchas posibilidades para implementarlos. Desafortunadamente, la prioridad_queue suministrada con la biblioteca estándar de C++ es bastante limitada, y otras implementaciones son mucho mejores para implementar A *. Spoilers: puede usar std :: set/multiset en lugar de std :: priority_queue. Pero sigue leyendo:
Entonces, ¿qué es lo que necesita de la cola de prioridad para implementar A * es:
- Consigue el nodo con el menor coste
- disminuir los costos de elementos arbitrarios
Cualquier cola de prioridad puede hacer 1., pero para 2., necesita una cola de prioridad "mutable". El Standard-Lib no puede hacer esto. Además, necesita una forma fácil de encontrar entradas en la cola de prioridad, para averiguar dónde disminuir las teclas (para cuando A * encuentre una mejor ruta a un nodo ya abierto). Hay dos formas básicas de hacerlo: almacena un identificador en el elemento de cola de prioridad dentro de su nodo de gráfico (o usa un mapa para almacenar esos identificadores para cada nodo de gráfico) o inserta los nodos de gráfico en sí.
Para el primer caso, donde almacena identificadores para cada nodo, puede usar std :: multiset para su cola de prioridad. std :: multiset :: first() siempre será su clave de "menor costo", y puede disminuir una clave quitándola del conjunto, cambiando el valor y volviendo a insertar, y actualizando el identificador. Alternativamente, puede usar las colas de prioridad mutables de Boost.Heap, que soportan directamente "disminuir clave".
Para el segundo caso, necesitaría algún tipo de árbol binario "intrusivo", ya que los nodos de pathfinding deben estar en la cola de prioridad. Si no desea hacer su propia versión, consulte los contenedores asociativos ordenados en Boost.Intrusive.
http://stackoverflow.com/questions/11912736/c-a-star-implementation-determining-whether-a-node-is-already-in-the-priori – Rost
@Rost ha .. que partido – Icebone1000