¿Cómo calcular el algoritmo heurístico de estrella fugaz?

8

Tengo un problema con el algoritmo de la estrella fugaz. Es mi proyecto final y necesito ayuda.

Mi pregunta es ¿cómo puedo calcular el algoritmo heurístico de la estrella fugaz? Puedo usar la estrella fugaz pgrouting , pero no entiendo cómo calcular la estrella fugaz heurística.

He buscado la calculadora estrella fugaz heurística en el libro de Internet, pero no puedo encontrarla ahora.


¿Puede contarme sobre el algoritmo de la estrella fugaz, no solo el código fuente, Sr. Mario?

donni
fuente

Respuestas:

2

Si te entiendo correctamente, y no soy un experto, pero tal vez puedas encontrar algo en el código fuente de la función heurística de estrella fugaz y modificarlo también según tus necesidades. Por supuesto, tendrías que construir pgrouting nuevamente.

Mario Miler
fuente
Gracias Sr.Mario Miler, su código fuente es el mismo con pgrouting o biblioteca en Postgresql, Postgis.
donni
Este es el código fuente del repositorio de pgrouting. Deberá descargar todo el repositorio, cambiar la función heurística de su elección y compilarlo. Puede encontrar algunas instrucciones aquí pgrouting.org/docs/1.x/install_ubuntu.html .. pequeño, viejo pero debería funcionar. No he construido pgrouting desde hace algún tiempo, así que no puedo decirte si hay algún problema.
Mario Miler
¿Puede hablarme sobre el algoritmo de la estrella fugaz, señor Mario?
donni
¿Puede contarme sobre el algoritmo de la estrella fugaz, no solo el código fuente, Sr. Mario?
donni
Shooting Start es solo un nombre elegante para lo que esencialmente sigue siendo A *. Simplemente enruta entre enlaces en lugar de nodos. Vea esta discusión: download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/…
Uffe Kousgaard
1

Recibo este de la lista de correo. Disparar * se basa en el borde, por lo que va de borde a borde, mientras que A * y Dijkstra van de vértice a vértice. Por lo tanto, necesita una estructura de datos que mantenga todos los bordes adyacentes para cada borde de su gráfico. También se puede hacer haciendo un gráfico lineal (http://en.wikipedia.org/wiki/Line_graph) a través de su red de carreteras original. Y luego puede asignar un costo de pasaje de borde a borde (como un atributo especial de su estructura de bordes adyacentes o como un costo del gráfico lineal) que en realidad representa cualquier tipo de limitaciones o penalizaciones por ir de un borde a otro, como como restricciones de giro en caso de giros o cualquier otro tipo de restricciones como semáforos. Teniendo esto, puede usar A * o cualquier otro algoritmo de ruta más corta usando bordes como vértices.

Entonces, esa es una idea detrás del Shooting *.

Y obtengo este agaian de Anton Patrushev: http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/276.html . Escribe así: en A * estamos usando algo similar a la función Manhattan (| Dx | + | Dy |) / 2 http://pgrouting.postlbs.org/browser/trunk/core/src/astar_boost_wrapper.cpp#L75 Allí verás otros intentos comentados. Intentamos diferentes funciones está bien. Probablemente, fue una razón histórica. función heurística y por alguna razón (no lo recuerdo ahora) decidí que para una red de carreteras común, en In Shooting * estamos usando la distancia euclidiana. http://pgrouting.postlbs.org/browser/trunk/core/src/shooting_star_boost_wrapper.cpp#L100 .

La otra fórmula: - Distancia euclidiana> Sqrt (Dx² + Dy² + Dz²); - Distancia de Manhattan> | Dx | + | Dy | + | Dz | ; - Distancia máxima> Máx. (| Dx |, | Dy |, | Dz |).

Todavía no entiendo todo. Amigo, ¿Puedes decirme brevemente y detalles de la estrella fugaz del algoritmo de proceso?

donni
fuente