algorithm - keywords - ¿Cuál es la forma más eficiente de encontrar un camino a través de un pequeño mundo gráfico?

metodos de clustering

Question

Tengo un mar de nodos ponderados con bordes que unen clusters de nodos. Este gráfico sigue el típico diseño de mundo pequeño.

Deseo encontrar un algoritmo de búsqueda de ruta, que no sea costoso para la potencia del procesador, para encontrar un camino a lo largo de la mejor ruta posible donde los nodos sean los más favorables, la ruta más rápida no es el factor más importante. Este algoritmo también tiene en cuenta la carga y el redireccionamiento del tráfico.

(nota al margen: ¿podrían usarse redes neuronales aquí?)

Gracias

Estoy mirando a ACO . ¿Hay algo mejor que ACO para este tipo de problema?

A la derecha, el algoritmo A * encuentra la ruta menos costosa o más rápida, sin equilibrio de carga.

Digamos que la ruta más rápida o más corta no es la ruta más importante, lo que es más importante es seguir un camino donde los nodos ponderados tienen un cierto valor. no1.

no2. Si usa A *, el tráfico en esa ruta se sobrecarga y repentinamente esa ruta es redundante. Tan genial como A * es, no tiene ciertas características que ACO es el equilibrio de carga inherente.

- a menos que sea equivocado e incomprendido A *

Entonces, ¿qué mejor que ACO?

Realmente se ve como un show entre ACO y A *, ha habido tantas charlas positivas sobre A *, sin duda voy a mirar más de cerca.

Primero en respuesta a David; Puedo ejecutar la simulación de ACO en segundo plano y encontrar la mejor ruta, así que sí, hay un costo inicial de inicio, pero afortunadamente la puesta en marcha no es esencial. Entonces puedo permitirme ejecutar una simulación varias veces. El único problema real es encontrar nodos de origen y destino conectados. Mientras que parece que A * podrá hacer esto con bastante facilidad. Ahora qué sucede cuando esta red se vuelve tremendamente grande como en millones de nodos. ¿A * podrá escalar fácilmente?

Investigaré A * más. ¡Pero los dejo con una última pregunta!

¿Podrá A * ser capaz de escalar tan bien como Antnet (ACO)?

Answer 1

Notas generales

El algoritmo de Dijkstra y la variante optimizada A * encuentran la ruta con "el" costo mínimo a través de su gráfico. Las cosas importantes son a) definir su gráfica correctamente yb) definir una función de costo apropiada.

En vista de una función de costos cambiante, Dijksta necesita uno para volver a calcular la solución.

Para equilibrar la carga, extendería Dikstra no solo para calcular la ruta óptima, sino también para usar algún tipo de comportamiento de inundación y relleno para crear un conjunto de posibles caminos (ordenados por costo) para encontrar alternativas. Solo el conocimiento sobre el problema específico y la función de costo puede responder si esto funcionará y cómo.

Ant Colony Optimization por otro lado parece ser mucho más flexible en la adaptación a una función de costo variable, al continuar la iteración después / mientras cambia la función de costo.

Eficiencia

Esto depende mucho del dominio de tu problema. Si tiene una buena heurística (consulte la sección Complejidad del artículo A * ) y rara vez cuesta cambios, entonces el tiempo de ejecución polinomial de A * podría favorecer la repetición de los cálculos. Por otro lado, ACO tiene que iterar una y otra vez antes de converger en una solución aproximada. Si los cambios de costos ocurren con mucha frecuencia, continuar la iteración a una velocidad constante podría ser más eficiente que actualizar la solución A *, ya que la información se conserva dentro del estado del algoritmo. Sin embargo, ACO no promete la solución óptima y probablemente tenga costos de puesta en marcha más altos antes de converger en una solución "buena". Una vez más, eso depende mucho de su dominio específico, gráfico y función de costos, así como sus requisitos de optimalidad.

Answer 2

Definitivamente A *. A * encontrará la mejor ruta posible o ninguna ruta en absoluto si no existe una ruta. Por ejemplo, la ruta de este barco se ha calculado utilizando A *

