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

Question

J'ai une mer de nœuds pondérés avec des arêtes reliant des groupes de nœuds. Ce graphique suit la disposition typique d'un petit monde.

Je souhaite trouver un algorithme de recherche de chemin, qui ne coûte pas cher en ressources processeur, pour trouver un chemin le long du meilleur chemin possible où les nœuds sont les mieux pondérés, le chemin le plus rapide n’est pas le facteur le plus important. Cet algorithme prend également en compte la portance et le réacheminement du trafic.

(remarque: les réseaux de neurones pourraient-ils être utilisés ici?)

Merci

Je regarde ACO . Y at-il quelque chose de mieux que ACO pour ce genre de problème?

Droite, l'algorithme A * trouve le coût le plus bas ou itinéraire le plus rapide, sans équilibrage de charge.

Disons que la route la plus rapide ou la plus courte n’est pas la route la plus importante. Le plus important est de suivre un chemin où les nœuds pondérés ont une certaine valeur. no1.

no2. Si vous utilisez A *, le trafic sur cette route est surchargé, puis soudainement, ce chemin devient redondant. Aussi astucieux que soit A *, il n’a pas certaines caractéristiques qui ACO, c’est-à-dire l’équilibrage de charge inhérent.

- sauf si je me trompe et que je comprends mal A *

Alors qu'est-ce qui bat l'ACO?

Cela ressemble vraiment à un spectacle entre ACO et A *, il y a eu tellement de discussions positives sur A *, je vais certainement approfondir la question.

Tout d'abord en réponse à David; Je peux exécuter la simulation ACO dans l’arrière-plan et trouver le meilleur chemin, alors oui, il ya un coût de démarrage initial, mais heureusement, le démarrage n’est pas essentiel. Je peux donc me permettre d’exécuter une simulation plusieurs fois. Le seul problème réel est de trouver des nœuds de source et de destination connectés. Alors qu'il semble que A * sera capable de le faire assez facilement. Maintenant, que se passe-t-il lorsque ce réseau devient terriblement grand, comme dans des millions de nœuds. A * pourra-t-il facilement évoluer?

Je vais rechercher A * plus loin. Mais je vous laisse avec une dernière question!

Est-ce que A * sera en mesure de s’adapter aussi bien qu’Antnet (ACO)?

Answer 1

Notes générales

L'algorithme de Dijkstra et sa variante optimisée A * trouvent le chemin avec " le " coût minimal grâce à votre graphique. Les éléments importants sont a) définir correctement votre graphique et b) définir une fonction de coût appropriée.

Face à une fonction de coût changeante, Dijksta a besoin de recalculer la solution.

Pour l’équilibrage de la charge, je voudrais que Dikstra non seulement calcule le chemin optimal, mais utilise un type de comportement de remplissage pour créer un ensemble de chemins possibles (triés par coût) afin de trouver des alternatives. Seule la connaissance du problème spécifique et de la fonction de coût peut indiquer si et comment cela pourrait fonctionner.

L’optimisation de la colonie de fourmis semble en revanche beaucoup plus souple pour s’adapter à une évolution fonction de coût, en poursuivant l'itération après / pendant que la fonction de coût change.

Efficacité

