jerarquías de contracción

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 grafo . Las aplicaciones más intuitivas son los sistemas de navegación de automóviles: un usuario quiere conducir desde${\displaystyle A}$a${\displaystyle B}$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 , los tramos de carretera que las conectan por aristas . Los pesos de las aristas representan el tiempo que se tarda en recorrer este segmento de la carretera. Un camino desde${\displaystyle A}$a${\displaystyle B}$es una secuencia de aristas (tramos de carretera); el camino más corto es aquel con la suma mínima de pesos de aristas entre todos los caminos posibles. El camino más corto en un grafo se puede calcular utilizando el algoritmo de Dijkstra, pero, dado que las redes de carreteras constan de decenas de millones de vértices, esto es impracticable. ^{[ 1 ]} Las jerarquías de contracción son un método de aceleración optimizado para explotar las propiedades de los grafos que representan redes de carreteras. ^{[ 2 ]} La aceleración se logra creando atajos en una fase de preprocesamiento que luego se utilizan durante una consulta de camino más corto para omitir vértices "sin importancia". ^{[ 2 ]} Esto se basa en la observación de que las redes de carreteras son altamente jerárquicas. Algunas intersecciones, por ejemplo, los cruces de autopistas, son "más importantes" y están más arriba en la jerarquía que, por ejemplo, un cruce que lleva a un callejón sin salida. Los atajos se pueden utilizar para guardar la distancia precalculada entre dos cruces importantes de modo que el algoritmo no tenga que considerar el camino completo entre estos cruces en el momento de la consulta. Las jerarquías de contracción desconocen qué carreteras consideran "importantes" los humanos (por ejemplo, las autopistas), pero se les proporciona el grafo como entrada y son capaces de asignar importancia a los vértices mediante heurísticas.

Las jerarquías de contracción no solo se aplican para acelerar algoritmos en sistemas de navegación de automóviles , sino también en planificadores de rutas basados ​​en la web , simulación de tráfico y 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 ]}

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 . Como las redes de carreteras cambian con poca frecuencia, se puede usar más tiempo (de segundos a horas) para precalcular algunos cálculos antes de que se respondan las consultas. Usando estos datos precalculados, se pueden responder muchas consultas tomando 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${\displaystyle u}$y${\displaystyle v}$no adyacentes en el grafo original. Su peso de arista es la suma de los pesos de las aristas en la más corta${\displaystyle u}$-${\displaystyle v}$camino.

Consideremos dos grandes ciudades conectadas por una autopista. Entre estas dos ciudades, existe una multitud de cruces que conducen a pequeños pueblos y suburbios. La mayoría de los conductores desean ir de una ciudad a la otra —quizás como parte de una ruta más larga— y no tomar ninguna de las salidas intermedias. En el grafo que representa este trazado vial, cada intersección se representa mediante un nodo y se crean aristas entre intersecciones vecinas. Para calcular la distancia entre estas dos ciudades, el algoritmo debe recorrer todas las aristas a lo largo del camino, sumando sus longitudes. Precalcular esta distancia una vez y almacenarla en una arista adicional creada entre las dos grandes ciudades ahorrará cálculos cada vez que se deba evaluar esta autopista en una consulta. Esta arista adicional se denomina "atajo" y no tiene equivalente en el mundo real. El algoritmo de jerarquías de contracción no tiene conocimiento de los tipos de carreteras, pero es capaz de determinar qué atajos deben crearse utilizando únicamente el grafo 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 examinar en el momento de la consulta. Para lograr esto, se realizan contracciones iterativas de vértices. Al contraer un vértice${\displaystyle v}$Se elimina temporalmente del gráfico.${\displaystyle G}$y se crea un acceso directo entre cada par.${\displaystyle \{u,w\}}$de vértices vecinos si el camino más corto desde${\textstyle u}$a${\textstyle w}$contiene${\displaystyle v}$. ^{[ 2 ]} El proceso de determinar si el camino más corto entre${\textstyle u}$y${\textstyle w}$contiene${\displaystyle v}$se denomina búsqueda de testigos. Se puede realizar, por ejemplo, calculando una ruta desde${\displaystyle u}$a${\displaystyle w}$utilizando una búsqueda hacia adelante utilizando solo nodos aún no contraídos. ^{[ 3 ]}

