¿Por qué mi algoritmo versión tan lento con esta entrada?

Question

Aquí estoy tratando de hacer una comparación de dos simples como sea posible de los algoritmos, la resolución de la simetría del problema del viajante, la búsqueda de la solución óptima sin el apoyo de la heurística.Yo estoy mostrando (o sólo de referencia) en el código de ambos algoritmos sólo para especificar mejor los detalles de la implementación, que podrían ser pertinentes para la comparación.He escrito mi F# código para resolver Advenimiento de Código El día 18 Parte 1.Es un BFS adaptado a encontrar la solución óptima para un grafo ponderado (última versión ha sido editada desde la pregunta original fue publicado aquí, pero, como ya se dijo, ignorar este tipo de detalles).Mientras que parece que funciona bien con otros simple demostración de insumos, stucks para siempre con la siguiente entrada.

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

Representa una lista de caracteres char vértices con mayúsculas limitada predecesores y los bordes de puntos ponderados por diferentes distancias.Así que aquí estoy buscando una comparación basada en el tiempo de la complejidad de los algoritmos, relacionado con un análisis de los casos donde el número de bordes aumenta, en un número fijo de vértices.Hay un solución de referencia en Python cual es el correcto y rápido, pero no veo dónde está la diferencia fundamental entre los dos algoritmos, una detrás de la otra menor código de diferencias (también porque las lenguas son diferentes).

He probado con recursión vs una cola, con árbol vs grid/mapa (véase mi github de la historia), pero no hubo suerte hasta ahora.

La parte principal del código se describe a continuación.Se debe caer bajo una primera extensión de la búsqueda (BFS) algoritmo, cuyos detalles de implementación que se presenta a continuación, sólo para completar la descripción teórica ya dada, debido a que la norma BFS ha sido adaptado a los objetivos múltiples, ponderada en los bordes y una tentativa de poda de árboles.

He aquí cómo se produce el paso, por lo que me elaborar la solución.

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

Observe que esta es una versión limitada de la TSP donde cada vértice puede tener como restricción de una lista de predecesores.

El fullGrid se supone que contiene la matriz de distancias y se ve bien para mí, en términos de los valores que contiene cuando me depurar.La envoltura solver es simplemente una recursión de cola o basado en la versión de la BFS.De nuevo, no estoy interesado en los detalles de la programación, sino en la comprensión, en un nivel conceptual, ¿por qué el algoritmo subyacente no es aplicable para un aparentemente manejable entrada de caso (de "solo" 16 nodos).

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

He encontrado el problema conceptual.En un BFS tipo de búsqueda, cuando la optimización es necesario debido a que el la longitud de la cola crece a la velocidad crítica, usted tiene que tomar la pista de la visitado elementos.

El objetivo es evitar la adición de otro elemento a la cola cuando se ya presente un mejor elemento no.

Sólo un poco de código, sólo para aclarar el concepto.

En mi caso He añadido una visitado mapa

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

y estoy colocación sólo los mejores artículos:

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

y saltarse los peores

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

Función de costo

Desde un punto de vista teórico, BFS puede garantizar que el primero solución devuelto será como corto como es posible, sólo si podemos suponer que cada movimiento tiene un costo de 1.Usted podría reducir los ejemplos anteriores, pero el mejor ajuste sigue siendo un gráfico donde el función de costo es represeted por los bordes de las longitud diferente.Con coste real de las funciones de encontrar la ruta más corta se vuelve más involucrados:este es exactamente el caso aquí.Sobre todo porque usted tiene que optimizar también el El espacio de la complejidad (véase el párrafo anterior), evitando el peor de los casos el tiempo de la complejidad de $O(b^d)$, con $b$ siendo el factor de ramificación y $d$ la profundidad de la primera solución.Se han descrito un escenario donde $d$ es bien sabido que en inicio (el número de las claves en el laberinto), mientras que el caso extremo de mencionar que se obtiene una mayor $b$ (número de cruces de el laberinto)