Haskell迷宫求解算法

Question

我正在尝试根据 Haskell 中以下链接中描述的算法实现迷宫求解器。

http://www.cs.bu.edu/teaching/alg/maze/

我是 haskell 和函数式编程的新手，我基本上尝试按照链接中的描述编写算法代码，我尝试在线浏览许多其他资源，但我被困在目标到达时停止行走的部分(它不会停止，它会返回原点)到达了，我无法取消标记迷宫中的错误位置。

迷宫的样子

.########
.......#.
#.####..#
#.#######
...#.G...
##...####
#..######

我的代码如下

       findPath :: Int->Int->Maze->(Bool,Maze)
       findPath x y maze
            | not (isSafe maze x y) = (False,maze)
            | isChar maze x y 'G' = trace ("Solution: "++ show maze)(True,maze)
            | isChar maze x y '#' = (False,maze)
            | isChar maze x y '!' = (False,maze)
            | fst walkNorth = (True,markedList)
            | fst walkEast = (True,markedList)
            | fst walkSouth = (True,markedList)
            | fst walkWest = (True,markedList)
            | otherwise = (False,unMarkedList)
                where markedList = replaceCharInMaze maze x y '+'
                      unMarkedList = replaceCharInMaze maze x y '!'
                      walkNorth = findPath x (y-1) markedList
                      walkEast = findPath (x+1) y markedList
                      walkSouth = findPath x (y+1) markedList
                      walkWest = findPath (x-1) y markedList

isSafe 函数只是检查边界，isChar 只是在给定的 x,y 位置匹配字符，replaceCharInMaze 函数用提供的字符替换 x,y 位置的字符。

isSafe :: [String]->Int->Int->Bool
isSafe list x y
    | y >= 0 && y < length (head list) && x >= 0 && x < length list && (isChar list xy '.' || isChar list x y 'G') = True
    | otherwise = False

所以，我有两个问题

1. 我无法将在 Otherwise 情况下完成的取消标记保留到下一个递归调用，我该如何继续保留迷宫的状态，以便即使是未标记的状态也是一部分解决方案？

2. 然后随着算法的进行，它会走到目标并回到起点，如何阻止这种情况发生？

由于我是 Haskell 和算法的新手，我查看了诸如状态 monad 之类的主题，这似乎是解决方案，但我不太确定是否继续进行，我还尝试查看其他堆栈溢出帖子，但找不到任何对我有帮助的东西。

trace语句中得到的迷宫输出如下

+++#..###..#.
.#+++#+++.##.
####+#+#+#-##
...#+++#+#...
.#.####++.##.
.#G+++++#....
.############
....####.....

但它并不止于此，它会回溯到原点并将输出打印为

+..#..###..#.
.#...#....##.
####.#.#.#.##
...#...#.#...
.#.####...##.
.#G.....#....
.############
....####.....

Answer 1

以下是使用您的示例运行程序时发生的情况。前四个守卫显然是假的，所以到那时并没有发生太多事情。它通过递归一次评估 walkNorth，以便发现 fst walkNorth 也是 False。然后它评估 walkEast，这需要一段时间，因为最终会导致目标。它发现 fst walkEast 为 True，因此它返回 (True,markedList)。重要的是要意识到返回对中的 markedList 只被“标记”一次(因此输出中只有一个“+”)。在通往目标的路上出现了许多“标记”，但从程序返回输出的地方看不到这些标记。每次将 markedList 传递给其中一个 walkXXX 函数时，您实际上是在创建一个新列表，带有一个附加标记，只能在函数调用中看到你把它传进去。你真正想要的是迷宫，在它被解决的地方有标记。在一天结束时，walkXXX 函数要么返回 (False,maze)，当在 XXX 方向行走没有到达目标(因为第 1 或第 3 guard 评估为 True)，或者 (True,maze) 如果它确实导致了目标(第二个守卫评估为 True)，在这种情况下，maze 在那个点将具有所有正确的标记。因此，不是为 fst walkXXX 情况返回 markedList，而是返回 snd walkXXX。即

    | fst walkNorth = (True,snd walkNorth)
    | walkEast = (True,snd walkEast)
    | walkSouth = (True,snd walkSouth)
    | walkWest = (True,snd walkWest)

你的第一个问题有点复杂。我想你想要的是将你的 walkXXX 定义更改为非常粗略的如下:

walkNorth = findPath x (y-1) markedList
walkEast = findPath (x+1) y (replaceCharInMaze markedList x (y-1))
walkSouth = findPath x (y+1) (replaceCharInMaze (replaceCharInMaze markedList x (y-1)) (x+1) y)

我会让你填写最后一个。如果您向东走，您就知道您已尝试向北走但没有找到目标，因此您可以取消标记它，等等。 (这不太行得通，至少因为它可能会尝试替换迷宫外的墙壁和角色，但想法是存在的。)

你似乎还不习惯Haskell 的不可变状态和频繁递归。其他一些事情(我不确定这些):我不认为你的 otherwise 案例曾经运行过，而且它实际上没有做任何事情——试着把它拿出来看看会发生什么；我也不认为您的 (True,markedList) 对中的 True 有任何效果——尝试将它们更改为 False。