venceras vecino triangulo saber puntos punto programa problema más mas esta dentro como cercanos cercano algorithm routing mapping

algorithm - vecino - problema del par de puntos más cercanos



¿Qué algoritmos calculan las direcciones del punto A al punto B en un mapa? (18)

Los algoritmos de gráficos como el algoritmo de Dijkstra no funcionarán porque el gráfico es enorme.

Este argumento no se mantiene necesariamente porque Dijkstra no suele ver el gráfico completo, sino un subconjunto muy pequeño (cuanto más interconectado esté el gráfico, más pequeño será este subconjunto).

Dijkstra puede funcionar bastante bien para gráficos de buen comportamiento. Por otro lado, con una cuidadosa parametrización, A * siempre funcionará igual de bien o mejor. ¿Ya has probado cómo funcionaría en tus datos?

Dicho esto, también me interesaría mucho escuchar las experiencias de otras personas. Por supuesto, ejemplos destacados como la búsqueda en Google Map son particularmente interesantes. Podía imaginar algo así como una heurística dirigida al vecino más cercano.

¿Cómo sugieren las direcciones los proveedores de mapas (como Google o Yahoo! Maps)?

Quiero decir, es probable que tengan datos del mundo real de alguna forma, que ciertamente incluyan distancias, pero también quizás cosas como la velocidad de conducción, la presencia de aceras, los horarios de los trenes, etc. Con aristas de pesos reflejando distancias. Quiero poder calcular rápidamente las direcciones de un punto arbitrario a otro. A veces, estos puntos estarán juntos (dentro de una ciudad), mientras que a veces estarán muy alejados (a través del país).

Los algoritmos de gráficos como el algoritmo de Dijkstra no funcionarán porque el gráfico es enorme. Por suerte, los algoritmos heurísticos como A * probablemente funcionarán. Sin embargo, nuestros datos están muy estructurados, ¿y quizás algún tipo de enfoque por niveles podría funcionar? (Por ejemplo, almacene direcciones precomputadas entre ciertos puntos "clave" muy alejados, así como algunas direcciones locales. Luego, las direcciones para dos puntos lejanos implicarán direcciones locales a puntos clave, direcciones globales a otro punto clave y luego direcciones locales). direcciones de nuevo.)

¿Qué algoritmos se utilizan realmente en la práctica?

PD. Esta pregunta fue motivada por encontrar peculiaridades en las direcciones de mapeo en línea. Contrariamente a la desigualdad del triángulo, a veces Google Maps cree que X-Z toma más tiempo y está más lejos que usar un punto intermedio como en X-Y-Z . Pero tal vez sus direcciones de caminar se optimizan para otro parámetro, también?

PPS. Aquí hay otra violación de la desigualdad del triángulo que sugiere (para mí) que utilizan algún tipo de enfoque por niveles: X-Z versus X-Y-Z . El primero parece usar el prominente Boulevard de Sebastopol, aunque está un poco apartado.

Edición : ninguno de estos ejemplos parece funcionar más, pero ambos lo hicieron en el momento de la publicación original.

Al abordar las violaciones de la desigualdad en el triángulo, es de esperar que el factor adicional por el que están optimizando es el sentido común. No necesariamente quieres la ruta más corta o rápida, ya que puede llevar al chaos and destruction . Si desea que sus instrucciones prefieran las rutas principales que son aptas para camiones y puede hacer frente a que se les envíen todos los controladores de navegación por satélite, descartará rápidamente la desigualdad del triángulo [1].

Si Y es una calle residencial estrecha entre X y Z, probablemente solo desee utilizar el acceso directo a través de Y si el usuario solicita explícitamente XYZ. Si piden XZ, deberían apegarse a las carreteras principales, incluso si están un poco más lejos y tardan un poco más. Es similar a la paradoja de Braess : si todos intentan tomar la ruta más corta y rápida, la congestión resultante significa que ya no es la ruta más rápida para nadie. Desde aquí nos desviamos de la teoría de grafos a la teoría de juegos.

[1] De hecho, cualquier esperanza de que las distancias producidas sean una función de distancia en el sentido matemático se muere cuando se permiten caminos de un solo sentido y se pierde el requisito de simetría. Perder la desigualdad del triángulo también es simplemente frotar sal en la herida.

El estado actual de la técnica en términos de tiempos de consulta para redes de carreteras estáticas es el algoritmo de etiquetado de Hub propuesto por Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Recientemente se publicó una encuesta a través y excelentemente escrita del campo como informe técnico de Microsoft http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

La versión corta es ...

El algoritmo de etiquetado del concentrador proporciona las consultas más rápidas para las redes de carreteras estáticas, pero requiere una gran cantidad de ram para ejecutarse (18 GiB).

