Algorithme: le plus court chemin entre tous les points

Supposons que j'ai 10 points. Je sais que la distance entre chaque point.

J'ai besoin de trouver le plus court chemin passant par tous les points.

J'ai essayé quelques algorithmes (Dijkstra, Floyd Warshall,...) et ils ont tous de me donner le chemin le plus court entre le début et la fin, mais ils ne font pas une route avec tous les points.

Permutations bien fonctionner, mais ils sont trop de ressources-cher.

Quels algorithmes pouvez-vous me conseiller de regarder pour ce problème? Ou est-il documenté de façon à ce faire avec les algorithmes?

source d'informationauteur Jeroen

  1. 24

    Ont un coup d'oeil à problème du voyageur de commerce.

    Vous voudrez peut-être chercher dans certains heuristique des solutions. Ils peuvent ne pas être en mesure de vous donner à 100% à des résultats exacts, mais souvent ils peuvent venir avec assez bonnes solutions (2 à 3 % de solutions optimales) dans un laps de temps raisonnable.

  2. 6

    C'est évidemment Problème du voyageur de commerce. Spécifiquement pour N=10vous pouvez soit essayer de le O(N!) naïve de l'algorithme, ou à l'aide de La Programmation Dynamiquevous pouvez réduire ce à O(n^2 2^n)en l'espace de trading.

    Au-delà, puisque c'est un problème NP-difficile, vous ne pouvez qu'espérer pour un rapprochement ou heuristiques, étant donné les mises en garde habituelles.

  3. 2

    Comme d'autres l'ont mentionné, c'est une instance de la TSP. Je pense que Concorddéveloppé à Georgia Tech, est l'état actuel de l'art-solveur. Il peut traiter plus de 10 000 points dans un délai de quelques secondes. Il dispose également d'une API facile à travailler avec.

  4. 0

    Je pense que c'est ce que vous cherchez, en fait:

    Floyd Warshall

    En informatique, le Floyd–Warshall algorithme (parfois connu sous le nom
    l'EPI de l'Algorithme de[clarification nécessaire], Roy–algorithme de Floyd ou tout simplement
    Floyd algorithme) est un graphe d'algorithme d'analyse pour trouver le plus court
    les chemins dans un graphe pondéré (positifs ou négatifs bord de poids). Un
    seule l'exécution de l'algorithme trouverez les longueurs (résumé
    poids les plus courts chemins entre toutes les paires de sommets bien qu'il
    ne pas renvoyer les détails des chemins eux-mêmes

    Dans le "Chemin de la reconstruction" du paragraphe il explique la structure de données vous aurez besoin de stocker les "chemins" (en fait, vous venez de stocker le prochain nœud à aller à, puis trivialement reconstruire selon le chemin d'accès est requis en tant que de besoin).