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?
pgrouting
routing
shooting-star
donni
fuente
fuente
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?
fuente