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

Question

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

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

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

Gracias

---

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

---

A la derecha, el algoritmo A * encuentra el menor costo o la ruta 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 una ruta donde los nodos ponderados tienen un valor determinado. no1.

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

- a menos que esté equivocado e incomprendido A *

Entonces, ¿qué es mejor que ACO?

---

Realmente parece un espectáculo entre ACO y A *, ha habido mucha conversación positiva acerca de A *, sin duda voy a profundizar en ello.

Primero en respuesta a David; Puedo ejecutar la simulación ACO en segundo plano y encontrar el mejor camino, así que sí, hay un costo de inicio inicial, pero afortunadamente el inicio 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 * será capaz de hacer esto con bastante facilidad. Ahora, ¿qué sucede cuando esta red se vuelve terriblemente grande como en millones de nodos? ¿Podrá A * escalar fácilmente?

Investigaré A * más a fondo. ¡Pero te dejo una última pregunta!

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

Answer 1

Notas generales

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

Ante una función de costo cambiante, Dijksta requiere uno para volver a calcular la solución.

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

Optimización de colonias de hormigas , por otro lado, parece ser mucho más flexible para adaptarse a un cambio función de costo, al continuar la iteración después / mientras la función de costo cambia.

Eficiencia

Esto depende mucho de su dominio problemático. Si tiene una buena heurística (consulte la sección Complejidad del artículo A * ) y rara vez los cambios en los costos, entonces el tiempo de ejecución polinomial de A * podría favorecer los repetidos cálculos. ACO, por otro lado, tiene que repetir 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 retiene dentro del estado del algoritmo. ACO no promete la solución óptima, aunque probablemente tiene costos de inicio más altos antes de converger en un " bueno " solución. Una vez más, eso depende en gran medida de su dominio específico, gráfico y función de costo, así como de sus requisitos de optimalidad.

Answer 2

Con A *, el costo de la ruta no necesita ser constante, por lo que puede 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 A-C ya que A-B-C es 2, mientras que A-C 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

donde

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 se agregan usuarios al sistema, la ruta AC será más costosa que ABC a los veinte usuarios (1 + 20/10) = 3, ABC es 2. A medida que los usuarios se eliminan del sistema, la ruta AC se convertirá en La mejor opción otra vez.

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

Answer 3

El algoritmo más utilizado para este problema es A * (Una estrella) , que es una algoritmo de Dijkstra generalizada con heurística adicional: el objetivo de la heurística es dirigir la búsqueda hacia el objetivo de búsqueda para que las búsquedas típicas terminen 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ía ser un buen punto de partida.

Answer 4

Definitivamente A *. A * encontrará la mejor ruta posible o ninguna ruta si no existe una ruta. P.ej. la ruta de este barco se ha calculado utilizando A *

_{(fuente: cokeandcode.com )}

Aquí hay una Demostración de Java interactiva para jugar. Tenga en cuenta que este algoritmo se ralentiza con el modo de espera, por lo que puede verlo ejecutarse. Sin esta desaceleración, encontraría la ruta 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 yf es la suma de ambos (es una conjetura para la ruta completa). A * mantiene dos listas, la lista Abierta y la Cerrada. La lista Abrir contiene todos los nodos que no se han explorado hasta ahora. La lista Cerrado todos los nodos que se han explorado. Un nodo cuenta como explorado si el algoritmo ya ha probado todos los nodos conectados a este nodo (conectado solo podría significar horizontal y verticalmente, pero también diagonal si se permiten movimientos diagonales entre nodos).

El algoritmo podría describirse como

1. Sea P el punto de partida
2. Asigna los valores de g, h y f 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 abierta (mejor == valor f más bajo)
   • Si B es el nodo objetivo - > dejar de fumar, encontraste el camino
   • Si la lista Abrir está vacía, > salir, no existe una ruta
5. Sea C un nodo válido conectado a B
   • Asignar g, h y f a C
   • Compruebe 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í, actualice la ruta
     • De lo contrario, agregue C a la Lista abierta
   • Repita el paso 5 para todos los nodos conectados a B
6. Agregar B a la lista Cerrada (exploramos todos los vecinos)
7. Repita desde el paso 4.

También vea Wikipedia para obtener detalles de la implementación.

Answer 5

He oído hablar de una implementación NN para manejar este tipo de problema también. Así que si quieres usar NN, eventualmente encontrarás tu camino ;-) pero deben ser inferiores en comparación con los "algoritmos genéticos".

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

Los

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

Answer 6

¿Un Dijkstra común no sería suficiente?

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

Answer 7

Algoritmo Dijkstras, pequeño ejemplo para ti

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")