Orden de los nodos

Los vértices del grafo de entrada deben contraerse de manera que se minimice el número de aristas añadidas al grafo mediante contracciones. Como el ordenamiento óptimo de nodos es NP-completo , ^{[ 8 ]} se utilizan heurísticas . ^{[ 2 ]}

Existen heurísticas ascendentes y descendentes . Por un lado, las heurísticas ascendentes, computacionalmente más económicas, deciden el orden en que se contraen los vértices de forma voraz ; esto significa que el orden no se conoce de antemano, sino que el siguiente nodo se selecciona para su contracción una vez completada la anterior. Por otro lado, las heurísticas descendentes precalculan el orden de todos los nodos antes de que se contraiga el primero. Esto produce mejores resultados, pero requiere más tiempo de preprocesamiento. ^{[ 2 ]}

En las heurísticas ascendentes , se utiliza una combinación de factores para seleccionar el siguiente vértice para la contracción. Dado que el número de atajos es el factor principal que determina el tiempo de ejecución del preprocesamiento y la consulta, queremos mantenerlo lo más pequeño posible. Por lo tanto, el término más importante para seleccionar el siguiente nodo para la contracción es el número neto de aristas añadidas al contraer un nodo.${\displaystyle x}$Esto se define como${\displaystyle A(x)-|\{(u,x)\colon (u,x)\in E\}|}$dónde${\displaystyle A(x)}$es el número de accesos directos que se crearían si${\displaystyle x}$debían ser contratados y${\displaystyle |\{(u,x)\colon (u,x)\in E\}|}$es el número de aristas incidentes a${\displaystyle x}$Utilizando únicamente este criterio, una ruta lineal daría como resultado una jerarquía lineal (muchos niveles ) y no crearía 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 conseguir, 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 entonces a los nodos con contadores más altos. ^{[ 9 ]}

Por otro lado, las heurísticas descendentes producen mejores resultados, pero requieren más tiempo de preprocesamiento. Clasifican los vértices que forman parte de muchos caminos más cortos como más importantes que aquellos que solo son necesarios para unos pocos caminos más cortos. Esto se puede aproximar utilizando disecciones anidadas . ^{[ 2 ]} Para calcular una disección anidada, se separa recursivamente un grafo en dos partes, que a su vez se separan en dos partes, y así sucesivamente. Es decir, se encuentra un subconjunto de nodos.${\displaystyle S\subseteq V}$que cuando se elimina del gráfico${\displaystyle G}$separado${\displaystyle G}$en dos piezas disjuntas${\displaystyle G_{1},G_{2}}$de tamaño aproximadamente igual, de tal manera que${\displaystyle S\cup G_{1}\cup G_{2}=G}$. Colocar todos los nodos${\displaystyle v\in S}$último en el ordenamiento de nodos y luego calcular recursivamente la disección anidada para${\displaystyle G_{1}}$y${\displaystyle G_{2}}$[ ^{10 ]} La intuición es que todas las consultas de una mitad del grafo a la otra mitad del grafo 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 eficientemente en redes de carreteras debido a sus pequeños separadores ^{. [ 11 ]}

Fase de consulta