El enrutamiento de los nodos de Transit es ligeramente más lento, aunque solo requiere alrededor de 2 GiB de memoria y tiene un tiempo de preprocesamiento más rápido.

Las jerarquías de contracción proporcionan un buen intercambio entre los tiempos de preprocesamiento rápidos, los bajos requisitos de espacio (0,4 GiB) y los tiempos de consulta rápidos.

Ningún algoritmo está completamente dominado ...

Esta charla de Google sobre tecnología por Peter Sanders puede ser de interés.

https://www.youtube.com/watch?v=-0ErpE8tQbw

También esta charla de Andrew Goldberg.

https://www.youtube.com/watch?v=WPrkc78XLhw

Una implementación de código abierto de jerarquías de contracción está disponible en el sitio web del grupo de investigación Peter Sanders en KIT. http://algo2.iti.kit.edu/english/routeplanning.php

También una publicación de blog fácilmente accesible escrita por Microsoft sobre el uso del algoritmo CRP ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

Esta pregunta ha sido un área activa de investigación en los últimos años. La idea principal es hacer un preprocesamiento en el gráfico una vez , para acelerar todas las consultas siguientes . Con esta información adicional los itinerarios pueden ser calculados muy rápido. Aún así, el algoritmo de Dijkstra es la base para todas las optimizaciones.

Arachnid describió el uso de la búsqueda bidireccional y la poda de bordes basada en información jerárquica. Estas técnicas de aceleración funcionan bastante bien, pero los algoritmos más recientes superan a estas técnicas por todos los medios. Con los algoritmos actuales, las rutas más cortas se pueden calcular en mucho menos tiempo que un milisegundo en una red de carreteras continental. Una implementación rápida del algoritmo no modificado de Dijkstra necesita aproximadamente 10 segundos .

El artículo Ingeniería de algoritmos de planificación de rutas rápidas ofrece una visión general del progreso de la investigación en ese campo. Ver las referencias de ese documento para más información.

Los algoritmos conocidos más rápidos no utilizan información sobre el estado jerárquico de la carretera en los datos, es decir, si es una carretera o una carretera local. En su lugar, calculan en una etapa de preprocesamiento una jerarquía propia que se optimiza para acelerar la planificación de rutas. Esta precomputación se puede usar para eliminar la búsqueda: lejos del inicio y del destino, las carreteras lentas no deben considerarse durante el algoritmo de Dijkstra. Los beneficios son muy buen rendimiento y una garantía de corrección para el resultado.

Los primeros algoritmos de planificación de rutas optimizados se ocupan solo de las redes de carreteras estáticas, lo que significa que una ventaja en el gráfico tiene un valor de costo fijo. Esto no es cierto en la práctica, ya que queremos tener en cuenta información dinámica como los atascos de tráfico o las restricciones dependientes del vehículo. Los últimos algoritmos también pueden lidiar con estos problemas, pero todavía hay problemas por resolver y la investigación continúa.

Si necesita las distancias de ruta más cortas para calcular una solución para el TSP , entonces probablemente esté interesado en matrices que contengan todas las distancias entre sus fuentes y destinos. Para esto, podría considerar la posibilidad de calcular las rutas más cortas de muchas a muchas utilizando las jerarquías de carreteras . Tenga en cuenta que esto se ha mejorado con nuevos enfoques en los últimos 2 años.

Esto es pura especulación de mi parte, pero supongo que pueden usar una estructura de datos del mapa de influencia que se superpone al mapa dirigido para restringir el dominio de búsqueda. Esto permitiría que el algoritmo de búsqueda dirija la ruta a las rutas principales cuando el viaje deseado sea largo.

Dado que se trata de una aplicación de Google, también es razonable suponer que gran parte de la magia se realiza mediante el almacenamiento en caché extenso. :) No me sorprendería si el caché del 5% más común de las solicitudes de ruta de Google Map permitiera una gran parte (20%? ¿50%?) De solicitudes que se respondan con una simple búsqueda.

Estoy un poco sorprendido de no ver el algoritmo de Floyd Warshall mencionado aquí. Este algoritmo funciona muy parecido al de Dijkstra. También tiene una característica muy agradable que le permite calcular siempre y cuando quiera continuar permitiendo más vértices intermedios. Así que, naturalmente, encontrará las rutas que usan autopistas interestatales o carreteras con bastante rapidez.

