Problème: J'ai une grande collection de points. Chacun de ces points a une liste avec des références à d'autres points avec la distance entre eux déjà calculée et stockée. Je dois déterminer la route la plus courte qui commence à partir d'une origine et passe à travers un nombre spécifique de points à n'importe quelle destination.
ex: Je suis en vacances et je reste dans une ville spécifique. Je fais un voyage aller simple pour voir quatre villes et je veux parcourir la moindre distance possible. Je ne peux pas visiter la même ville plus d'une fois.
solution actuelle: En ce moment, je suis tout à fait itérant à travers toutes les possibilités manuellement et stockez le chemin le plus court. Cela fonctionne mais se sent inefficace. En outre, ce problème sera éventuellement élargi pour inclure la recherche de plusieurs points d'origine à plusieurs points de destination, alors je pense que cela pourrait exploser l'espace de recherche.
Quel est le meilleur moyen de rechercher la route la plus courte?
7 Réponses :
Cela sonne vendre du vendeur-esque? Une solution consiste à utiliser une technique d'optimisation telle qu'un algorithme évolutif. Actuellement, vous faites une recherche exhaustive, qui sera très lente très rapidement. Mais je pense que cela est à peu près un problème de vendeur itinérant et il a été abordé depuis plusieurs décennies, sinon des siècles, et de nombreux moyens d'attaque possibles. Google est votre ami.
Ce n'est pas TSP puisque vous pouvez passer dans le même point plus qu'une fois.
Je pensais que le TSP impliquait de connaître chaque point qui devait être touché? Dans mon cas, il n'y a pas de points spécifiques qui doivent être inclus, juste des points qui suivent le chemin le plus court d'une origine.
@Shay: Il y a beaucoup de saveurs de TSP, y compris celles qui permettent à un utilisateur de visiter le même sommet plusieurs fois.
En général, vous devriez devoir stricter de mauvaises variantes ... Je pense que vous devriez utiliser certaines variantes de la méthode sucaire_and_bound http://fr.wikipedia.org/wiki/branch_and_bound
++ Oui. Il s'agit d'un problème d'optimisation de la recherche d'arbres, de sorte que la branche et la liaison s'applique. Cela peut être fait de la largeur d'abord ou de profondeur.
Soit Bredth Première recherche comme Norheim.se a déclaré ou Algorithme de Dijkstra serait mon suggestion aussi.
Répondre au poste mis à jour, votre solution de contrôle toutes les possibilités est optimale (au moins, personne n'a découvert de meilleurs algorithmes jusqu'à présent). Oui, c'est un vendeur de voyage, dont l'essense ne touche pas toutes les villes, mais touchant chaque ville pour les futurs interrogateurs: Algorithme Floyd-Warshall et tout floyd- comme les variations sont inapplicables ici.
Fait amusant: o (n ^ 5)> O (n!) Jusqu'à n = 8 :)
Merci. Je l'optimisai quelque peu en trouvant la solution immédiate de trouver les itinéraires individuels les plus courts, puis de descendre d'un niveau et de la recherche, puis de monter un autre niveau (etc.) Je suppose que c'est une première recherche de profondeur?
Cela peut être appelé approfondi - première Traversal , pas une recherche . recherche vise à visiter chaque nœud , tandis que votre algorithme vise à visiter chaque chemin et est donc plus coûteux.
Il n'y a pas d'algorithme de temps polynomial connu. Cependant, cela n'implique pas que la vérification de toutes les possibilités est optimale. Il existe des algorithmes assez sophistiqués pour le problème du vendeur itinérant et des problèmes connexes qui permettent de résoudre des problèmes importants avec des milliers de villes.
Pavel utilise le terme optimal en ce sens que cela trouvera la meilleure solution (quelle que soit la complexité d'exécution) sur tout ensemble de données.
Il semble que les bords de votre graphique soient bidirectionnels. Dans ce cas, l'algorithme que vous recherchez est Algorithme de Dijkstra .
Peut-être que c'est ce que l'affiche originale signifie en "itérant à travers chaque possibilité manuellement et stocke le chemin le plus court", mais je pensais que j'aimerais faire explicit ce qui semble être une solution de base.
Supposons que vous avez déjà un algorithme de chemin le plus court de deux points - cela comporte des solutions classiques pour divers types de graphiques. Supposons que toutes les distances sont non négatives et D (A-> B-> C) = D (A-> B) + D (B-> C).
L'essentiel est que le chemin commence à S passe par l'une des villes intermédiaires "ABCD" et se termine par E:
E.g. SABCDE, SACBDE, ETC ...
Avec seulement 4 villes intermédiaires, vous énumérez les 24 permutations. Pour chaque permutation, utilisez votre algorithme à deux points le plus court pour calculer le chemin de la tête à la queue et sa distance totale.
Ensuite, étant donné le point de départ et de fin, il y a 12 possibilités attachées à l'une des ABCD et pour chaque deux possibilités d'intérieurs. Vous avez déjà calculé ces distances, vous ajoutez donc à la distance de S à la tête et à la queue sur E. Choisissez un minimum. Donc, une fois que vous avez précalisé les distances intermédiaires pour un ensemble fixe de villes intérieures, vous devez effectuer 12 problèmes de chemin les plus courts de deux points pour une paire de points de départ et de fin.
Cela échoue évidemment mal avec un nombre croissant de villes intermédiaires. Ce n'est pas clair pour moi que cela pourrait faire mieux à moins d'imposer des restrictions plus importantes sur la structure graphique (est-ce dans un espace d'euclidénan physique? Inégalité de triangle?).
Mon exemple de pensée: Supposons que toutes les distances intermédiaires entre les villes soient O (1). Sans restriction sur le graphique, la distance de S à une ville intermédiaire peut être de 1 000 sauf pour un étant 1. Idemble pour la queue. Vous pouvez donc forcer la première ville à être visitée pour être n'importe quoi. Maintenant, allez-y une couche, prenez la première ville comme le «point de départ». Appliquez le même argument: vous pouvez faire le meilleur chemin dans n'importe laquelle des villes suivantes en manipulant les distances du graphique.
Il semble donc que la complexité ne puisse pas être aidée sans hypothèses supplémentaires.
Il s'agit de la situation en temps très répandue et en temps réel que tout le monde peut tomber dans.Google MAP, l'interface utilisateur vous donne le chemin dans le même ordre, vous ajoutez dans la liste de destination. Cela ne vous donne pas le chemin optimal, bien que leur propre API Google Maps fournit la solution.
Google Maps API fournit la solution à cet effet. Dans la demande de découvrir le chemin, vous devez fournir le drapeau 'optimizewaypoints: vrai,'. La demande semblera comme ça. et vous pouvez voir le code total de l'utilitaire dans la source de vue sous forme d'utilitaire complet est développé dans JavaScript et HTML. J'espère que cela aidera.
Votre site Web est Down Buddy, c'est donc le lien
Est-ce un graphique directionnel ou bidirectionnel? Je ne peux pas dire.
Certaines des réponses ici (TSP, Floyd-Warshall, la première, la branche et la liaison) sont dérivées d'interprétations follement incohérentes et contradictoires de cette question, donc je suis enclin à penser que la question ici n'est très bien formulée.
Permettez-moi brièvement de reformuler: un exemple est que je prends des vacances et je reste à une ville. Je veux voir quatre villes à partir de la mienne et je veux parcourir la moindre distance possible. Je ne peux pas visiter la même ville plus d'une fois.
Votre édition récente change totalement la façon dont j'ai interprété votre question.
Oh mon Dieu. Cela invalide une solution basée sur Floyd-Warshall si fort qu'ils ont même l'air assez ridicule :)
Désolé! C'est ma première publication ici ... :(