这个输入为什么我的算法版本如此慢？

Question

这里我正在尝试进行两种简单的算法的比较，解决对称的旅行推销员问题，找出了没有启发式的支持的最佳解决方案。我显示（或只是引用）两个算法的代码，只能更好地指定实现细节，这可能与比较相关。 我写了我的 f＃code 解决代码中的出现第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 我尝试过递归与队列，与树vs grid / map （见我的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可以保证返回的 Fi RST 解决方案将作为短，仅当我们可以假设每一个举动都有一个成本为1.您可以将上述示例降低到该方面，但最佳拟合仍然是成本函数的图形由不同的长度。 随着<强大>实际成本函数查找最短路径变得更加介入：这正是这里的情况。特别是因为您必须优化空间复杂性（请参阅上一段），避免 $ o（b ^ d）$ < / span>，带 $ b $ 作为分支因子和 $ d $ 第一个解决方案的深度。您已经描述了一个场景，其中 $ d $ 在开始时众所周知（迷宫中的键数），而您提到的边缘案例是由更大的<跨越类=“Math-Container”> $ B $ （迷宫的交叉数）