A * Ejemplo en Game Map http://www.cokeandcode.com/images/path1.png

Aquí hay una demo de Java interactiva para jugar. Tenga en cuenta que este algoritmo se ralentiza por los sueños, por lo que se ve funcionando. Sin esta ralentización, encontraría el camino en menos de un segundo.

El algoritmo es simple, pero poderoso. Cada nodo tiene 3 valores, g es el costo hasta este nodo. h es el costo estimado de este nodo al objetivo y f es la suma de ambos (es una suposición para la ruta completa). A * mantiene dos listas, la lista Abierta y Cerrada. La lista Abrir contiene todos los nodos que no se han explorado hasta el momento. La lista cerrada enumera todos los nodos que se han explorado. Un nodo cuenta como explorado si el algoritmo ya ha probado cada nodo conectado a este nodo (conectado solo podría significar horizontal y verticalmente, pero también diagonal si se permiten diagonales entre nodos).

El algoritmo podría describirse como

1. Deje que P sea el punto de partida
2. Asigna g, h, y f valores a P
3. Agregue P a la lista abierta (en este punto P es el único nodo en esa lista).
4. Deje que B sea el mejor nodo de la lista Abrir (bist == valor f más bajo)
   • Si B es el nodo objetivo -> salir, encontraste el camino
   • Si la lista Abrir está vacía -> salir, no existe ninguna ruta
5. Deje C ser un nodo válido conectado a B
   • Asigna g, h, y f a C
   • Verifique si C está en la Lista Abierta o Cerrada
     • En caso afirmativo, verifique si la nueva ruta es más eficiente (valor f más bajo)
       • Si es así, actualiza la ruta
     • De lo contrario, agregue C a la Lista Abierta
   • Repita el paso 5 para todos los nodos conectados a B
6. Agregue B a la lista cerrada (exploramos todos los vecinos)
7. Repita desde el paso 4.

También eche un vistazo a Wikipedia para detalles de implementación.

Answer 3

El algoritmo más comúnmente utilizado para este problema es A * (A Star) , que es una búsqueda generalizada de algoritmos de Dijkstra con heurísticas añadidas: el objetivo de la heurística es dirigir la búsqueda hacia el objetivo de búsqueda para que las búsquedas típicas finalicen más rápido.

Este algoritmo tiene muchas variantes, versiones derivadas y mejoras, la búsqueda de Google o la página de Wikipedia deberían ser un buen punto de partida.

Answer 4

También he oído hablar de una implementación de NN para manejar este tipo de problema. Entonces, si quieres usar NN, finalmente encontrarás el camino ;-) pero deben ser inferiores en comparación con los "algoritmos genéticos".

Si el consumo computacional / de tiempo es un problema, sugeriría usar algoritmos genéticos. Este es específicamente el tipo de problemas en los que son excepcionales.

Las GA se basan en una función que describe su satisfacción con cualquier solución dada. Puede modificar esta función para adaptarla a sus necesidades (es decir, puede incluir no solo el costo del camino sino también cualquier factor que desee).

Answer 5

Con A *, el costo de ruta no necesita ser constante, por lo que podría comenzar con el siguiente gráfico:

A---1---B---1---C
|               |
/-------1-------/

donde queremos ir de A a C. Inicialmente, el algoritmo de búsqueda de ruta elegirá la ruta de CA ya que ABC es 2, mientras que AC es 1. Podemos agregar un término adicional a las rutas:

A---r---B---r---C
|               |
/-------r-------/

con

r(NM) = k(NM) + users(NM) / 10

dónde

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

A medida que los usuarios se agregan al sistema, la ruta AC será más costosa que ABC en veinte usuarios (1 + 20/10) = 3, ABC es 2. A medida que los usuarios se eliminen del sistema, la ruta de CA se convertirá en la mejor opción de nuevo.

El poder real de A * es la heurística que usa para calcular el costo de cada conexión.

Answer 6

¿No sería suficiente un Dijkstra común?

http://improve.dk/generic-dijkstras-algorithm/