树状结构中的递归

Question

作为一个学校项目，我必须使用回溯方法在迷宫中找到解决路径，通常我没有线性问题的递归求解算法，但是当涉及到多个选择/路径时，我不会不知道如何找到一种解决方案。

问题参数：

• 以矩阵表示的迷宫，它具有到达同一终点的多种方法
• 起点

使用的语言：

• F＃

问题示例

00000000000 S1 000000000 111111 0000 1 0 1 00 11E00 1111111 000 1 000 1 00000 1111111 000 1 00 1 000000 1 00 1 00000000000000

0：墙壁1：路径E：终点S：起点

为了使其易于阅读，我对路径进行了高亮处理

部分代码：

member private this.solve(x,y) =
        (*let mutable seen = []
        let rec checkSeen(x,y,seen) = 
            match seen with
            | [] -> false
            | p::xs -> if (x,y) = p then true else checkSeen(x,y,xs)*)
        let rec sol(x,y,path: (int * int) list) =
            if (x,y) = this.endPoint then
                path
            else
                if this.checkPoint(x+1,y) then
                    sol(x+1,y,path)
                if this.checkPoint(x-1,y) then
                    sol(x-1,y,path)
                // other ifs
        sol(x,y,[])

除了代码（如果您愿意并提供给我），我想更多地了解递归和树状结构背后的逻辑。

Answer 1

您当前的方法看起来还可以。但是，因为您要进行深度优先搜索，所以您遇到的主要问题是，没有什么可以阻止您陷入像[(1,1);(1,2);(1,1);...]这样的无限长路径的困扰，而不是进入更具生产力的路径。为避免这种情况，您可以扫描路径以查看建议的下一个点是否已经存在（这在列表的长度上最多花费时间是线性的，这对于较小的问题大小可能是合适的），也可以传递访问点集作为递归函数的附加参数（应该允许更快的成员资格查询）。

您遇到的另一个问题是，您没有任何方法可以合并不同分支的结果。一种简单的方法是将内部函数的返回类型更改为选项类型，并从顶部Some(path)返回if并将其他重写为类似的形式

[x, y+1
 x, y-1
 x+1, y
 x-1, y]
|> List.tryPick (fun (x',y') -> if this.checkPoint(x',y') then 
                                    sol(x', y', (x,y)::path)
                                else None)

这是递归地尝试每个可能的方向，并返回第一个成功的方向。由于这是深度优先的搜索，因此不一定会返回最短路径。您还可以轻松创建一个变体，该变体返回所有可能路径的列表，而不是使用选项（最大的更改是使用List.collect而不是List.tryPick），在这种情况下，您可以从列表中选择最短的解决方案您想要的，尽管这样做会进行很多中间计算。
更复杂的更改是切换到广度优先搜索而不是深度优先搜索，这将使您很容易返回最短路径。从概念上讲，这是一种跟踪所有“可见”点的最短路径的方法（以[S,[]]开头，以及尚未探索其子项的一组点（再次以[然后，只要有要探索的点，就收集其所有不同的子代；对于每个尚不知道路径的子代，添加路径并将其放入下一组要探索的子代中。