Siempre me ha intrigado el enrutamiento de mapas, pero nunca encontré ningún buen tutorial introductorio (¡o incluso avanzado!) Sobre él. ¿Alguien tiene punteros, consejos, etc.?¿Ruteo del mapa, a la Google Maps?
Actualización: Estoy buscando principalmente indicadores sobre cómo se implementa un sistema de mapas (estructuras de datos, algoritmos, etc.).
Observe cómo se aborda este tipo de cosas en un proyecto de software verdaderamente gratuito utilizando solo datos proporcionados por el usuario y con licencia y tiene un wiki containing stuff you might find interesting.
Hace unos años, los muchachos involucrados eran bastante tranquilos y respondían muchas preguntas, así que no veo ninguna razón por la que todavía no sean un buen grupo.
En lugar de aprender las API para cada proveedor de servicio de mapas (como Gmaps, Ymaps API) Su buena para aprender Mapstraction
"Mapstraction es una biblioteca que proporciona una API común para varias APIs de mapeo javascript"
I Sugeriría que vaya a la URL y aprenda una API general. Hay una buena cantidad de How-Tos también.
¿Por enrutamiento de mapa, quiere decir encontrar el camino más corto a lo largo de una red de calles?
El algoritmo de ruta más corta de Dijkstra es el más conocido. Wikipedia no tiene una mala introducción: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Hay un applet de Java aquí donde puedes verlo en acción: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html y Google te lleva al código fuente en cualquier idioma.
Cualquier aplicación real para la generación de rutas de conducción incluirá un poco de datos sobre la red de calles que describe el asociado costos con los enlaces que atraviesan y jerarquía de la red nodos de carretera, velocidad media, la prioridad de intersección, la vinculación de señales de tráfico, giros prohibidos, etc. .
todavía tengo que encontrar un buen tutorial sobre el enrutamiento, pero hay un montón de código para leer:
hay aplicaciones de enrutamiento GPL que utilizan datos de OpenStreetMap, por ejemplo, Gosmore que funciona en Windows (+ móvil) y Linux. Hay una serie de aplicaciones interesantes que usan la misma información, pero gosmore tiene algunos usos geniales e.g. interface with websites.
El mayor problema con el enrutamiento son los datos incorrectos, y nunca se obtienen datos lo suficientemente buenos. Entonces, si quiere probarlo, mantenga su prueba muy local para que pueda controlar mejor los datos.
Barry Brumitt, uno de los ingenieros de los mapas de Google característica de búsqueda de rutas, ha escrito una entrada en el tema que pueda ser de su interés:
The road to better path-finding 11/06/2007 03:47:00 PM
A * está mucho más cerca de los algoritmos de mapeo de producción. Requiere bastante menos exploración en comparación con el algoritmo original de Dijikstra.
En realidad, D * modificado es lo que generalmente se usa hasta donde yo sé. – mmcdole
Desde un punto de vista conceptual, imagine tirar una piedra en un estanque y observar las ondas. Las rutas representarían el estanque y la piedra su posición inicial.
Por supuesto, el algoritmo debería buscar alguna proporción de n^2 rutas a medida que aumenta la distancia n. Usted tomaría la posición inicial y verificaría todos los caminos disponibles desde ese punto. Luego, recursivamente, pida los puntos al final de esos caminos, etc.
Puede aumentar el rendimiento, al no hacer doble respaldo en una ruta, al no volver a verificar las rutas en un punto si ya se ha cubierto y al renunciar a las rutas que llevan demasiado tiempo.
Una forma alternativa es utilizar el enfoque de feromonas de hormigas, donde las hormigas se arrastran aleatoriamente desde un punto de inicio y dejan un rastro de olor, que acumula el mayor número de hormigas que cruzan una ruta determinada. Si envía (suficientes) hormigas desde el punto de inicio y el punto final, finalmente la ruta con el aroma más fuerte será la más corta. Esto se debe a que el camino más corto se habrá visitado más veces en un período de tiempo determinado, dado que las hormigas caminan a un ritmo uniforme.
EDITAR @ Spikie
Como explicación más detallada de cómo implementar el algoritmo de estanque - estructuras de datos necesarios potenciales se destacan:
Tendrá que guardar el mapa como una red. Esto es simplemente un conjunto de nodes y edges entre ellos. Un conjunto de nodes constituye un route. Un borde une dos nodos (posiblemente ambos del mismo nodo) y tiene un cost asociado, como distance o time para atravesar el borde. Un borde puede ser bidireccional o unidireccional. Probablemente, lo más simple es tener unidireccionales y duplicar para un viaje de dos vías entre nodos (es decir, un borde de A a B y uno diferente para B y A).
Por ejemplo, imagine tres estaciones de ferrocarril dispuestas en un triángulo equilátero apuntando hacia arriba. También hay otras tres estaciones a medio camino entre ellos. Los bordes unen todas las estaciones adyacentes, el diagrama final tendrá un triángulo invertido dentro del triángulo más grande.
Nodos de etiquetas comenzando desde la esquina inferior izquierda, yendo de izquierda a derecha y arriba, como A, B, C, D, E, F (F en la parte superior).
Supongamos que los bordes se pueden atravesar en cualquier dirección. Cada borde tiene un costo de 1 km.
Ok, por lo que deseamos pasar de la parte inferior izquierda A a la estación superior F. Hay muchas rutas posibles, incluidas las que se duplican, p. Ej. ABCEBDEF.
Tenemos una rutina decir, NextNode, que acepta un node y un cost y se llama a sí mismo para cada nodo que puede viajar.
Claramente, si permitimos que esta rutina se ejecute, eventualmente descubrirá todas las rutas, incluidas las que son potencialmente de una longitud infinita (por ejemplo, ABABABAB, etc.). Detendemos que esto suceda al verificar en el cost. Cada vez que visitamos un nodo que no ha sido visitado anteriormente, colocamos tanto el costo como el nodo del que venimos contra ese nodo. Si se ha visitado un nodo antes de verificar el costo existente y si somos más baratos, actualizamos el nodo y continuamos (recursión). Si somos más caros, salteamos el nodo. Si se omiten todos los nodos, salimos de la rutina.
Si alcanzamos nuestro nodo objetivo, también salimos de la rutina.
De esta manera se verifican todas las rutas viables, pero crucialmente solo las de menor costo. Al final del proceso, cada nodo tendrá el costo más bajo para llegar a ese nodo, incluido nuestro nodo objetivo.
Para obtener la ruta trabajamos hacia atrás desde nuestro nodo de destino. Como almacenamos el nodo del que venimos junto con el costo, simplemente saltamos hacia atrás para construir la ruta. Para nuestro ejemplo podríamos terminar con algo como:
nodo A - (Total) Costo 0 - Desde el nodo Ninguno
Nodo B - Costo 1 - Desde el nodo A
nodo C - Costo 2 - Desde el Nodo B
Nodo D - Coste 1 - Del nodo A
Nodo E - Costo 2 - Desde el nodo D/Costo 2 - Desde el nodo B (esta es una excepción ya que hay un costo igual)
Nodo F - Costo 2 - Desde el nodo D
Así que la ruta más corta es ADF.
@ jonathan, por favor, puede dar detalles del algoritmo de piedra en el estanque y cómo puedo aplicarlo en un mapa.Digamos que estoy en un punto y quiero buscar en onda expansiva antes de pasar a la siguiente ondulación externa. y amigo lo sé y 2 años tarde a la conversación – Spikie
Se me ocurre otra idea sobre el costo de cada recorrido, pero aumentaría el tiempo y la potencia de procesamiento necesarios para calcular.
Ejemplo: Hay 3 maneras en que puedo tomar (donde vivo) para ir del punto A al B, según GoogleMaps. Las unidades Garmin ofrecen cada una de estas 3 rutas en el cálculo de la ruta Quickest. Después de recorrer cada una de estas rutas muchas veces y promediar (obviamente habrá errores dependiendo de la hora del día, la cantidad de cafeína, etc.), creo que los algoritmos podrían tener en cuenta el número de curvas en el camino para un alto nivel de precisión. , por ejemplocarretera recta de 1 milla será más rápido que una carretera de 1 milla con curvas pronunciadas. No es una sugerencia práctica, pero ciertamente una que utilizo para mejorar el conjunto de resultados de mi viaje diario al trabajo.
Desde mi experiencia trabajando en este campo, A * hace el trabajo muy bien. Es (como se mencionó anteriormente) más rápido que el algoritmo de Dijkstra, pero aún es lo suficientemente simple para que un programador ordinariamente competente lo implemente y comprenda.
La construcción de la red de rutas es la parte más difícil, pero se puede dividir en una serie de pasos simples: obtener todas las carreteras; ordenar los puntos en orden; hacer grupos de puntos idénticos en diferentes caminos en intersecciones (nodos); agregue arcos en ambas direcciones donde los nodos se conectan (o en una dirección solo para una carretera de sentido único).
El algoritmo A * en sí es well documented on Wikipedia. El lugar clave para optimizar es la selección del mejor nodo de la lista abierta, para lo cual necesita una cola de prioridad de alto rendimiento. Si está usando C++, puede usar el adaptador de prioridad de STL.
Personalizar el algoritmo para enrutar diferentes partes de la red (por ejemplo, peatones, automóviles, transporte público, etc.) de la velocidad, la distancia u otros criterios es bastante fácil. Esto se hace escribiendo filtros para controlar qué segmentos de ruta están disponibles, cuándo construir la red y qué peso se asigna a cada uno.
Los mapas son generalmente demasiado grandes para permitir los algoritmos estándar de ruta más corta, tendrás que construir algunas heurísticas para seleccionar un subgráfico. Además, puede utilizar enfoques heurísticos completamente diferentes (por ejemplo, autopistas primero ...) para encontrar una ruta. –