Perché la versione del mio algoritmo è così lenta con questo input?

Question

Qui sto cercando di fare un confronto tra due algoritmi il più semplici possibile, risolvendo il problema del commesso viaggiatore simmetrico, trovando la soluzione ottimale senza il supporto dell'euristica.Mostro (o semplicemente faccio riferimento) il codice di entrambi gli algoritmi solo per specificare meglio i dettagli di implementazione, che potrebbero essere rilevanti per il confronto.Ho scritto il mio Codice F# per risolvere l'Avvento del Codice Giorno 18 Parte 1.È un BFS adattato per trovare la soluzione ottimale per un grafico ponderato (l'ultima versione è stata modificata da quando la domanda originale è stata pubblicata qui, ma, come già detto, ignora questo tipo di dettagli).Anche se sembra funzionare bene con altri semplici input demo, rimane bloccato per sempre con l'input seguente.

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

Rappresenta un elenco di vertici di caratteri minuscoli con predecessori e bordi vincolati in maiuscolo pesati da diverse distanze tratteggiate.Qui cerco quindi un confronto basato sulla complessità temporale degli algoritmi, legato ad un'analisi dei casi in cui il numero di spigoli aumenta, ad un numero fisso di vertici.C'è un soluzione di riferimento in Python il che è corretto e veloce, ma non riesco a vedere dove sia la differenza fondamentale tra i due algoritmi, dietro le altre piccole differenze di codice (anche perché i linguaggi sono diversi).

Ci ho provato con ricorsione vs coda, con albero vs griglia/mappa (vedi la mia cronologia di GitHub) ma senza fortuna fino ad ora.

La parte principale del codice è descritta di seguito.Dovrebbe rientrare in un algoritmo di ricerca in ampiezza (BFS), i cui dettagli di implementazione sono riportati di seguito solo per completare la descrizione teorica già fornita, poiché il BFS standard è stato adattato a obiettivi multipli, bordi ponderati e una potatura provvisoria degli alberi.

Ecco come produco il singolo passaggio attraverso il quale elaboro la soluzione.

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

Si noti che questa è una versione vincolata del TSP in cui ogni vertice può avere come vincolo un elenco di predecessori.

IL fullGrid dovrebbe contenere la matrice delle distanze e mi sembra a posto, in termini di valori che contiene quando eseguo il debug.Il risolutore del wrap è semplicemente una versione del BFS basata sulla ricorsione o sulla coda.Ancora una volta, non sono interessato ai dettagli della programmazione ma a capire, a livello concettuale, perché l'algoritmo sottostante non è applicabile per un caso di input apparentemente trattabile (di "soli" 16 nodi).

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

Ho trovato il problema concettuale.In un tipo di ricerca BFS, quando è necessaria l'ottimizzazione perché il file lunghezza della coda cresce a velocità critica, devi tenerne traccia visitato elementi.

L'obiettivo è evitare di aggiungere un altro elemento alla coda quando lo è già presente UN oggetto migliore Là.

Solo un po' di codice, solo per chiarire il concetto.

Nel mio caso ho aggiunto una mappa visitata

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

e sto accodando solo gli elementi migliori:

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

e tralasciando quelli peggiori

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

Funzione di costo

Da un punto di vista teorico, BFS può garantire che il prima la soluzione restituita sarà come corto il più possibile, solo se possiamo supporre che ogni mossa abbia un costo pari a 1.Potresti ridurre gli esempi precedenti a questo, ma la soluzione migliore rimane a grafico dove il funzione di costo è rappresentato dai bordi di lunghezza diversa.Con funzioni di costo reale trovare il percorso più breve diventa più complicato:questo è esattamente il caso qui.Soprattutto perché devi ottimizzare anche il file Complessità spaziale (vedi paragrafo precedente), evitando la complessità temporale del caso peggiore $O(b^d)$, con $b$ essendo il fattore di ramificazione e $d$ la profondità della prima soluzione.Hai descritto uno scenario in cui $d$ è ben noto all'inizio (il numero delle chiavi nel labirinto) mentre il caso limite di cui parli è ottenuto da uno più grande $b$ (numero di attraversamenti del labirinto)