algorithm - 解决没有可变性的迷宫的最简单方法

Question

在学习了一些 Scala 和 FP 的好处之后，我正在重新实现我之前的一些 CS 作业，以更好地理解 FP。然而，我得到了一项似乎用 FP 实现的任务（或至少是微不足道的翻译）。

在解决简单的 2D 迷宫时，有必要记住访问过哪些节点。但是，如果没有共享状态，每个递归调用如何知道其他递归调用检查了哪些节点？我可以将迷宫作为参数传递给每个递归调用，并返回一个包含访问过的地方的新迷宫，但这似乎计算量太大，无法在每个递归调用中复制整个迷宫。是否需要更高级的方法来实现不可变迷宫求解器？

Answer 1

您可以传递包含访问节点的集合（如果节点本身在您的设置中具有可比性，则可以传递它们的 ID/名称）。将项目添加到不可变集合通常需要O(log n)，因此检查元素是否包含在集合中。所以这比复制迷宫要便宜得多。

Answer 2

也许您注意到我之前的答案已被删除。虽然我是在开玩笑，但同时也只是暗示“计算机显示所有死角为红色，连接入口和出口的路径为绿色”，同时也隐喻了我所理解的功能范式 - 一种包含预先计算的确定性。鉴于我的理解和知识有限，我在 Haskell 中研究了一个避免递归深度搜索的示例，计算 4x5 迷宫的路径，给定一个数组，其中迷宫中的每个单元（即每个数组元素）仅包含它可以连接到的单元格；-1 表示入口，-2 表示出口。（您可以在代码部分的顶部看到迷宫的轮廓。）我知道，更有经验的程序员可以做得更多更好。

                                  {-M A Z E-}
[E]=[ ]=[ ]=[ ] 
     |
[ ]=[ ]=[ ]=[ ]
     |       |
[ ] [ ]=[ ] [ ]
 |   |       |
[ ] [ ]=[ ]=[ ]
 |   |
[ ]=[ ]=[ ]=[E]

import Data.List
import Data.Maybe

--Each element in the maze lists the indexes of connected cells, '-1' for entrance, '-2' for exit
maze = [[-1,1],  [0,2,5],     [1,3],   [2],
        [5],     [4,6,1,9],   [5,7],   [6,11],
        [12],    [5,13,10],   [9],     [7,15],
        [8,16],  [14,9,17],   [13,15], [14,11],
        [12,17], [13,16,18],  [17,19], [18,-2]]

maze' = [[-1,1],  [0,2],    [1,3],   [2,7],
         [8,5],   [4,6],    [5,7],   [3,6],
         [4,9],   [8,10],   [9,11],  [10,15],
         [16,13], [12,14],  [13,15], [11,14],
         [12,17], [16,18],  [17,19], [18,-2]]

index a = fromJust $ elemIndex a maze
indexes a = map (index) a
areConnected index_a index_b = elem index_a (maze !! index_b)

isStart a  --(a :: cell)
  | elem (-1) a = True
  | otherwise   = False

isEnd a  --(a :: cell)
  | elem (-2) a = True
  | otherwise   = False

hasStart a   --(a :: [cell])
  | isStart (head a) = True
  | otherwise    = False

hasEnd a   --(a :: [cell])
  | isEnd (last a) = True
  | otherwise    = False

isSequenced (w:x:xs) (y:z:zs) --includes possibility of overlap since we do not know how many cells comprise the solution
  | areConnected (index $ last xs) (index y)
    || last xs == y
    || let (b:c:cs) = reverse (w:x:xs) in [c,b] == [y,z] = True
  | otherwise                                            = False

removeBacktracks (x:xs)
  | (x:xs) == []                                     = []
  | xs == []                                         = [x]
  | x == head xs                                     = removeBacktracks xs
  | length xs > 1 && x == let (y:ys) = xs in head ys = removeBacktracks (tail xs)
  | otherwise                                        = x : removeBacktracks xs

--list dead ends
dead_ends = filter (\x -> length x==1 && find (==(-1)) x == Nothing) maze
dead_ends_indexes = map (index) dead_ends

connectedToDeadEnd (x:xs)
  | x `elem` dead_ends_indexes                   = True
  | not (x `elem` dead_ends_indexes) && xs == [] = False
  | otherwise                                    = connectedToDeadEnd xs

--list first from dead ends
first_from_dead_ends = filter (\x -> length x==2 && find (==(-1)) x == Nothing && connectedToDeadEnd x) maze

--create sequences
filtered = [l | l <- maze, not (elem l dead_ends) && not (elem l first_from_dead_ends)]
sequences_3 = [[a,b,c] | a <- filtered, not (isEnd a),
                         b <- filtered, not (isEnd b || isStart b), areConnected (index a) (index b),
                         c <- filtered, not (isStart c), a /= c, areConnected (index b) (index c)]

sequences_4 = [a ++ [b] | a <- sequences_3, not (hasEnd a), b <- filtered,
                          last a /= b, areConnected (index $last a) (index b)]

paths = take 1 [indexes $ concat [a, b, c, d, e] | a <- sequences, hasStart a,
                                                   b <- sequences, not (hasStart b || hasEnd b),
                                                   isSequenced a b,
                                                   c <- sequences, b /= c, not (hasStart c || hasEnd c),
                                                   isSequenced b c,
                                                   d <- sequences, c /= d, not (hasStart d || hasEnd d),
                                                   isSequenced c d,
                                                   e <- sequences, hasEnd e,
                                                   isSequenced d e]
                                                 where sequences 
                                                         | length filtered < 16 = sequences_3
                                                         | otherwise            = sequences_4

path = removeBacktracks $ head paths
main = print path
--outputs: [0,1,5,9,13,17,18,19]