Haskell 中的回溯

Question

我必须遍历一个矩阵并说出每种类型有多少个“特征区域”。

特征区域被定义为值n或＞n的元素相邻的区域。

例如，给定矩阵：

0 1 2 2
0 1 1 2
0 3 0 0

有一个类型 1 的特征区域，它等于原始矩阵：

0 1 2 2
0 1 1 2
0 3 0 0

有两个类型 2 的特征区域：

0 0 2 2    0 0 0 0
0 0 0 2    0 0 0 0
0 0 0 0    0 3 0 0

和一个类型 3 的特征区域：

0 0 0 0 
0 0 0 0
0 3 0 0 

因此，对于函数调用：

countAreas [[0,1,2,2],[0,1,1,2],[0,3,0,0]] 

结果应为因为

[1,2,1]

我还没有定义 countAreas，所以当我的 visit 函数没有更多可能的方块来移动时，我会被卡住并且无法进行正确的递归调用。我是函数式编程的新手，对于如何在这里实现回溯算法我仍然摸不着头脑。看看我的代码，我能做些什么来改变它？

move_right :: (Int,Int) -> [[Int]] -> Int -> Bool
move_right (i,j) mat cond | (j + 1) < number_of_columns mat && consult (i,j+1) mat /= cond = True
               | otherwise = False

move_left :: (Int,Int) -> [[Int]] -> Int -> Bool
move_left (i,j) mat cond | (j - 1) >= 0 && consult (i,j-1) mat /= cond = True
               | otherwise = False

move_up :: (Int,Int) -> [[Int]] -> Int -> Bool
move_up (i,j) mat cond | (i - 1) >= 0 && consult (i-1,j) mat /= cond = True
               | otherwise = False

move_down :: (Int,Int) -> [[Int]] -> Int -> Bool
move_down (i,j) mat cond | (i + 1) < number_of_rows mat && consult (i+1,j) mat /= cond = True
               | otherwise = False

imp :: (Int,Int) -> Int
imp (i,j) = i


number_of_rows :: [[Int]] -> Int
number_of_rows i = length i

number_of_columns :: [[Int]] -> Int
number_of_columns (x:xs) =  length x

consult :: (Int,Int) -> [[Int]] -> Int
consult (i,j) l = (l !! i) !! j

visited :: (Int,Int) -> [(Int,Int)] -> Bool
visited x y = elem x y

add :: (Int,Int) -> [(Int,Int)] -> [(Int,Int)]
add x y = x:y

visit :: (Int,Int) -> [(Int,Int)] -> [[Int]] -> Int -> [(Int,Int)]
visit (i,j) vis mat cond | move_right (i,j) mat cond && not (visited (i,j+1) vis) = visit (i,j+1) (add (i,j+1) vis) mat cond
               | move_down (i,j) mat cond && not (visited (i+1,j) vis) = visit (i+1,j) (add (i+1,j) vis) mat cond
               | move_left (i,j) mat cond && not (visited (i,j-1) vis) = visit (i,j-1) (add (i,j-1) vis) mat cond
               | move_up (i,j) mat cond && not (visited (i-1,j) vis) = visit (i-1,j) (add (i-1,j) vis) mat cond
               | otherwise = vis

Answer 1

在这里使用数组类型而不是列表列表会对您有帮助吗？你仍然在进行函数式编程，只是使用了更好的数据结构。

如果适合您，您可以创建一个Array (Int,Int) Int。请参阅：

http:// hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/Data-Array-IArray.html

import Data.Array

...获取库。

Answer 2

我认为回溯实际上并不是您所追求的。在我看来，您的目标是让您的 visit 函数建立一个访问列表，因为它从满足某些条件的某个点找到矩阵中的所有连接元素。你需要考虑的是什么算法可以实现这一点。不要担心用函数式或命令式编程来表达它（还）。试想一下：该算法本质上是递归的吗？迭代？如果你在计算过程中停止它，你怎么知道算法下一步要做什么？您需要什么数据？

我现在不担心代码中的各种改进（使用 Array 或消除 if 语句等），您可以稍后再进行处理。您缺少的关键是可行的算法。