Почему моя версия алгоритма работает так медленно с этим вводом?

Question

Здесь я пытаюсь провести сравнение двух максимально простых алгоритмов, решающих симметричную задачу коммивояжера, находя оптимальное решение без поддержки эвристики.Я показываю (или просто ссылаюсь) код обоих алгоритмов только для того, чтобы лучше указать детали реализации, которые могли бы иметь отношение к сравнению.Я написал свой Код F # чтобы решить проблему появления кода День 18 Часть 1.Это BFS, адаптированный для поиска оптимального решения для взвешенного графика (последняя версия была отредактирована с тех пор, как здесь был опубликован исходный вопрос, но, как уже было сказано, игнорируйте такого рода детали).Хотя кажется, что он отлично работает с другими простыми демонстрационными входными данными, со следующим вводом он застревает навсегда.

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

Он представляет собой список вершин, заполненных строчными символами, с предшественниками, ограниченными прописными буквами, и ребрами, взвешенными по разным расстояниям между точками.Итак, здесь я ищу сравнение, основанное на временной сложности алгоритмов, связанное с анализом случаев, когда количество ребер увеличивается при фиксированном количестве вершин.Существует эталонное решение на Python это правильно и быстро, но я не вижу, в чем фундаментальная разница между двумя алгоритмами, стоящая за другими незначительными различиями в коде (также потому, что языки разные).

Я пробовал с рекурсия против очереди, с дерево против сетки / карты (смотрите мою историю на github) но до сих пор безуспешно.

Основная часть кода описана ниже.Он должен подпадать под алгоритм поиска в ширину (BFS), детали реализации которого приведены ниже только для завершения уже приведенного теоретического описания, поскольку стандартный BFS был адаптирован к нескольким целям, взвешенным ребрам и предварительной обрезке дерева.

Вот как я выполняю единственный шаг, с помощью которого я разрабатываю решение.

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

Обратите внимание, что это ограниченная версия TSP, где каждая вершина может иметь в качестве ограничения список предшественников.

Тот Самый fullGrid предполагается, что он содержит матрицу расстояний, и для меня это выглядит нормально, с точки зрения значений, которые он содержит, когда я его отлаживаю.Решатель переноса - это просто версия BFS, основанная на рекурсии или очереди.Опять же, меня интересуют не детали программирования, а понимание на концептуальном уровне, почему базовый алгоритм неприменим для явно поддающегося обработке ввода ("всего" 16 узлов).

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

Я нашел концептуальную проблему.В поиске типа BFS, когда необходима оптимизация, потому что длина очереди растет с критической скоростью, вы должны следить за посещенный Товары.

Цель состоит в том, чтобы избегайте добавления другого элемента в очередь , когда это уже присутствует a лучший товар там.

Просто немного кода, только для того, чтобы прояснить концепцию.

В моем случае Я добавил посещенная карта

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

и я ставлю в очередь только лучшие товары:

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

и пропускать самые худшие из них

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

Функция затрат

С теоретической точки зрения, BFS может гарантировать, что Первый возвращенное решение будет выглядеть следующим образом короткий насколько это возможно, только если мы можем предположить, что стоимость каждого хода равна 1.Вы могли бы свести приведенные выше примеры к этому, но наилучшим вариантом остается График где находится функция затрат представлен ребрами разная длина.С функции реальных затрат поиск кратчайшего пути становится все более сложным делом:здесь именно так и обстоит дело.Особенно потому, что вы должны оптимизировать также Космическая сложность (см. предыдущий параграф), избегая временной сложности в наихудшем случае $O(b^d)$, с $b$ являясь фактором ветвления и $d$ глубина залегания первого раствора.Вы описали сценарий , в котором $d$ хорошо известен в начале (количество ключей в лабиринте), в то время как упомянутый вами краевой случай получается с помощью большего $b$ (количество пересечений лабиринта)