Cela dépend beaucoup de votre domaine de problème. Si vous avez une bonne heuristique (voir la section Complexity de l'article A * ) et les changements de coûts sont rares, le temps d’exécution polynomial d’A * peut donc favoriser des calculs à nouveau ACO doit quant à lui itérer encore et encore avant de converger vers une solution approximative. Si les changements de coûts se produisent très fréquemment, poursuivre l'itération à un taux constant pourrait s'avérer plus efficace que de mettre à jour la solution A *, car les informations sont conservées dans l'état de l'algorithme. ACO ne promet pas la solution optimale, cependant et probablement a des coûts de démarrage plus élevés avant de converger vers un "bien". Solution. Encore une fois, cela dépend beaucoup de votre domaine spécifique, de votre graphique et de votre fonction de coût, ainsi que de vos exigences en matière d'optimalité.

Answer 2

Avec A *, le coût du trajet n'a pas besoin d'être constant, vous pouvez donc commencer par le graphique suivant:

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

où nous voulons aller de A à C. Initialement, l'algorithme de recherche de chemin choisira le chemin A-C puisque A-B-C est 2 alors que A-C est 1. Nous pouvons ajouter un terme supplémentaire aux chemins:

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

avec

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

où

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

Au fur et à mesure que les utilisateurs sont ajoutés au système, la voie de circulation AC deviendra plus chère que ABC à 20 utilisateurs (1 + 20/10) = 3, alors que ABC est égal à 2. À mesure que les utilisateurs sont supprimés du système, la voie de circulation AC devient la meilleure option encore.

La puissance réelle de l'A * est l'heuristique que vous utilisez pour calculer le coût de chaque connexion.

Answer 3

L'algorithme le plus couramment utilisé pour résoudre ce problème est A * (une étoile) . L'algorithme de Dijkstra est une recherche généralisée avec une heuristique supplémentaire - le but de cette heuristique est de diriger la recherche vers l’objectif de recherche afin que les recherches types se terminent plus rapidement.

Cet algorithme a de nombreuses variantes, versions dérivées et améliorations, la recherche Google ou la page Wikipedia devraient constituer un bon point de départ.

Answer 4

Certainement A *. A * trouvera le meilleur chemin possible ou aucun chemin si aucun chemin n'existe. Par exemple. le trajet de ce bateau a été calculé avec A *

_{(source: cokeandcode.com )}

Voici une démo Java interactive avec laquelle jouer. Veuillez noter que cet algorithme est ralenti par les mises en veille, vous le voyez donc en train de fonctionner. Sans ce ralentissement, le chemin serait trouvé en moins d'une seconde.

L’algorithme est simple mais puissant. Chaque nœud a 3 valeurs, g est le coût jusqu’à ce nœud. h est le coût estimé de ce nœud vers la cible et f est la somme des deux (supposition pour le chemin complet). A * maintient deux listes, la liste ouverte et la liste fermée. La liste Ouvrir contient tous les nœuds qui n'ont pas encore été explorés. La liste fermée liste tous les nœuds qui ont été explorés. Un noeud compte comme exploré si l'algorithme a déjà testé chaque noeud connecté à ce noeud (connecté ne peut signifier que horizontalement et verticalement, mais aussi en diagonale si les déplacements en diagonale entre les noeuds sont autorisés).

L'algorithme pourrait être décrit comme

1. Soit P le point de départ
2. Attribuer les valeurs g, h et f à P
3. Ajoutez P à la liste ouverte (à ce stade, P est le seul noeud de cette liste).
4. Soit B le meilleur noeud de la liste Open (meilleur == plus petite valeur f)
   • Si B est le noeud de l'objectif - > quittez, vous avez trouvé le chemin
   • Si la liste Ouvrir est vide - > quitter, aucun chemin n'existe
5. Soit C un noeud valide connecté à B
   • Attribuer g, h et f à C
   • Vérifiez si C est sur la liste ouverte ou fermée
     • Si oui, vérifiez si le nouveau chemin est le plus efficace (valeur f plus faible)
       • Si c'est le cas, mettez à jour le chemin
     • Sinon, ajoutez C à la liste ouverte
   • Répétez l'étape 5 pour tous les nœuds connectés à B
6. Ajouter B à la liste fermée (nous avons exploré tous les voisins)
7. Répétez à partir de l'étape 4.

Consultez également Wikipedia pour plus de détails sur la mise en oeuvre.

Answer 5

J'ai entendu parler d'une implémentation NN pour traiter ce type de problème également. Donc, si vous voulez utiliser les NN, vous finirez par trouver votre chemin ;-) mais ils doivent être inférieurs par rapport aux "algorithmes génétiques".

Si la consommation en temps de calcul est un problème, je suggérerais fortement d’utiliser des algorithmes génétiques. C'est exactement le type de problèmes auquel ils sont exceptionnels.

Les GA sont basés sur une fonction qui décrit votre satisfaction pour une solution donnée. Vous pouvez modifier cette fonction en fonction de vos besoins (en d’autres termes, vous pouvez inclure non seulement le coût du chemin, mais également le facteur de votre choix).

Answer 6

Un Dijkstra commun ne serait-il pas suffisant?

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

Answer 7

Algorithme de Dijkstras, 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")