En la fase de consulta, se realiza una búsqueda bidireccional a partir del nodo inicial.${\displaystyle s}$y el nodo objetivo${\displaystyle t}$en el grafo original aumentado por los atajos creados en la fase de preprocesamiento. ^{[ 2 ]} El vértice más importante en el camino más corto entre${\displaystyle s}$y${\displaystyle t}$será o${\displaystyle s}$o${\displaystyle t}$ellos mismos o más importantes que ambos${\displaystyle s}$y${\displaystyle t}$. Por lo tanto, el vértice${\displaystyle u}$minimizando${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)}$está en el más corto${\displaystyle s-t}$ruta en el gráfico original y${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)=\mathrm {dist} (s,t)}$se mantiene. ^{[ 2 ]} Esto, en combinación con la forma en que se crean los atajos, 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 pequeño el espacio de búsqueda. ^{[ 3 ]} En todos los caminos arriba-(abajo-arriba)-abajo, el interior (abajo-arriba) se puede omitir, porque se ha creado un atajo en la etapa de preprocesamiento.

Recuperación de ruta

Una consulta CH, como se describió anteriormente, proporciona el tiempo o la distancia desde${\displaystyle s}$a${\displaystyle t}$pero no el camino real. Para obtener la lista de aristas (caminos) en el camino más corto, es necesario desempaquetar los atajos tomados. Cada atajo es la concatenación de dos aristas: dos aristas del grafo original, dos atajos o una arista original y un atajo. Almacenar el vértice central de cada atajo durante la contracción permite desempaquetar recursivamente la ruta más corta en tiempo lineal. ^{[ 2 ] [ 3 ]}

Si los pesos de los bordes 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 puede usarse, por ejemplo, para alternar entre la distancia más corta y el tiempo más corto, o incluir información de tráfico actual, así como preferencias del usuario, como evitar ciertos tipos de carreteras (ferries, autopistas, etc.). 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 puede guardarse para cuando se necesiten posteriormente en la fase de personalización. Cada vez que se personaliza la métrica, las contracciones pueden aplicarse 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 recalcular algunos atajos. ^{[ 3 ]} Para que esto funcione, el orden de contracción debe calcularse utilizando disecciones anidadas independientes de la métrica. ^{[ 1 ]}

Los CH, como se describió anteriormente, buscan la ruta más corta desde un nodo de inicio a un nodo de destino. Esto se denomina ruta más corta uno a uno y se utiliza, por ejemplo, en sistemas de navegación para automóviles. Otras aplicaciones incluyen la correspondencia de trazas GPS con segmentos de carretera y la aceleración de simuladores de tráfico que deben considerar las rutas probables tomadas por todos los conductores en una red. En la predicción de rutas, se intenta estimar hacia dónde se dirige probablemente un vehículo calculando qué tan bien coinciden sus posiciones actual y pasada con la ruta más corta desde su punto de partida a cualquier destino posible. Esto se puede hacer de manera eficiente utilizando CH. ^{[ 2 ]}

En escenarios de uno a muchos , un nodo inicial${\displaystyle s}$y un conjunto de nodos objetivo${\displaystyle T}$se dan y la distancia${\displaystyle \mathrm {dist} (s,t)}$a pesar de${\displaystyle t\in T}$debe calcularse. La aplicación más destacada para las consultas de uno a muchos son las búsquedas de puntos de interés. 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 ruta más corta de muchos a muchos , un conjunto de nodos iniciales${\displaystyle S}$y un conjunto de nodos objetivo${\displaystyle T}$se dan y la distancia${\displaystyle \mathrm {dist} (s_{i},t_{i})}$a pesar de${\displaystyle (s_{i},t_{j})\in S\times T}$debe calcularse. Esto se utiliza, por ejemplo, en aplicaciones logísticas. ^{[ 2 ]} Los CH se pueden extender a consultas de muchos a muchos de la siguiente manera. Primero, realice una búsqueda hacia atrás y hacia arriba desde cada${\displaystyle t_{j}\in T}$. Para cada vértice${\displaystyle u}$escaneado durante esta búsqueda, uno de los almacenes${\displaystyle \mathrm {dist} (t_{j},u)}$en un cubo${\displaystyle \beta (u)}$. Luego, se realiza una búsqueda ascendente hacia adelante desde cada${\displaystyle s_{i}\in S}$, comprobando para cada cubo no vacío, si la ruta sobre el vértice correspondiente mejora alguna distancia óptima. Es decir, si${\displaystyle \mathrm {dist} (s_{i},u)+\mathrm {dist} (u,t_{j})<\mathrm {dist} (s_{i},t_{j})}$para cualquier${\displaystyle (s_{i},t_{j})\in S\times T}$. ^{[ 2 ] [ 3 ]}

