时间戳

首页 > 解决方案 > 树状结构中的递归

algorithm - 树状结构中的递归

问题描述

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

问题参数：

使用的语言：

代码输出：

████████████████████
█     █           ██
█ ███ ███ █████ █ ██
█   █   █   █   █ ██
█ █ █ █ █ █ █ ███ ██
█     █Sxxxx  █   ██
█ █████ █ █x███ █ ██
█     █   █xxx█   ██
█ █ █ ███████x██████
█ █ █   █   █x    ██
█ █ ███ █ █ █x███ ██
█   █   █ █  x█   ██
█ ███ ███ █ █x█ █ ██
█            x█   ██
███ █████████x███ ██
███ █     █xxx█ █ ██
███ █ █ █ █x███ █ ██
███   █ █xxx█     ██
█████████x██████████
█████████E██████████

#: 墙壁
 : 路径
E: 终点
S: 起点

部分代码：

let rec dfs(x,y,path,visited) =
        let rec checkVisited point visited = 
            match visited with
            | [] -> false
            | (x,y)::xs -> if point = (x,y) then true else checkVisited point xs
        let adjacents = [(x,y+1);(x+1,y);(x,y-1);(x-1,y)]
        for point in adjacents do
            if point = this.endPoint then
                this.solutionPath <- path
            else
                if checkVisited point visited = false && this.checkPoint point && this.isWall point = false then
                    dfs(fst(point),snd(point),(path@[point]),(visited@[(x,y)]))

这是在迷宫中搜索解决方案的另一种方式（mooore 优化）

let rec dfs(x,y,path) =
            // setting the point in the matrix visited (setting it to 'false')
            matrix.[y].[x] <- (fst(matrix.[y].[x]),false)
            // getting the adjacents of the point
            let adjacents = [(x,y+1);(x+1,y);(x,y-1);(x-1,y)]
            // iterate the adjacents
            for (x1,y1) in adjacents do
                // if the adjacent is the end point set the soultion path
                if (x1,y1) = this.endPoint then
                    this.solutionPath <- path
                else
                    // else check if the point is in the matrix and is not yet visited
                    if this.checkPoint(x1,y1) && snd(matrix.[y1].[x1]) <> false && this.isWall(x1,y1) = false then
                        // execute recursively the method in the point and add the current poisition to the path
                        dfs(x1,y1,((x1,y1)::path))
        dfs(x,y,[])

我成功了！如果您在执行此操作时遇到任何问题，我会为您提供帮助（即使是其他语言）！

标签： algorithmrecursionf#treemaze

解决方案

您当前的方法看起来基本没问题。但是因为您正在进行深度优先搜索，所以您遇到的主要问题是没有什么可以阻止您尝试无限长的路径[(1,1);(1,2);(1,1);...]而不是进入更有效率的路径。为避免这种情况，您可以扫描路径以查看建议的下一个点是否已经在其中（这需要时间最多与列表长度呈线性关系，这对于小型问题可能很好），或者传递访问点的集合作为递归函数的额外参数（应该允许更快的成员资格查询）。

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

[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,[]]，以及一组尚未探索其子级的点（再次从 开始[S]）。然后，只要有要探索的点，就收集他们所有不同的孩子；对于每个还没有已知路径的孩子，添加路径并将其放入下一组要探索的孩子中。

推荐阅读