Warum ist meine Algorithmusversion bei dieser Eingabe so langsam?

Question

Hier versuche ich einen Vergleich zweier möglichst einfacher Algorithmen durchzuführen, um das symmetrische Problem des Handlungsreisenden zu lösen und die optimale Lösung ohne die Unterstützung von Heuristiken zu finden.Ich zeige (oder verweise nur) den Code beider Algorithmen nur, um die Implementierungsdetails besser zu spezifizieren, die für den Vergleich relevant sein könnten.Ich habe meine geschrieben F#-Code um Advent of Code zu lösen Tag 18 Teil 1.Es handelt sich um ein BFS, das angepasst wurde, um die optimale Lösung für ein gewichtetes Diagramm zu finden (die letzte Version wurde bearbeitet, seit die ursprüngliche Frage hier gepostet wurde, aber wie bereits gesagt, ignorieren Sie diese Art von Details).Während es mit anderen einfachen Demo-Eingaben gut zu funktionieren scheint, bleibt es bei der folgenden Eingabe für immer hängen.

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

Es handelt sich um eine Liste von Kleinbuchstaben mit auf Großbuchstaben beschränkten Vorgängern und Kanten, die durch unterschiedliche Punktabstände gewichtet sind.Hier suche ich also nach einem Vergleich, der auf der zeitlichen Komplexität der Algorithmen basiert und sich auf eine Analyse der Fälle bezieht, in denen die Anzahl der Kanten bei einer festen Anzahl von Eckpunkten zunimmt.Da ist ein Referenzlösung in Python Das ist korrekt und schnell, aber ich sehe nicht, wo der grundlegende Unterschied zwischen den beiden Algorithmen hinter den anderen geringfügigen Codeunterschieden liegt (auch weil die Sprachen unterschiedlich sind).

Ich habe es mit versucht Rekursion vs. eine Warteschlange, mit Baum vs. Raster/Karte (siehe meine Github-Geschichte), aber bis jetzt ohne Erfolg.

Der Hauptteil des Codes wird unten beschrieben.Es sollte unter einen Breitensuchalgorithmus (BFS) fallen, dessen Implementierungsdetails unten nur zur Vervollständigung der bereits gegebenen theoretischen Beschreibung angegeben werden, da das Standard-BFS an mehrere Ziele, gewichtete Kanten und eine vorläufige Baumbeschneidung angepasst wurde.

So erstelle ich den einzelnen Schritt, mit dem ich die Lösung ausarbeite.

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

Beachten Sie, dass dies eine eingeschränkte Version des TSP ist, bei der jeder Scheitelpunkt eine Liste von Vorgängern als Einschränkung haben kann.

Der fullGrid soll die Abstandsmatrix enthalten und sieht für mich in Bezug auf die darin enthaltenen Werte beim Debuggen gut aus.Der Wrapping-Solver ist einfach eine rekursive oder warteschlangenbasierte Version des BFS.Auch hier geht es mir nicht um die Programmierdetails, sondern darum, auf konzeptioneller Ebene zu verstehen, warum der zugrunde liegende Algorithmus für einen scheinbar handhabbaren Eingabefall (von „nur“ 16 Knoten) nicht anwendbar ist.

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

Ich habe das konzeptionelle Problem gefunden.Wenn bei einer BFS-Suche eine Optimierung erforderlich ist, weil die Länge der Warteschlange wächst mit kritischer Geschwindigkeit, man muss den Überblick behalten hat besucht Artikel.

Das Ziel ist es Vermeiden Sie es, ein weiteres Element hinzuzufügen in die Warteschlange, wenn es ist bereits anwesend A besserer Artikel Dort.

Nur ein bisschen Code, nur um das Konzept zu verdeutlichen.

In meinem Fall Ich habe hinzugefügt eine besuchte Karte

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

und ich stelle nur bessere Artikel in die Warteschlange:

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

und die schlimmsten überspringen

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

Kostenfunktion

Aus theoretischer Sicht kann BFS garantieren, dass die Zuerst Die zurückgegebene Lösung wird wie folgt sein kurz wie möglich, nur wenn Wir können davon ausgehen, dass jeder Zug Kosten von 1 hat.Man könnte die obigen Beispiele darauf reduzieren, aber die beste Lösung bleibt a Graph bei dem die Kostenfunktion wird durch Kanten von dargestellt unterschiedliche Länge.Mit reale Kostenfunktionen Das Finden des kürzesten Weges wird komplizierter:genau das ist hier der Fall.Vor allem, weil man auch das optimieren muss Raumkomplexität (siehe vorherigen Absatz), wodurch die zeitliche Komplexität im schlimmsten Fall vermieden wird $O(b^d)$, mit $b$ der Verzweigungsfaktor sein und $d$ die Tiefe der ersten Lösung.Sie haben ein Szenario beschrieben, in dem $d$ ist zu Beginn bekannt (die Anzahl der Schlüssel im Labyrinth), während der von Ihnen erwähnte Randfall von einem größeren erhalten wird $b$ (Anzahl der Durchquerungen des Labyrinths)