Pourquoi la version de mon algorithme est-elle si lente avec cette entrée ?

Question

Ici, j'essaie de faire une comparaison de deux algorithmes aussi simples que possible, résolvant le problème du voyageur de commerce symétrique, trouvant la solution optimale sans le support de l'heuristique.Je montre (ou je fais simplement référence) le code des deux algorithmes uniquement pour mieux préciser les détails d'implémentation, qui pourraient être pertinents pour la comparaison.j'ai écrit mon Code F# pour résoudre l'avènement du code Jour 18 Partie 1.Il s'agit d'un BFS adapté pour trouver la solution optimale pour un graphique pondéré (la dernière version a été modifiée depuis la publication de la question originale ici, mais, comme déjà dit, ignorez ce genre de détails).Bien que cela semble fonctionner correctement avec d'autres entrées de démonstration simples, cela reste pour toujours avec l'entrée suivante.

#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################

Il représente une liste de sommets de caractères minuscules avec des prédécesseurs contraints en majuscules et des arêtes pondérées par différentes distances en pointillés.Je recherche donc ici une comparaison basée sur la complexité temporelle des algorithmes, liée à une analyse des cas où le nombre d'arêtes augmente, à un nombre fixe de sommets.Il y a un solution de référence en Python ce qui est correct et rapide, mais je ne vois pas où est la différence fondamentale entre les deux algorithmes, derrière les autres différences mineures de code (également parce que les langages sont différents).

j'ai essayé avec récursivité vs une file d'attente, avec arbre vs grille/carte (voir mon historique github) mais sans succès jusqu'à présent.

La partie principale du code est décrite ci-dessous.Il devrait relever d'un algorithme de recherche en largeur (BFS), dont les détails de mise en œuvre sont rapportés ci-dessous uniquement pour compléter la description théorique déjà donnée, car le BFS standard a été adapté à des cibles multiples, des bords pondérés et une tentative d'élagage des arbres.

Voici comment je produis l’étape unique par laquelle j’élabore la solution.

1 single step receives as input which is the move index i
2 then it updates the distance of the current solution draft by summing the distance to the vertex i
3 it updates the current position as of vertex i
4 it also updates the list of predecessors by including vertex i
5 it computes the new tree of reachable vertices starting from the `fullGrid` and taking into account the newly updated list of predecessors

Notez qu'il s'agit d'une version contrainte du TSP où chaque sommet peut avoir comme contrainte une liste de prédécesseurs.

Le fullGrid est censé contenir la matrice des distances et cela me semble bien, en termes de valeurs qu'il contient lorsque je le débogue.Le solveur d'encapsulation est simplement une version récursive ou basée sur une file d'attente du BFS.Encore une fois, je ne suis pas intéressé par les détails de la programmation mais par la compréhension, à un niveau conceptuel, pourquoi l'algorithme sous-jacent n'est pas applicable à un cas d'entrée apparemment traitable (de "seulement" 16 nœuds).

Start by receiving the graph topology and starting point
    Define a mindistance variable
    and a list of completed solutions, initially empty

    Start looping at the queue of partial solutions
        So a single partial solution is dequeued
        It computes possible vertices based on current predecessors
        Check if nothing remains and adds it to the completed alternatives updating mindistance
        Otherwise loop as in classical BFS
        For all possible moves = reachable vertices

                For each one applies above said single step
                If done updates mindistance and completed alternatives 
                Otherwise enqueue such partial solution 


    Finally select the min alternative by distance.

Answer 1

J'ai trouvé le problème conceptuel.Dans une recherche de type BFS, lorsqu'une optimisation est nécessaire car le longueur de la file d'attente grandit à une vitesse critique, il faut suivre le a visité articles.

Le but est de éviter d'ajouter un autre élément à la file d'attente quand c'est le cas déjà présent un meilleur article là.

Juste un peu de code, uniquement pour clarifier le concept.

Dans mon cas J'ai ajouté une carte visitée

let mutable visited = Map.empty<char,((char list) * int) list>

et je ne mets en file d'attente que les meilleurs éléments :

if visited.ContainsKey(solutionNext.tree.area) 
    && (visited.[solutionNext.tree.area] 
        |> List.exists (
            fun (keys, distance) -> 
            distance <= solutionNext.tree.distance
            && solutionNext.keys |> List.forall(fun k -> keys |> List.contains k)
        ))
then () 
else 
    solution_queue <- enqueue solution_queue solutionNext
    let previous = if visited.ContainsKey(solutionNext.tree.area) then visited.[solutionNext.tree.area] else []
    visited <- Map.add solutionNext.tree.area ((solutionNext.keys, solutionNext.tree.distance) :: previous)  visited

et sauter les pires

while (MyQueue.length solution_queue > 0) do
    let solution = dequeue &solution_queue
    if visited.ContainsKey(solution.tree.area) 
        && (visited.[solution.tree.area] 
            |> List.exists (
                fun (keys, distance) -> 
                distance < solution.tree.distance
                && solution.keys |> List.forall(fun k -> keys |> List.contains k)
            ))
    then () else

Fonction de coût

D'un point de vue théorique, BFS peut garantir que le d'abord la solution retournée sera la même court que possible, seulement si nous pouvons supposer que chaque mouvement a un coût de 1.Vous pourriez réduire les exemples ci-dessus à cela, mais le meilleur ajustement reste un graphique où le fonction de coût est représenté par les bords de longueur différente.Avec fonctions de coût réel trouver le chemin le plus court devient plus complexe :c'est exactement le cas ici.Surtout parce qu'il faut également optimiser le Complexité spatiale (voir paragraphe précédent), en évitant la complexité temporelle du pire des cas $O(b^d)$, avec $b$ étant le facteur de branchement et $d$ la profondeur de la première solution.Vous avez décrit un scénario dans lequel $d$ est bien connu au départ (le nombre de clés dans le labyrinthe) alors que le cas limite que vous évoquez est obtenu par un plus grand $b$ (nombre de traversées du labyrinthe)