Haskell迷宫解决算法

Question

Haskell迷宫解决算法

haskellrecursionfunctional-programmingmaze

3

我正在尝试用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

所以，我有两个问题：

我无法将未标记的情况持久化到下一个递归调用中，我该如何持久化迷宫的状态，以便未标记的状态也成为解决方案的一部分？
随着算法的进行，它走到目标并返回起点，如何阻止这种情况发生？

由于我对Haskell和算法都很新，我查看了一些主题，例如状态单子，这似乎是解决方案，但我不太确定如何继续，我还尝试查看其他堆栈溢出帖子，但找不到任何有助于我的东西。

跟踪语句期间迷宫的输出如下：

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

但它并不止于此，它会追溯到原点并将输出打印出来。

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

- Pradeep Samuel Daniel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ackien · Accepted Answer

这是当您运行示例程序时会发生的情况。前四个保护条件明显为False，在那之前没有什么发生。它通过递归一次来评估walkNorth，以找出fst walkNorth也是False。然后它评估walkEast，需要一段时间，因为最终导致目标。它发现fst walkEast为True，因此返回(True，markedList)。重要的是要意识到返回的一对中的markedList只被标记了一次（因此输出中只有一个'+'）。在通往目标的路上，许多“标记”已经发生了，但是从程序返回其输出的位置看不到这些。每次将markedList传递到walkXXX函数中之一时，您实际上都在创建一个新列表，并带有附加标记，这仅在传递到其中一个函数调用中可见。实际上，您想要的是标记在解决问题的地方的迷宫。在一天结束时，如果向XXX方向行走不会导致目标（因为第1或第3个保护条件为True），则walkXXX函数返回(False，maze)，否则如果它导致目标（第2个保护条件为True），则返回(True，maze)，在这种情况下，此时的maze将具有所有正确的标记。因此，对于fst walkXXX情况，请返回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。