Algorithmes TSP optimisés
Je suis intéressé par les moyens d'améliorer ou de trouver des algorithmes qui sont en mesure de résoudre le Problème du voyageur de commerce environ n = 100 to 200
villes.
Le lien wikipédia que j'ai donné la liste des diverses optimisations, mais il le fait à un assez haut niveau, et je ne sais pas comment aller sur le fait de les mettre en œuvre dans le code.
Il y a de la puissance industrielle des problèmes là-bas, comme Concordemais ceux-ci sont bien trop complexe pour ce que je veux, et les solutions classiques qui inondent les recherches de c. à thé de tous les présents algorithmes randomisés ou le classique retours en arrière ou les algorithmes de programmation dynamique, qui ne fonctionnent que pour environ 20 villes.
Donc, personne ne sait comment implémenter un simple (par simple je veux dire qu'une mise en œuvre ne prend pas plus de 100 à 200 lignes de code) TSP solveur qui travaille dans un temps raisonnable (quelques secondes) pour au moins 100 villes? Je suis seulement intéressé par des solutions exactes.
Vous pouvez supposer que l'entrée sera généré aléatoirement, donc je n'ai pas de soins pour les entrées qui sont spécifiquement destinées à briser un certain algorithme.
source d'informationauteur IVlad
Vous devez vous connecter pour publier un commentaire.
200 lignes et pas de bibliothèques est difficile de contrainte. L'avancée des solveurs utilisent branch and bound avec le Lieu–Karp de détente, et je ne suis pas sûr que même si la plupart des version de base, qui correspondent en 200 lignes normales. Néanmoins, voici un aperçu.
Tenue Karp
Une façon d'écrire c. à thé comme un entier programme est comme suit (Dantzig, Fulkerson, Johnson). Pour toutes les arêtes e, la constante we désigne la longueur de l'arête e, et de la variable xe est 1 si l'arête e est sur le tour, et 0 sinon. Pour tous les sous-ensembles S de sommets, ∂(S) désigne les arêtes reliant les sommets S, avec un sommet pas dans S.
minimiser la sommebords e we xe
sous réserve
1. pour tous les sommets v, sommebords e ∂({v}) xe = 2
2. pour tous non vides bon sous-ensembles S de sommets, sommebords e ∂(S) xe ≥ 2
3. pour toutes les arêtes de e dans E, xe dans {0, 1}
Condition 1 assure que l'ensemble des arêtes est une collection de circuits. Condition 2 assure qu'il n'y a qu'un seul. (Sinon, soit S l'ensemble des sommets visités par l'une des tours.) Le Lieu–Karp relaxation est obtenue en faisant ce changement.
3. pour toutes les arêtes de e dans E, xe dans {0, 1}3. pour toutes les arêtes de e dans E, 0 ≤ xe ≤ 1
Lieu–Karp est un programme linéaire, mais il a un nombre exponentiel de contraintes. Une façon de le résoudre est d'introduire des multiplicateurs de Lagrange et puis ne subgradient d'optimisation. Qui se résume à une boucle qui calcule un minimum spanning tree et puis les mises à jour de certains vecteurs, mais les détails sont en quelque sorte impliqué. En plus de "Tenue–Karp" et "subgradient (descente|optimisation)", "1-arbre" est un bon terme de recherche.
(Un ralentissement de l'alternative consiste à écrire un LP solveur et introduire subtour de contraintes sont violées par les précédents optima. Cela signifie que l'écriture d'un LP solveur et un min-cut procédure, qui est aussi plus de code, mais il peut améliorer et étendre les plus exotiques c. à thé de contraintes).
Branch and bound
Par "solution partielle", je veux dire une cession partielle de variables à 0 ou 1, où un avantage attribué 1 qui est certainement dans la tour, et un bord assigné 0 est définitivement hors. L'évaluation Tiendra–Karp avec ces contraintes donne une borne inférieure sur l'optimum de la tour qui respecte les décisions déjà prises (une extension).
Branch and bound maintient un ensemble de solutions partielles, au moins un de ce qui s'étend à une solution optimale. Le pseudo-code pour une variante, la profondeur d'abord de recherche avec le meilleur de la première mandature est comme suit.
L'idée de branch and bound est qu'il y a un arbre de recherche de solutions partielles. Le point de résoudre Lieu–Karp est que la valeur de la LP est tout au plus la longueur de l'OPT de la meilleure tournée, mais aussi conjecturé être d'au moins 3/4 OPT (dans la pratique, habituellement plus près à la FAC).
L'un détail, dans le pseudo-code que j'ai laissé de côté est de savoir comment choisir la ramification de la variable. Le but est généralement de faire le "dur" des décisions de première, de sorte que la fixation d'une variable dont la valeur est déjà proche de 0 ou 1 n'est probablement pas sage. Une option est de choisir le plus proche de 0,5, mais il y a beaucoup, beaucoup d'autres.
MODIFIER
Implémentation de Java. 198 non vides contenues, noncomment lignes. J'ai oublié que 1-les arbres ne fonctionnent pas avec l'affectation des variables à 1, donc je branche par trouver un sommet dont 1-arbre est de degré >2 et supprimer chaque bord à son tour. Ce programme accepte TSPLIB cas dans
EUC_2D
format, par exemple,eil51.tsp
eteil76.tsp
eteil101.tsp
etlin105.tsp
de http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/.Si votre graphique satisfaire le triangle de l'inégalité et vous voulez une garantie de 3/2 au sein de l'optimum, je vous suggère de christofides algorithme. J'ai écrit une implémentation en php phpclasses.org.
À compter de 2013, Il est possible de résoudre de 100 villes en utilisant uniquement la formulation exacte de Cplex. Ajouter degré des équations pour chaque sommet, mais comprennent subtour-en évitant des contraintes telles qu'elles apparaissent. La plupart d'entre eux ne sont pas nécessaires. Cplex a un exemple sur ce.
Vous devriez être en mesure de résoudre de 100 villes. Vous aurez à effectuer une itération à chaque fois une nouvelle subtour est trouvé. J'ai couru un exemple ici et dans un couple de minutes et 100 itérations plus tard, j'ai reçu mes résultats.
J'ai pris Lieu-Karp algorithme de la concorde de la bibliothèque et 25 villes sont résolus à 0,15 secondes. Cette performance est parfaitement bien pour moi! Vous pouvez extraire le code (écrit en C ANSI) de lieu-karp de la concorde de la bibliothèque: http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm. Si le téléchargement a l'extension gz, il devrait être tgz. Vous pourriez avoir besoin de le renommer. Ensuite, vous devez faire de petits ajustements à port en VC++. Prenez d'abord le fichier heldkarp h et c (renommer rpc) et de l'autre d'environ 5 fichiers, faire des ajustements et cela devrait fonctionner appel CCheldkarp_small(...) avec edgelen: euclid_ceiling_edgelen.
C. à thé est un problème NP-difficile. (Autant que nous le sachions) il n'y a pas d'algorithme pour un problème NP-difficile des problèmes qui s'exécute en temps polynomial, si vous demandez quelque chose qui n'existe pas.
C'est assez rapide à finir dans un délai raisonnable, et puis il n'est pas exact, ou exact, mais n'arrive pas à terminer dans votre vie de 100 villes.
De donner une réponse muette: moi aussi. Tout le monde est intéressé par un tel algorithme, mais comme d'autres, a déclaré: je ne dispose pas (encore?) existent. Esp votre combinaison de exact, 200 nœuds, quelques secondes d'exécution et à seulement 200 lignes de code est impossible. Vous savez déjà qu'il est NP-difficile et si vous avez la moindre impression de comportement asymptotique vous devriez savoir qu'il n'existe pas de moyen d'y parvenir (à l'exception de vous prouver que NP=P, et même que je dirais que c'est pas possible). Même l'exact commercial solveurs besoin pour de tels cas beaucoup plus que quelques secondes et comme vous pouvez l'imaginer, ils ont beaucoup plus de 200 lignes de code (même si vous il suffit de considérer leur noyau).
EDIT: Le wiki des algorithmes sont les "suspects habituels" du terrain: Programmation Linéaire et de branch-and-bound. Leurs solutions pour les instances avec des milliers de nœuds a fallu des Années pour résoudre (ils l'ont fait avec beaucoup de Processeurs parallèles, de sorte qu'ils peuvent le faire plus vite). Certains utilisent même pour le branch-and-bound problème des connaissances spécifiques pour les cadres, afin qu'ils ne soient approches générales.
Branch and bound juste énumère tous les chemins possibles (par exemple, avec les retours en arrière) et s'applique une fois qu'il a une solution pour arrêter un a commencé la récursivité lorsqu'il peut prouver que le résultat n'est pas meilleur que le déjà trouvé la solution (par exemple, si vous venez de visiter 2 de vos villes et le chemin d'accès est déjà plus qu'un découvert de 200 visite de la ville. Vous pouvez ignorer toutes les visites qui commencent par 2 de la ville de combinaison). Ici vous pouvez investir beaucoup de problème de connaissances spécifiques dans la fonction qui vous dit, que le chemin ne va pas être mieux que le déjà trouvé la solution. Le mieux c'est, du moins chemins d'accès que vous avez à regarder, le plus rapide est de votre algorithme.
La Programmation linéaire est une méthode d'optimisation afin de résoudre linéaire de l'inégalité des problèmes. Il fonctionne en temps polynomial (recto seulement pratique, mais qui n'importe pas ici), mais la solution est réel. Lorsque vous avez la contrainte supplémentaire que la solution doit être un entier, il devient NP-complet. Pour les petits cas, il est possible, par exemple, une méthode pour le résoudre, puis de regarder quelles sont les variables de la solution viole la partie entière et ajouter plus d'inégalités de le changer (ce qui est appelé coupe-plan, le nom provient du fait que les inégalités de définir plus élevé (plus de dimensions) à l'avion, l'espace de solution est un polytop et en ajoutant des inégalités de vous couper quelque chose avec un avion de la polytop). Le sujet est très complexe et même un général simple simplex est difficile à comprendre si vous ne voulez pas plonger profond dans les mathématiques. Il y a plusieurs bons livres sur le sujet, l'un des parieurs est de Chvatal, Programmation Linéaire, mais il y a plusieurs autres.
J'ai une théorie, mais je n'ai jamais eu le temps de poursuivre:
Le TSP est un problème de délimitation (forme unique où tous les points se trouvent sur le périmètre) où la solution optimale est une solution qui a le plus court de périmètre.
Il ya beaucoup de façons simples pour obtenir tous les points qui se situent sur un minimum de délimitation du périmètre (imaginez une grande bande élastique étiré autour d'un tas de clous dans un grand tableau.)
Ma théorie est que si vous commencer à pousser sur la bande élastique de sorte que la longueur de la bande augmente de la même quantité entre les points adjacents sur le périmètre, et chaque segment reste dans la forme de l'un des vélos de l'arc, la étiré élastique va croiser les points sur la trajectoire optimale avant les points de passage non-chemins optimaux. Voir cette page sur mathopenref.com sur le dessin d'ellipses, particulièrement les étapes 5 et 6. Les Points sur la délimitation du périmètre peuvent être considérés comme des points focaux de l'ellipse (F1, F2) dans les images ci-dessous.
Ce que je ne sais pas si la "bulle d'étirement" processus doit être réinitialisé après chaque nouveau point est ajouté, ou si les "bulles" de continuer à croître et à chaque nouveau point sur le périmètre ne provoque que la version localisée de "bulle" pour se transformer en deux segments de ligne. Je vais laisser ça à la figure.