Algunas aplicaciones incluso requieren cálculos de uno a todos , es decir, encontrar las distancias desde un vértice de origen.${\displaystyle s}$a todos los demás vértices del grafo. Como el algoritmo de Dijkstra visita cada arista 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 en cuanto a caché debido a su mala localidad. Se pueden utilizar CH para una implementación más óptima en cuanto a caché. Para ello, una búsqueda ascendente hacia adelante desde${\displaystyle s}$A continuación, se realiza un escaneo descendente de todos los nodos en el grafo enriquecido con atajos. Esta ú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. ^{[ 12 ]} Nótese que esto es posible porque el orden en que se procesan los nodos en la segunda fase es independiente del nodo de origen.${\displaystyle s}$. ^{[ 2 ]}

En producción, los sistemas de navegación para automóviles deben poder calcular las rutas de viaje más rápidas utilizando información de tráfico prevista y mostrar rutas alternativas. Ambas funciones se pueden realizar utilizando CH. ^{[ 2 ]} La primera se denomina enrutamiento con redes dependientes del tiempo, donde el tiempo de viaje de un enlace dado ya no es constante, sino que depende de la hora del día en que se ingresa al enlace. Las rutas alternativas deben parecer fluidas, ser significativamente diferentes de la ruta más corta, pero no significativamente más largas. ^{[ 2 ]}

Los CH se pueden extender para optimizar múltiples métricas al mismo tiempo; esto se denomina planificación de rutas multicriterio . Por ejemplo, se podría minimizar tanto el costo como el tiempo de viaje. Otro ejemplo son los vehículos eléctricos, para los cuales la carga disponible de la batería limita las rutas válidas, ya que la batería no puede agotarse por completo. ^{[ 2 ]}

Se han establecido varios límites en el preprocesamiento y el rendimiento de las consultas de las jerarquías de contracción. En lo siguiente,${\displaystyle n}$sea ​​el número de vértices en el grafo,${\displaystyle m}$el número de aristas,${\displaystyle h}$la dimensión de la autopista ,${\displaystyle D}$el diámetro del gráfico,${\displaystyle td}$es la profundidad del árbol y${\displaystyle tw}$es el ancho del árbol .

El primer análisis del rendimiento de la jerarquía de contracción se basa en parte en una magnitud conocida como dimensión de autopista . Si bien la definición de esta magnitud es técnica, intuitivamente un grafo tiene una dimensión de autopista pequeña si para cada${\displaystyle r>0}$Hay un conjunto disperso de vértices.${\displaystyle S_{r}}$de tal manera que cada camino más corto de longitud mayor que${\displaystyle r}$incluye un vértice de${\displaystyle S_{r}}$Calcular el valor exacto de la dimensión de la autopista es NP-difícil ^{[ 13 ] [ 14 ]} y muy probablemente W[1]-difícil , ^{[ 15 ]} pero para las cuadrículas se sabe que la dimensión de la autopista es${\displaystyle h\in \Theta ({\sqrt {n}})}$. ^{[ 16 ]}

Se presentó un análisis alternativo en la línea de trabajo de Jerarquía de contracción personalizable. Los tiempos de ejecución de las consultas pueden estar limitados por${\displaystyle O(td^{2})}$. Dado que la profundidad del árbol puede estar limitada en términos del ancho del árbol,${\displaystyle O((tw\log n)^{2})}$También es un límite superior válido. La fuente principal es ^{[ 17 ]} , pero las consecuencias para los tiempos de ejecución en el peor de los casos se detallan mejor en ^{[ 18 ] .}