Hablando como alguien que pasó 18 meses trabajando en una compañía de mapas, que incluyó trabajar en el algoritmo de enrutamiento ... sí, Dijkstra''s funciona, con un par de modificaciones:

  • En lugar de hacer una vez de Dijkstra''s desde la fuente hasta el destino, comienzas en cada extremo y expandes ambos lados hasta que se encuentran en el medio. Esto elimina aproximadamente la mitad del trabajo (2 * pi * (r / 2) ^ 2 vs pi * r ^ 2).
  • Para evitar explorar las callejuelas de cada ciudad entre su origen y destino, puede tener varias capas de datos de mapas: una capa de ''autopistas'' que contiene solo autopistas, una capa ''secundaria'' que contiene solo calles secundarias, etc. Luego, solo explora secciones más pequeñas de las capas más detalladas, expandiéndose según sea necesario. Obviamente, esta descripción deja muchos detalles, pero entiendes la idea.

Con modificaciones a lo largo de esas líneas, puede hacer incluso enrutamiento a través del país en un período de tiempo muy razonable.

Hablando de GraphHopper , un rápido planificador de rutas de código abierto basado en OpenStreetMap, he leído un poco de literatura e implementado algunos métodos. La solución más simple es una Dijkstra y una mejora simple es una Dijkstra bidireccional que explora aproximadamente la mitad de los nodos. Con el Dijkstra bidireccional, una ruta a través de toda Alemania toma ya 1 seg (para el modo de automóvil), en C sería probablemente solo 0.5s o menos;)

He creado un gif animado de una búsqueda de ruta real con Dijkstra bidireccional here . También hay algunas ideas más para hacer que Dijkstra sea más rápido como hacer A *, que es un "Dijkstra orientado a objetivos". También he creado un gif-animation para ello.

¿Pero cómo hacerlo (mucho) más rápido?

El problema es que para una búsqueda de ruta se deben explorar todos los nodos entre las ubicaciones y esto es realmente costoso, ya que en Alemania hay varios millones de ellos. Pero un punto adicional de Dijkstra, etc., es que tales búsquedas utilizan una gran cantidad de RAM.

Existen soluciones heurísticas pero también soluciones exactas que organizan el gráfico (red de carreteras) en capas jerárquicas, ambas tienen ventajas y desventajas y principalmente resuelven la velocidad y el problema de RAM. He enumerado algunos de ellos en esta respuesta .

Para GraphHopper, decidí usar las Jerarquías de Contracción porque es relativamente ''fácil'' de implementar y no demora mucho en la preparación del gráfico. Todavía resulta en tiempos de respuesta muy rápidos, como puede probar en nuestra instancia en línea GraphHopper Maps . Por ejemplo, desde el sur de África hasta el este de China, lo que da como resultado una distancia de 23000 km y casi 14 días de viaje en automóvil para el automóvil y solo tomó ~ 0.1 s en el servidor.

He hecho esto muchas veces, en realidad, probando varios métodos diferentes. Dependiendo del tamaño (geográfico) del mapa, es posible que desee considerar el uso de la función haversine como una heurística.

La mejor solución que he creado es utilizar A * con una distancia en línea recta como función heurística. Pero luego necesitas algún tipo de coordenadas para cada punto (intersección o vértice) en el mapa. También puede probar diferentes ponderaciones para la función heurística, es decir,

f(n) = k*h(n) + g(n)

donde k es una constante mayor que 0.

He trabajado en enrutamiento durante algunos años, con una reciente ráfaga de actividad motivada por las necesidades de mis clientes, y he descubierto que A * es lo suficientemente rápido; Realmente no hay necesidad de buscar optimizaciones o algoritmos más complejos. Enrutar sobre un gráfico enorme no es un problema.

Pero la velocidad depende de tener toda la red de enrutamiento, por lo que me refiero al gráfico dirigido de arcos y nodos que representan segmentos de ruta y cruces, respectivamente, en la memoria. La sobrecarga de tiempo principal es el tiempo necesario para crear esta red. Algunas cifras aproximadas basadas en una computadora portátil normal con Windows y enrutamiento en toda España: tiempo necesario para crear la red: 10-15 segundos; tiempo necesario para calcular una ruta: demasiado corto para medir.

La otra cosa importante es poder reutilizar la red para tantos cálculos de enrutamiento como desee. Si su algoritmo ha marcado los nodos de alguna manera para registrar la mejor ruta (el costo total para el nodo actual y su mejor arco), como debe hacerlo en A *, debe restablecer o borrar esta información anterior. En lugar de pasar por cientos de miles de nodos, es más fácil usar un sistema de números de generación. Marque cada nodo con el número de generación de sus datos; incrementa el número de generación cuando calculas una nueva ruta; cualquier nodo con un número de generación anterior está obsoleto y su información puede ignorarse.

Los mapas nunca toman en consideración todo el mapa. Mi conjetura es: 1. Según su ubicación, cargan un lugar y los puntos de referencia en ese lugar. 2. Cuando busca el destino, es decir, cuando cargan la otra parte del mapa y hacen una gráfica de dos lugares y luego aplican los algoritmos de ruta más corta.

