Quel est le moyen le plus efficace de trouver un chemin à travers un petit graphique du monde?

Remarques générales

De l'algorithme de Dijkstra et optimisé variante* trouver le chemin avec "le" coût minimal par le biais de votre graphique. Les choses importantes sont: a) de la définition de votre graphique correctement et b) de la définition appropriée de la fonction de coût.

Face à une évolution de la fonction de coût Dijksta nécessite un re-calcul de la solution.

Pour l'équilibrage de charge, je voudrais étendre Dikstra non seulement de calculer le chemin optimal, mais l'utilisation de certains type d'inondation de remplissage de comportement afin de créer un ensemble de chemins possibles (triés par coût) pour trouver des solutions de rechange. Seulement des connaissances sur le problème spécifique de la fonction de coût peut répondre si et comment cela pourrait fonctionner.

Ant Colony Optimisation d'autre part semble être beaucoup plus souple pour s'adapter à l'évolution de la fonction de coût, par la poursuite de l'itération après/pendant que la fonction de coût des modifications.

L'efficacité

Cela dépend beaucoup de votre problème de domaine. Si vous avez une bonne heuristique (voir la La complexité de la section de l'article) et rarement des coûts les modifications, puis Un " * " polynôme d'exécution peut favoriser répétés des calculs. L'ACO a en revanche pour parcourir encore et encore avant de converger sur une solution approximative. Si le coût des changements se produisent très souvent, la poursuite de l'itération à un taux constant pourrait être plus efficace que la mise à jour de la Une solution, étant donné que l'information est conservée dans l'état de l'algorithme. L'ACO n'a pas de promesse la solution optimale, si et probablement a le plus de coûts de démarrage avant de converger sur une "bonne" solution. Encore que beaucoup dépend de votre domaine spécifique, graphique et la fonction de coût ainsi que vos exigences sur l'optimalité.

OriginalL'auteur David Schmitt

Les plus couramment utilisés algorithme pour résoudre ce problème est * (Une Étoile), qui est généralisée L'algorithme de Dijkstra de recherche avec l'ajout des heuristiques le but de l'heuristique est de diriger la recherche vers la recherche de l'objectif typique de recherches en finir plus vite.

Cet algorithme a de nombreuses variantes, dérivé versions et améliorations, de recherche de Google ou la page Wikipédia devrait être un bon point de départ.

OriginalL'auteur Suma

J'ai entendu parler d'un NN mise en œuvre pour gérer ce genre de problème. Donc, si vous voulez utiliser NNs finalement, vous trouverez votre chemin 😉 mais ils doivent être inférieurs par rapport à "algorithmes génétiques".

Si le calcul de l'/le temps de la consommation est un problème, je vous suggère fortement d'utiliser les algorithmes génétiques. C'est exactement le type de problèmes qu'ils sont exceptionnels.

Gaz sont basées sur une fonction qui décrit votre satisfaction pour toute solution. Vous pouvez modifier cette fonction pour répondre à vos besoins (ie. vous pouvez inclure non seulement le coût de chemin, mais n'importe quel facteur vous le souhaitez).

OriginalL'auteur

Dijkstras algorithme, petit exemple pour vous

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")

OriginalL'auteur