Algoritmo para determinar la ruta más rápida?

17

Digamos que vamos del 1 al 5. La ruta más corta será 1-4-3-5 (total: 60 km).

Grafico

Podemos usar el algoritmo de Dijkstra para hacer eso.

Ahora el problema es que la ruta más corta no siempre es la más rápida debido a los atascos de tráfico u otros factores.

Por ejemplo:

  • Se sabe que 1-2 tiene atascos frecuentes, por lo que debe evitarse.
  • De repente, se produce un accidente automovilístico a lo largo de 4-3, por lo que también debe evitarse.
  • Etc ...

Entonces, probablemente podamos acelerar en la ruta 1-4-5, debido a que no hay atascos / accidentes, por lo que llegaremos a 5 más rápido.

Bueno, esa es la idea general, y aún no he pensado en más detalles.

¿Hay algún algoritmo para resolver este problema?

graph dijkstra anta40
fuente
3
¿Es esta tarea? ¿No es esto solo en.wikipedia.org/wiki/Travelling_salesman_problem para atravesar un gráfico ponderado?
StuperUser
9
@StuperUser: No, TSP es un circuito de todos los nodos sin duplicados. En el caso de muestra, no es necesario golpear el nodo 2, por ejemplo.
David Thornley
2
@DavidThornley ya veo. Entonces, ¿Dijkstra es la ruta más corta en un gráfico ponderado? ¿Y TSP es transversal visitando cada nodo?
StuperUser
1
@Stuper: El recorrido más corto, sí
BlueRaja - Danny Pflughoeft
2
@StuperUser, solo para su información, TSP es un problema fuertemente NP-completo sin solución que pueda ejecutarse en tiempo polinómico. ... Entonces ya lo sabes.
Riwalk

Respuestas:

5

Dado que trajiste congestión en la imagen, ten cuidado de que no te atrape la paradoja de Braess . Si todos eligen el camino óptimo, el tiempo de viaje es peor para todos.

Michael Brown
fuente
49

Sí: Dijkstra

Dijkstra funciona igual de bien para esta situación.
Simplemente usa el tiempo en lugar de la distancia como el peso de cada arco.

Martin York
fuente
9
Por lo general, la 'distancia' en Dijkstra se ponderaría para todo tipo de cosas, costo / peajes, preferencia de autopista, límites de velocidad: usar solo la distancia es solo el enfoque más simple. Esto es lo que hace que el algoritmo sea tan inteligente
Martin Beckett
66
Aunque Dijsktra lo hará, generalmente elegiría A * para cualquier trabajo serio de búsqueda de caminos; La heurística ayudará mucho.
Mircea Chirea
66
Enlace: A * algoritmo de búsqueda . Es una extensión del método de Dijkstra.
mgkrebbs
Mientras haya una heurística aplicable, A * será superior a la de Dijkstra (en términos de rendimiento).
bummzack
Una heurística admisible sería algo difícil de encontrar aquí teniendo en cuenta que parece que tenemos en cuenta muchos factores (como los atascos de tráfico).
pwny
16

Si. El algoritmo de Dijkstra resolverá este problema.

El problema en su caso es que automáticamente asume que la ruta más corta equivale a la distancia recorrida, cuando en realidad equivale más apropiadamente al COSTO de tomar una ruta.

Si una ruta tiene un obstáculo, su COSTE debería ser mayor, y el algoritmo aún se aplica.

árbol de arce
fuente
Sí, lo siento si no usé la redacción correcta. Lo que quiero decir es la 'ruta más conveniente' (costo mínimo más
grande
11

Debería poder reemplazar su distancia con el tiempo entre nodos y resolverla de la misma manera.

DKnight
fuente
10

Dijkstra

Como se dijo antes, no solo se usa para la distancia más corta. Creo que esta animación da una buena comprensión del "poder" (a falta de una palabra mejor) de Dijkstra:

Dijkstra

Dinámica
fuente