En informática , el método de jerarquías de contracción es una técnica de aceleración para encontrar el camino más corto en un gráfico . Las aplicaciones más intuitivas son los sistemas de navegación para automóviles: un usuario desea conducir desde a utilizando la ruta más rápida posible. La métrica optimizada aquí es el tiempo de viaje. Las intersecciones están representadas por vértices , las secciones de la carretera que las conectan por aristas . Los pesos de los bordes representan el tiempo que lleva conducir a lo largo de este segmento de la carretera. Un camino de a es una secuencia de bordes (tramos de carretera); el camino más corto es el que tiene la suma mínima de pesos de borde entre todos los caminos posibles. La ruta más corta en un gráfico se puede calcular utilizando el algoritmo de Dijkstra pero, dado que las redes de carreteras constan de decenas de millones de vértices, esto no es práctico. [1] Las jerarquías de contracción es un método de aceleración optimizado para explotar las propiedades de los gráficos que representan las redes de carreteras. [2] La aceleración se logra mediante la creación de accesos directos en una fase de preprocesamiento que luego se utilizan durante una consulta de ruta más corta para omitir vértices "sin importancia". [2] Esto se basa en la observación de que las redes de carreteras son muy jerárquicas. Algunas intersecciones, por ejemplo los cruces de carreteras, son "más importantes" y están más arriba en la jerarquía que, por ejemplo, un cruce que conduce a un callejón sin salida. Los accesos directos se pueden utilizar para guardar la distancia calculada previamente entre dos cruces importantes, de modo que el algoritmo no tenga que considerar la ruta completa entre estos cruces en el momento de la consulta. Las jerarquías de contracción no saben qué caminos los humanos consideran "importantes" (por ejemplo, carreteras), pero se les proporciona el gráfico como entrada y pueden asignar importancia a los vértices usando heurísticas.
Las jerarquías de contracción no solo se aplican a los algoritmos de aceleración en los sistemas de navegación para automóviles, sino también en los planificadores de rutas basados en la web , la simulación de tráfico y la optimización logística. [3] [1] [4] Las implementaciones del algoritmo están disponibles públicamente como software de código abierto . [5] [6] [7] [8] [9]
Algoritmo
El algoritmo de jerarquías de contracción (CH) es un enfoque de dos fases para el problema de la ruta más corta que consta de una fase de preprocesamiento y una fase de consulta . Dado que las redes de carreteras cambian con poca frecuencia, se puede utilizar más tiempo (de segundos a horas) para calcular previamente algunos cálculos antes de responder a las consultas. Con estos datos calculados previamente, se pueden responder muchas consultas en muy poco tiempo (microsegundos) cada una. [1] [3] Los CH se basan en atajos para lograr esta aceleración. Un atajo conecta dos vértices y no adyacente en el gráfico original. Su peso de borde es la suma de los pesos de borde en el más corto- camino.
Considere dos grandes ciudades conectadas por una carretera. Entre estas dos ciudades, hay una multitud de cruces que conducen a pequeños pueblos y suburbios. La mayoría de los conductores quieren ir de una ciudad a otra, tal vez como parte de una ruta más grande, y no tomar una de las salidas en el camino. En el gráfico que representa este trazado de carretera, cada intersección está representada por un nodo y los bordes se crean entre las intersecciones vecinas. Para calcular la distancia entre estas dos ciudades, el algoritmo tiene que atravesar todos los bordes a lo largo del camino, sumando su longitud. Calcular previamente esta distancia una vez y almacenarla en un borde adicional creado entre las dos grandes ciudades guardará los cálculos cada vez que esta carretera deba evaluarse en una consulta. Esta ventaja adicional se denomina "atajo" y no tiene contrapartida en el mundo real. El algoritmo de jerarquías de contracción no tiene conocimiento sobre los tipos de carreteras, pero puede determinar qué accesos directos deben crearse utilizando solo el gráfico como entrada.
Fase de preprocesamiento
El algoritmo CH se basa en atajos creados en la fase de preprocesamiento para reducir el espacio de búsqueda, es decir, el número de vértices que CH tiene que mirar en el momento de la consulta. Para lograr esto, se realizan contracciones de vértices iterativas. Al contraer un vértice se elimina temporalmente del gráfico , y se crea un atajo entre cada par de vértices vecinos si el camino más corto desde a contiene . [2] El proceso de determinar si el camino más corto entre y contiene se llama búsqueda de testigos. Se puede realizar, por ejemplo, calculando una ruta desde a usando una búsqueda hacia adelante usando solo nodos aún no contratados. [3]
Orden de nodo
Los vértices del gráfico de entrada deben contraerse de manera que se minimice el número de aristas añadidas al gráfico por contracciones. Como el orden óptimo de los nodos es NP-completo , se utilizan [10] heurísticas . [2]
Existen heurísticas ascendentes y descendentes . Por un lado, las heurísticas ascendentes computacionalmente más baratas deciden el orden en el que contraer los vértices de forma codiciosa ; esto significa que el orden no se conoce de antemano, sino que se selecciona el siguiente nodo para la contracción después de que se haya completado la contracción anterior. Por otro lado, las heurísticas de arriba hacia abajo calculan previamente el orden de todo el nodo antes de que se contraiga el primer nodo. Esto produce mejores resultados pero necesita más tiempo de preprocesamiento. [2]
En la heurística ascendente , se utiliza una combinación de factores para seleccionar el siguiente vértice para la contracción. Como el número de accesos directos es el factor principal que determina el preprocesamiento y el tiempo de ejecución de la consulta, queremos mantenerlo lo más pequeño posible. El término más importante por el cual seleccionar el siguiente nodo para la contracción es, por lo tanto, el número neto de bordes añadidos al contraer un nodo.. Esto se define como dónde es el número de accesos directos que se crearían si iban a ser contratados y es el número de aristas incidentes a . Usando este criterio solo, una ruta lineal daría como resultado una jerarquía lineal (muchos niveles) y no se crearían atajos. Al considerar el número de vértices cercanos que ya están contraídos, se logra una contracción uniforme y una jerarquía plana (menos niveles). Esto se puede hacer, por ejemplo, manteniendo un contador para cada nodo que se incrementa cada vez que se contrae un vértice vecino. Los nodos con contadores más bajos se prefieren a los nodos con contadores más altos. [11]
La heurística de arriba hacia abajo , por otro lado, produce mejores resultados pero necesita más tiempo de preprocesamiento. Clasifican los vértices que forman parte de muchos caminos más cortos como más importantes que los que solo son necesarios para unos pocos caminos más cortos. Esto se puede aproximar mediante disecciones anidadas . [2] Para calcular una disección anidada, uno separa recursivamente un gráfico en dos partes, que luego se separan en dos partes y así sucesivamente. Es decir, encuentre un subconjunto de nodos que cuando se quita del gráfico separar en dos piezas disjuntas de aproximadamente el mismo tamaño de manera que . Coloque todos los nodos último en el orden del nodo y luego calcular recursivamente la disección anidada para y , [12] la intuición es que todas las consultas de la mitad del gráfico a la otra mitad del gráfico deben pasar por el pequeño separador y, por lo tanto, los nodos en este separador son de gran importancia. Las disecciones anidadas se pueden calcular de manera eficiente en redes de carreteras debido a sus pequeños separadores. [13]
Fase de consulta
En la fase de consulta, se realiza una búsqueda bidireccional partiendo del nodo inicial y el nodo objetivo en el gráfico original aumentado por los accesos directos creados en la fase de preprocesamiento. [2] El vértice más importante en el camino más corto entre y será cualquiera o ellos mismos o más importantes que ambos y . Por lo tanto, el vértice minimizando está en el más corto ruta en el gráfico original y sostiene. [2] Esto, en combinación con la forma en que se crean los accesos directos, significa que tanto la búsqueda hacia adelante como hacia atrás solo necesitan relajar los bordes que conducen a nodos más importantes (hacia arriba) en la jerarquía, lo que mantiene el espacio de búsqueda pequeño. [3] En todas las rutas ascendentes (descendentes) descendentes, se puede omitir la interior (descendente ascendente) porque se ha creado un acceso directo en la etapa de preprocesamiento.
Recuperación de ruta
Una consulta CH, como se describe arriba, produce el tiempo o la distancia desde a pero no el camino real. Para obtener la lista de bordes (carreteras) en el camino más corto, los atajos tomados deben descomprimirse. Cada atajo es la concatenación de dos bordes: dos bordes del gráfico original, o dos atajos, o un borde original y un atajo. El almacenamiento del vértice medio de cada atajo durante la contracción permite el desempaquetado recursivo en tiempo lineal de la ruta más corta. [2] [3]
Jerarquías de contracción personalizadas
Si los pesos de los bordes se cambian con más frecuencia que la topología de la red, CH puede extenderse a un enfoque de tres fases al incluir una fase de personalización entre la fase de preprocesamiento y la de consulta. Esto se puede utilizar, por ejemplo, para cambiar entre la distancia más corta y el tiempo más corto o incluir información de tráfico actual, así como las preferencias del usuario, como evitar ciertos tipos de carreteras (transbordadores, autopistas, ...). En la fase de preprocesamiento, la mayor parte del tiempo de ejecución se dedica a calcular el orden en que se contraen los nodos. [3] Esta secuencia de operaciones de contracción en la fase de preprocesamiento se puede guardar para cuando se necesiten posteriormente en la fase de personalización. Cada vez que se personaliza la métrica, las contracciones se pueden aplicar de manera eficiente en el orden almacenado utilizando la métrica personalizada. [2] Además, dependiendo de los nuevos pesos de los bordes, puede ser necesario volver a calcular algunos atajos. [3] Para que esto funcione, el orden de contracción debe calcularse utilizando disecciones anidadas independientes de la métrica. [1]
Extensiones y aplicaciones
Los CH, como se describió anteriormente, buscan una ruta más corta desde un nodo inicial hasta un nodo objetivo. Esto se denomina camino más corto uno a uno y se utiliza, por ejemplo, en los sistemas de navegación para automóviles. Otras aplicaciones incluyen hacer coincidir las trazas de GPS con los segmentos de la carretera y acelerar los simuladores de tráfico que deben considerar las rutas probables que toman todos los conductores en una red. En la predicción de ruta, uno intenta estimar hacia dónde se dirige probablemente un vehículo calculando qué tan bien sus posiciones actual y pasada concuerdan con una ruta más corta desde su punto de partida hasta cualquier objetivo posible. Esto se puede hacer de manera eficiente utilizando CH. [2]
En escenarios de uno a muchos , un nodo inicial y un conjunto de nodos de destino se dan y la distancia para todos tiene que ser calculado. La aplicación más destacada para las consultas de uno a varios son las búsquedas de puntos de interés. Los ejemplos típicos incluyen encontrar la gasolinera, el restaurante o la oficina de correos más cercanos utilizando el tiempo de viaje real en lugar de la distancia geográfica como métrica. [2]
En el escenario de la ruta más corta de muchos a muchos , un conjunto de nodos iniciales y un conjunto de nodos de destino se dan y la distancia para todos tiene que ser calculado. Esto se utiliza, por ejemplo, en aplicaciones logísticas. [2] Los CH pueden ampliarse a consultas de varios a varios de la siguiente manera. Primero, realice una búsqueda hacia atrás hacia arriba desde cada. Para cada vértice escaneados durante esta búsqueda, uno almacena en un balde . Luego, uno ejecuta una búsqueda ascendente hacia adelante desde cada, comprobando para cada cubo no vacío, si la ruta sobre el vértice correspondiente mejora la mejor distancia. Es decir, si para cualquier . [2] [3]
Algunas aplicaciones incluso requieren cálculos de uno a todos , es decir, encontrar las distancias desde un vértice de origena todos los demás vértices del gráfico. Como el algoritmo de Dijkstra visita cada borde exactamente una vez y, por lo tanto, se ejecuta en tiempo lineal, es teóricamente óptimo. Sin embargo, el algoritmo de Dijkstra es difícil de paralelizar y no es óptimo para la caché debido a su mala ubicación. Los CH se pueden utilizar para una implementación más óptima en caché. Para esto, una búsqueda ascendente hacia adelante desdeseguido de un escaneo descendente sobre todos los nodos en el gráfico enriquecido con accesos directos. La última operación escanea la memoria de forma lineal, ya que los nodos se procesan en orden decreciente de importancia y, por lo tanto, se pueden colocar en la memoria en consecuencia. [14] Tenga en cuenta que esto es posible porque el orden en el que se procesan los nodos en la segunda fase es independiente del nodo de origen.. [2]
En producción, los sistemas de navegación para automóviles deberían poder calcular las rutas de viaje más rápidas utilizando información de tráfico prevista y mostrar rutas alternativas. Ambos se pueden hacer usando CH. [2] El primero se denomina enrutamiento con redes dependientes del tiempo en las que el tiempo de viaje de un borde dado ya no es constante, sino más bien una función de la hora del día al entrar en el borde. Las rutas alternativas deben ser suaves, significativamente diferentes del camino más corto, pero no significativamente más largas. [2]
Los CH se pueden ampliar para optimizar múltiples métricas al mismo tiempo; esto se denomina planificación de rutas con criterios múltiples . Por ejemplo, se podría minimizar tanto el costo como el tiempo de viaje. Otro ejemplo son los vehículos eléctricos para los que la carga de la batería disponible limita las rutas válidas, ya que es posible que la batería no se agote. [2]
Teoría
Se han establecido varios límites en el preprocesamiento y el rendimiento de consultas de las jerarquías de contracción. En el siguiente vamos ser el número de vértices en el gráfico, el número de aristas, la dimensión de la carretera, y el diámetro del gráfico.
El análisis del desempeño de la jerarquía de contracción se basa en parte en una cantidad conocida como dimensión de la carretera . Si bien la definición de esta cantidad es técnica, intuitivamente un gráfico tiene una pequeña dimensión de autopista si por cada hay un escaso conjunto de vértices tal que cada camino más corto de longitud mayor que incluye un vértice de . Calcular el valor exacto de la dimensión de la autopista es NP-difícil, [15] pero para las cuadrículas se sabe que la dimensión de la autopista. [dieciséis]
Rendimiento de preprocesamiento
Algoritmo | Año | Complejidad del tiempo |
---|---|---|
Procesamiento aleatorio [17] | 2015 |
Rendimiento de la consulta
Técnica de algoritmo / análisis | Año | Complejidad del tiempo | Notas |
---|---|---|---|
Gráficos de crecimiento acotado [18] | 2018 | ||
Procesamiento aleatorio [17] | 2015 | Exacto, sin notación O; funciona con alta probabilidad | |
SHARC modificado [15] | 2010 | Preprocesamiento de polinomios | |
SHARC modificado [15] | 2010 | Preprocesamiento superpolinomial |
Referencias
- ^ a b c d Dibbelt, Julian; Strasser, Ben; Wagner, Dorothea (5 de abril de 2016). "Jerarquías de contracción personalizables". Revista de algoritmos experimentales . 21 (1): 1–49. arXiv : 1402.0402 . doi : 10.1145 / 2886843 .
- ^ a b c d e f g h i j k l m n o p q r Bast, Hannah; Delling, Daniel; Goldberg, Andrew V .; Müller-Hannemann, Matthias; Pajor, Thomas; Sanders, Peter; Wagner, Dorothea; Werneck, Renato F. (2016). "Planificación de rutas en redes de transporte". Ingeniería de algoritmos . Apuntes de conferencias en Ciencias de la Computación. 9220 : 19–80. arXiv : 1504.05140 . doi : 10.1007 / 978-3-319-49487-6_2 . ISBN 978-3-319-49486-9.
- ^ a b c d e f g h Geisberger, Robert; Sanders, Peter; Schultes, Dominik; Vetter, Christian (2012). "Enrutamiento exacto en grandes redes de carreteras mediante jerarquías de contracción". Ciencia del transporte . 46 (3): 388–404. doi : 10.1287 / trsc.1110.0401 .
- ^ Delling, Daniel; Sanders, Peter; Schultes, Dominik; Wagner, Dorothea (2009). "Algoritmos de planificación de rutas de ingeniería". Algoritmos de redes grandes y complejas . Apuntes de conferencias en Ciencias de la Computación. 5515 : 117-139. doi : 10.1007 / 978-3-642-02094-0_7 . ISBN 978-3-642-02093-3.
- ^ "OSRM - Máquina de enrutamiento de código abierto" .
- ^ "Wiki - OpenTripPlanner" .
- ^ "Web - GraphHopper" .
- ^ "GitHub - Tempus" .
- ^ "GitHub - RoutingKit" .
- ^ Bauer, Reinhard; Delling, Daniel; Sanders, Peter; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorothea (1 de marzo de 2010). "Combinando técnicas de aceleración jerárquicas y dirigidas a objetivos para el algoritmo de dijkstra" . Revista de algoritmos experimentales . 15 : 2.1. doi : 10.1145 / 1671970.1671976 . ISSN 1084-6654 .
- ^ Geisberger, Robert; Sanders, Peter; Schultes, Dominik; Delling, Daniel (2008). McGeoch, Catherine C. (ed.). "Jerarquías de contracción: enrutamiento jerárquico más rápido y sencillo en redes de carreteras". Algoritmos experimentales . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. 5038 : 319–333. doi : 10.1007 / 978-3-540-68552-4_24 . ISBN 9783540685524.
- ^ Bauer, Reinhard; Colón, Tobías; Rutter, Ignaz; Wagner, Dorothea (13 de septiembre de 2016). "Tamaño del espacio de búsqueda en jerarquías de contracción" . Informática Teórica . 645 : 112-127. doi : 10.1016 / j.tcs.2016.07.003 . ISSN 0304-3975 .
- ^ Delling, Daniel; Goldberg, Andrew V .; Razenshteyn, Ilya; Werneck, Renato F. (mayo de 2011). "Graficar particiones con cortes naturales". (: unav) : 1135–1146. CiteSeerX 10.1.1.385.1580 . doi : 10.1109 / ipdps.2011.108 . ISBN 978-1-61284-372-8.
- ^ Delling, Daniel; Goldberg, Andrew V .; Nowatzyk, Andreas; Werneck, Renato F. (2011). "PHAST: árboles de ruta más cortos acelerados por hardware". Simposio de procesamiento paralelo y distribuido (IPDPS), 2011 IEEE International : 921–931. doi : 10.1109 / ipdps.2011.89 . ISBN 978-1-61284-372-8.
- ^ a b c Abraham, Ittai; Fiat, Amos; Goldberg, Andrew (2010). Dimensión de la autopista, caminos más cortos y algoritmos demostrablemente eficientes (PDF) . Actas del simposio anual ACM-SIAM de 2010 sobre algoritmos discretos. doi : 10.1137 / 1.9781611973075.64 .
- ^ Kosowski, Adrian; Viennot, Laurent (2016). "Más allá de la dimensión de la carretera: etiquetas de distancias pequeñas con esqueletos de árboles". arXiv : 1609.00512 .
- ^ a b Funke, Stefan; Storandt, Sabine (2015). "Eficiencia demostrable de las jerarquías de contracción con preprocesamiento aleatorio". Algoritmos y computación . ISBN 978-3-662-48971-0.
- ^ Blum, Johannes; Funke, Stefan; Storandt, Sabine (2018). Espacios de búsqueda sublineales para la planificación de rutas más cortas en redes de cuadrículas y carreteras (PDF) . AAAI.
enlaces externos
Implementaciones de código abierto
- https://www.graphhopper.com/
- https://github.com/ifsttar/Tempus
- https://github.com/RoutingKit/RoutingKit
- http://project-osrm.org/
- http://www.opentripplanner.org/