Además, hay una técnica importante La programación dinámica que sospecho se utiliza en el cálculo de las rutas más cortas. Puedes referirte a eso también.

No he trabajado en Google, Microsoft o Yahoo Maps antes, así que no puedo decirte cómo funcionan.

Sin embargo, diseñé un sistema personalizado de optimización de la cadena de suministro para una empresa de energía que incluía una aplicación de programación y enrutamiento para su flota de camiones. Sin embargo, nuestro criterio de enrutamiento fue mucho más específico para el negocio que donde se reduce la construcción o el tráfico o el cierre de carriles.

Empleamos una técnica llamada ACO (optimización de colonias de hormigas) para programar y enrutar camiones. Esta técnica es una técnica de IA que se aplicó al problema del vendedor ambulante para resolver problemas de enrutamiento. El truco con ACO es generar un cálculo de error basado en hechos conocidos del enrutamiento para que el modelo de resolución de gráficos sepa cuándo salir (cuando el error es lo suficientemente pequeño).

Puede buscar en Google ACO o TSP para obtener más información sobre esta técnica. Sin embargo, no he usado ninguna de las herramientas de código abierto de AI para esto, así que no puedo sugerir una (aunque escuché que SWARM fue bastante completo).

Probablemente sea similar a la respuesta en rutas precalculadas entre las ubicaciones principales y los mapas en capas, pero tengo entendido que en los juegos, para acelerar A *, tiene un mapa que es muy tosco para la navegación macro y un mapa detallado para Navegación hasta el límite de las direcciones macro. Por lo tanto, tiene 2 rutas pequeñas para calcular y, por lo tanto, su espacio de búsqueda es mucho más pequeño que simplemente hacer una ruta única hacia el destino. Y si estás en el negocio de hacer esto mucho, tendrías muchos de esos datos precalculados, por lo que al menos parte de la búsqueda es una búsqueda de datos precalculados, en lugar de una búsqueda de una ruta.

Tenía mucha curiosidad acerca de las heurísticas utilizadas, cuando hace un tiempo conseguimos rutas desde el mismo lugar de partida cerca de Santa Rosa, a dos campamentos diferentes en el Parque Nacional Yosemite. Estos diferentes destinos produjeron rutas bastante diferentes (a través de la I-580 o CA-12) a pesar del hecho de que ambas rutas convergieron en las últimas 100 millas (a lo largo de la CA-120) antes de desviarse nuevamente por unas pocas millas al final. Esto fue bastante repetible. Las dos rutas estaban a una distancia de hasta 50 millas por cerca de 100 millas, pero las distancias / tiempos estaban bastante cerca entre sí como era de esperar.

Lamentablemente no puedo reproducir eso, los algoritmos deben haber cambiado. Pero me tenía curiosidad por el algoritmo. Todo lo que puedo especular es que hubo algunas podas direccionales que resultaron ser exquisitamente sensibles a la pequeña diferencia angular entre los destinos vistos desde lejos, o hubo diferentes segmentos precomputados seleccionados por la elección del destino final.

Tuve algunos pensamientos más sobre esto:

1) Recuerda que los mapas representan una organización física. Almacena la latitud / longitud de cada intersección. No necesita verificar mucho más allá de los puntos que se encuentran en la dirección de su objetivo. Solo si te encuentras bloqueado necesitas ir más allá de esto. Si almacena una superposición de conexiones superiores, puede limitarla aún más: normalmente nunca cruzará una de esas de una manera que se aleje de su destino final.

2) Divida el mundo en un conjunto completo de zonas definidas por conectividad limitada, defina todos los puntos de conectividad entre las zonas. Encuentre en qué zonas se encuentran su origen y destino, para la ruta de inicio y final de la zona desde su ubicación hasta cada punto de conexión, para las zonas entre simplemente el mapa entre los puntos de conexión. (Sospecho que muchos de estos últimos ya están precalculados).

Tenga en cuenta que las zonas pueden ser más pequeñas que un área metropolitana. Cualquier ciudad con características de terreno que la dividan (por ejemplo, un río) sería múltiples zonas.

Un algoritmo de ruta más corta de todos los pares calculará las rutas más cortas entre todos los vértices en un gráfico. Esto permitirá que las rutas se calculen previamente en lugar de requerir que se calcule una ruta cada vez que alguien quiera encontrar la ruta más corta entre una fuente y un destino. El algoritmo Floyd-Warshall es un algoritmo de ruta más corta de todos los pares.

Veo lo que pasa con los mapas en el OP:

Mire la ruta con el punto intermedio especificado: la ruta va ligeramente hacia atrás debido a esa carretera que no es recta.

Si su algoritmo no retrocede, no verá la ruta más corta.