Les mostraré un documento:
Investigación sobre el algoritmo de búsqueda de ruta más corta para mapas
Estudiante: Li Tutor: Dong Luan
Resumen: Hasta ahora, un gran número de expertos y académicos nacionales y extranjeros han realizado investigaciones en profundidad sobre el "problema del camino más corto". A través del análisis teórico y la aplicación práctica, las ventajas y desventajas del algoritmo de búsqueda en amplitud (BFS), el algoritmo de búsqueda en profundidad (DFS) y el algoritmo A * se comparan sistemáticamente desde todos los aspectos.
Palabras clave: algoritmo de búsqueda de ruta más corta; algoritmo de búsqueda de primero en profundidad;
Algoritmo de búsqueda de ruta más corta en el mapa
Resumen: hasta ahora, A; Un gran número de expertos y académicos nacionales y extranjeros han realizado investigaciones en profundidad sobre el "problema del camino más corto". Este artículo estudia el algoritmo de búsqueda en amplitud (BFS), el algoritmo de búsqueda en profundidad (DFS) y el algoritmo A* desde cualquier aspecto del sistema a través del análisis teórico y la aplicación práctica.
Palabras clave: algoritmo de ruta más corta; algoritmo de amplitud primero; algoritmo A*;
Prólogo:
El problema de la ruta más corta es un sistema de información geográfica ( SIG) Uno de los contenidos importantes del análisis de redes, también tiene un significado importante en la teoría de grafos. Muchos problemas en la vida real están relacionados con el "problema del camino más corto", como el enrutamiento de redes, el diseño de circuitos integrados, problemas de cableado, navegación electrónica, transporte y turismo, etc. Este artículo utiliza el algoritmo de búsqueda primero en profundidad, el algoritmo de búsqueda primero en amplitud y el algoritmo A * para discutir y analizar un problema específico, y compara las ventajas y desventajas de los tres algoritmos.
En el estudio de los algoritmos de búsqueda de la ruta más corta del mapa, los principios de comparación de las ventajas y desventajas de varios algoritmos siguen principalmente los siguientes tres puntos: [1]
(1) Integridad de el algoritmo: propuesto Una pregunta tiene una respuesta y el algoritmo puede garantizar que se pueda encontrar la respuesta correspondiente. La integridad de un algoritmo es uno de los excelentes indicadores del rendimiento del algoritmo.
(2) Complejidad temporal del algoritmo: haga una pregunta, ¿cuánto tiempo le toma al algoritmo encontrar la respuesta correspondiente? La velocidad del algoritmo es un reflejo importante de la calidad del algoritmo.
(3) Complejidad espacial del algoritmo: ¿cuánto espacio de almacenamiento requiere el algoritmo cuando busca respuestas a preguntas? Cuantos menos recursos ocupe el algoritmo, mejor será su rendimiento.
Algoritmo de búsqueda del camino más corto en el mapa:
1. Búsqueda en amplitud
Búsqueda en amplitud, también conocida como búsqueda en amplitud o La búsqueda horizontal primero es uno de los algoritmos de búsqueda de gráficos más simples. Este algoritmo también es el prototipo de muchos algoritmos de gráficos importantes. Tanto el algoritmo de ruta más corta de fuente única de Dijkstra como el algoritmo de árbol de expansión mínima de Prim adoptan ideas similares a la búsqueda en amplitud. La búsqueda en amplitud, también conocida como BFS, es un método de búsqueda ciega que tiene como objetivo expandir y examinar sistemáticamente todos los nodos del gráfico para encontrar resultados. En otras palabras, busca exhaustivamente en todo el gráfico sin considerar las posibles direcciones del resultado hasta encontrar el resultado. BFS no utiliza un algoritmo de regla general.
El pseudocódigo del algoritmo de búsqueda en amplitud es el siguiente: [2-3]
BFS(v)// Búsqueda en amplitud G, comenzando desde el vértice v
//Todos los vértices buscados están marcados como visitados (i)=1.
Los valores iniciales de los componentes de //Visitado// son todos 0.
Visitado (v) = 1;
q =[]; //Inicializa Q como una cola con un solo elemento v.
Cuando Q no está vacío
u = del head(Q);
For es adyacente a todos los vértices que hacemos de u.
Si visitó(w)=0, entonces
AddQ(w, Q); //Coloque W al final de la cola q.
Visitado (w) = 1
endif
Fin
Hora de finalización
Fin de BFS
p>Aquí se llaman dos funciones: AddQ(w, Q) coloca w al final de la cola Q; DelHead(Q) toma el primer vértice de la cola Q y lo elimina de Q. Repita el proceso DelHead(Q) hasta que la cola Q esté vacía.
Integridad: el algoritmo de búsqueda en amplitud está completo.
Esto significa que no importa qué tipo de gráfico, mientras el objetivo exista, BFS definitivamente lo encontrará. Sin embargo, si el objetivo no existe y el gráfico es infinito, BFS no convergerá (no terminará).
Complejidad temporal: en el peor de los casos, BFS debe encontrar todas las rutas a los nodos posibles, por lo que su complejidad temporal es, donde |V es el número de nodos en el gráfico, |E| bordes en el gráfico.
Complejidad espacial: debido a que todos los nodos deben almacenarse, la complejidad espacial de BFS es, donde |V| es el número de nodos en el gráfico y |E| Otra forma de decirlo es que la complejidad espacial de BFS es O (B), donde B es el coeficiente de rama máximo del árbol y m es la longitud de ruta más larga del árbol. Debido a la enorme demanda de espacio, BFS no es adecuado para resolver problemas muy grandes. [4-5]
2. Algoritmo de búsqueda en profundidad
La búsqueda en profundidad, abreviada como DFS, es un algoritmo de retroceso. Como sugiere el nombre del algoritmo, la estrategia de búsqueda seguida por la búsqueda en profundidad es buscar en el gráfico lo más profundamente posible. [6] En resumen, el proceso consiste en buscar a lo largo de los vecinos de un vértice hasta que el vértice actualmente buscado no tenga vecinos no visitados. En este momento, la ruta original del vértice buscado por el predecesor regresa al vértice visitado buscado anteriormente por él, y este vértice se utiliza como el vértice buscado actualmente. Continúe este proceso hasta que la ejecución ya no sea posible.
El pseudocódigo del algoritmo de búsqueda en profundidad es el siguiente: [7]
DFS(v) //Visita todos los vértices alcanzados por v.
Visitado (v) = 1;
For es adyacente a cada vértice w do de v.
Si visitado(w)=0, entonces
DFS(w);
endif
End
Fin de DFS
Como algoritmo de búsqueda, DFS juega un papel importante en la búsqueda de soluciones a problemas NP (incluido NPC). Sin embargo, la complejidad temporal del algoritmo de búsqueda es O (n!) y su eficiencia es relativamente baja. Cuando aumenta el tamaño de los datos, este algoritmo se vuelve insuficiente. [8] Hay muchas soluciones al problema de eficiencia de la búsqueda en profundidad. El más común es la poda, que consiste en eliminar ramas de búsqueda inútiles. Hay dos tipos: poda factible y poda óptima.
BFS: particularmente efectivo para resolver los problemas más cortos o mínimos, con poca profundidad de búsqueda, pero la desventaja es el gran consumo de memoria (es necesario abrir una gran cantidad de celdas de la matriz para almacenar el estado).
DFS: es eficaz para resolver todos los problemas de recorrido y búsqueda. Es muy rápido cuando la profundidad de búsqueda del problema es pequeña y muy ineficiente cuando la profundidad es grande.
Algoritmo 3.A*
Un artículo de 1968, "P. E. Hart, N. J. Nelson y B. Raphael. Heurística para determinar gráficos Base formal de rutas de costo mínimo. IEEE Trans. Sci and Cybernetics, SSC-4(2):100-107, 1968. [9] Desde entonces, se ha desarrollado un algoritmo ingenioso y eficiente, que se utiliza ampliamente en campos relacionados. El algoritmo A* en realidad introduce una función de evaluación. Basado en la búsqueda de amplitud, no expande todos los nodos expandibles a la vez, sino que utiliza la función de evaluación para realizar la evaluación en todos los nodos no expandidos para encontrar el nodo que debe expandirse más y expandirlo hasta encontrar el nodo de destino.
El pseudocódigo del proceso de búsqueda principal del algoritmo A* es el siguiente: [10]
Crea dos tablas, la tabla abierta guarda todos los nodos que se han generado pero. no investigado, y la tabla cerrada registra los nodos que han sido visitados.
Calcular la estimación del punto de partida;
Colocar el punto de partida en la tabla abierta;
Y (ON!=NULL) //Desde la mesa abierta table Tome el nodo n con el valor estimado más pequeño f;
Si (n nodo = = nodo objetivo) break
endif
Para (cada nodo hijo de el nodo actual n x)
Calcule el valor estimado de x;
si (X está abierto)
si (el valor estimado de x es menor que el valor estimado de la tabla abierta)
Establecer n como el padre de x;
Actualizar el valor estimado en la tabla abierta //Obtener el valor estimado de la ruta mínima;
endif
endif
Si (se incluye X)
si (la estimación de x es menor que la estimación de la tabla CLOSE)
Establezca n como el padre de x;
Actualice el valor estimado en la tabla de liquidación;
Coloque el nodo X en OPEN // para obtener el valor estimado del camino mínimo.
endif
endif
Si (X no está en el camino)
Establezca n como el padre de x;
Encuentra la estimación de x;
E inserta x en la tabla abierta; //Aún no ordenado
endif
Termina en
Inserte n nodos en la tabla cerrada;
Ordene los nodos en la tabla abierta según el valor estimado // De hecho, es para comparar el tamaño del nodo F en la tabla abierta; , desde el nodo con el camino más corto para proceder a continuación.
finalizar mientras (abierto! = vacío)
Guardar la ruta, es decir, comenzando desde el punto final, cada nodo se mueve a lo largo del nodo padre hasta el punto inicial, este es su path;
p>
A *Análisis de algoritmo:
Tanto DFS como BFS son búsquedas ciegas al expandir nodos secundarios, es decir, no elegirán qué nodo es mejor en la siguiente búsqueda, pero salta a ese nodo Siguiente búsqueda. En el caso de mala suerte, donde es necesario explorar todo el espacio del conjunto de soluciones, es obvio que solo se puede aplicar a la búsqueda de problemas de pequeña escala. La mayor diferencia entre el algoritmo A* y las búsquedas ciegas como DFS y BFS es que cuando el nodo de búsqueda actual selecciona el siguiente nodo, puede elegir mediante una función heurística, seleccionar el nodo con el costo más pequeño como el siguiente nodo de búsqueda, y salta sobre él. [11] El algoritmo a* utiliza la comprensión del problema y el proceso de resolución de problemas para buscar información heurística que sea beneficiosa para la resolución de problemas, y luego utiliza esta información heurística para buscar el camino óptimo. En lugar de recorrer todo el mapa, busca en una dirección determinada basándose en una función heurística en cada paso. Cuando el mapa es grande y complejo, su complejidad computacional es mucho mejor que la del algoritmo de Dijkstra. Este es un algoritmo de búsqueda muy rápido y eficiente. Sin embargo, el algoritmo A* correspondiente también tiene sus desventajas. La información heurística se agrega artificialmente, es altamente subjetiva y depende directamente de la experiencia del operador. Diferentes situaciones utilizan diferentes información heurística y funciones heurísticas. Su selección es difícil y en gran medida no se puede encontrar el camino óptimo.
Resumen:
Este artículo describe algunos pasos del algoritmo de ruta más corta, resume algunas ventajas y desventajas de cada algoritmo y algunas relaciones entre algoritmos. Aunque BFS o DFS son fáciles de usar, debido a limitaciones de tiempo y espacio, solo pueden resolver problemas de pequeña escala. BFS debe usarse para los problemas más cortos o mínimos, y DFS debe usarse al atravesar y resolver todos los problemas. En cuanto al algoritmo A*, es un algoritmo de búsqueda heurística y un algoritmo de prioridad óptima. Es adecuado para problemas de pequeña, gran y ultra gran escala, pero el algoritmo de búsqueda heurística es muy subjetivo y su calidad depende de la experiencia del programador y de la función heurística elegida, por lo que es relativamente difícil escribir un Excelente programa que utiliza el algoritmo A*. Cada algoritmo tiene sus propias ventajas y desventajas. Elegir algoritmos razonables para diferentes problemas es la mejor manera.
Referencias:
[1] Chen, Teng, Chen Qinghua. Análisis de caso de cuatro algoritmos de ruta más corta [J]. Conocimiento y tecnología informática (Academic Exchange), 2007(16):1030-1032
Yin, Yin. El algoritmo de ruta más corta para gráficos y su aplicación en redes [J Software Guide, 2011(07):51-53.
Liu Wenhai, Xu Rongcong.
Varios algoritmos de ruta más corta y comparación [J]. Fujian Computer, 2008(02):9-12.
Deng Chunyan. Comparación de dos algoritmos de ruta más corta [J]. Conocimiento y tecnología informática, 2008(12):511-513
Wang Sunan, Wei Songren, Jiang Wenshengren. Comparación de algoritmos de camino más corto [J]. Ingeniería de sistemas y electrónica, 1994 (05): 43-49.
Xu, Li Tianzhi. Algoritmo para resolver todos los caminos más cortos[J]. Ingeniería y ciencia informática, 2006 (12): 83-84
Li, Liu Runtao. Un algoritmo de ruta más corta basado en Dijkstra [J]. Journal of Harbin University of Science and Technology, 2008 (03): 35-37
Xu Dao. Un nuevo algoritmo para encontrar el camino más corto [J]. Ingeniería y ciencia informática, 2006 (02).
[9]Yan Chunshen. Un algoritmo mejorado de profundidad primero basado en gráficos y un algoritmo de Dijkstra para el programa de patrulla policial [J 2010 Conferencia Internacional sobre Ingeniería Eléctrica y Control Automático, 2010(3): 73-77
[10] Busong Ya. VC++ implementa el camino más corto basado en el algoritmo de Dijkstra [J]. Información científica y tecnológica (enseñanza e investigación científica), 2008 (18): 36-37
Yang, Wang, Ma. Implementación de un algoritmo de optimización y análisis del camino más corto [J]. Journal of Jilin University (Information Science Edition), 2002 (02): 70-74