Porque é que a minha versão do algoritmo, de modo lento, com essa entrada?

Question

Aqui eu estou tentando fazer uma comparação de dois simples possível algoritmos, a solução do problema do caixeiro viajante simétrico, encontrar a solução ideal sem o apoio de heurística.Eu estou mostrando (ou de referência) o código de ambos os algoritmos apenas para melhor especificar os detalhes de implementação, que poderão ser relevantes para a comparação.Eu escrevi o meu F# código para resolver o Advento do Código de Dia 18 Parte 1.É um BFS adaptado para encontrar a melhor solução para uma ponderada gráfico (a última versão foi editada desde que a pergunta original foi postado aqui, mas, como já disse, ignorar esse tipo de detalhes).Enquanto ele parece funcionar bem com outros simples demonstração de entradas, ele stucks para sempre com a entrada a seguir.

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

Ele representa uma lista de minúsculas char vértices com letras maiúsculas restrita antecessores e bordas ponderada por diferentes pontilhada distâncias.Então aqui eu estou olhando para uma comparação com base no tempo de complexidade de algoritmos, relacionados à análise de casos em que o número de arestas aumenta, em um número fixo de vértices.Há um solução de referência em Python o que é correto e rápido, mas eu não consigo ver onde está a diferença fundamental entre os dois algoritmos, atrás de outras pequenas diferenças de código (também porque as línguas são diferentes).

Eu tentei com a recursividade vs uma fila, com árvore vs grade/mapa (ver o meu github história), mas sem sorte até agora.

A parte principal do código é descrito abaixo.Deve cair em uma amplitude first search (BFS) algoritmo, cujos detalhes de implementação são relatados abaixo, só para completar a descrição teórica já dada, porque o padrão BFS foi adaptado para vários destinos, ponderada bordas e uma tentativa de poda de árvores.

Aqui está como eu produzir uma única etapa, por que eu elaboro a solução.

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

Repare que esta é uma versão restrita do TSP onde cada vértice pode ter restrição de uma lista de predecessores.

O fullGrid deve conter a matriz de distâncias e parece-me muito bem, em termos dos valores nele quando eu depurá-lo.A quebra do solver é simplesmente uma recursão ou fila versão com base do BFS.Novamente, eu não estou interessado em detalhes de programação, mas em termos de compreensão, em um nível conceitual, porque o algoritmo subjacente não é aplicável para uma aparentemente difíceis de ser tratados caso do input (de "apenas" 16 nós).

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

Eu descobri que o problema conceitual.Em um BFS tipo de pesquisa, quando a otimização é necessária porque o comprimento da fila cresce a velocidade crítica, você tem que pegar a linha do visitou itens.

O objetivo é evitar a adição de outro item a fila quando é já presente um melhor item não.

Apenas algumas código, apenas para esclarecer o conceito.

No meu caso Eu adicionei a visita mapa

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

e eu vou colocar apenas os melhores itens:

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 ignorando os piores

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

Função de custo

A partir de um ponto de vista teórico, BFS pode garantir que a primeira solução retornada será como curto quanto possível, somente se podemos supor que cada movimento tem um custo de 1.Você pode reduzir os exemplos acima para isto, mas o melhor ajuste permanece um gráfico onde o função de custo é representava por bordas de comprimento diferente.Com real, funções de custo encontrar o menor caminho torna-se mais envolvido:este é exatamente o caso aqui.Especialmente porque você tem que otimizar também o Espaço complexidade (ver parágrafo anterior), evitando o pior caso de tempo de complexidade $S(b^d)$, com $b$ sendo o fator de ramificação e $d$ a profundidade da primeira solução.Você descreveu um cenário onde $d$ é bem conhecido no início (o número de chaves no labirinto), enquanto que o caso de borda que você menciona é obtida através de um maior $b$ (número de passagens do labirinto)