最簡單的方法來解決迷宮沒有可變性

Question

學習了一些Scala和FP的好處後，我重新實現了我以前的CS任務，以更好地理解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]