5

我一直在使用 Haskell 研究一个抽象的国际象棋算法（试图扩大我对不同范式的理解），并且我遇到了一个我已经思考了几个星期的挑战。

这是问题所在：

给定一个尺寸为 nxn 的棋盘（由整数列表表示；每个整数代表一个后续的点值），确定提供最多点的路径。如果最佳路径存在平局，则返回其中任何一个。

以下是具体情况：

A = [[5,4,3,1],[10,2,1,0],[0,1,2,0],[2,3,4,20]]

呈现为：

R1: 5  4  3  1, R2: 10 2 1 0, R3: 0 1 2 0, R4: 2 3 4 20.

规则是：

  1. 您可以从第一行的任何位置开始

  2. 您可以一次移动一个方格，可以是直线向下、左下（对角线）或右下（对角线）。

  3. 输出必须是整数元组。

第一个元素是表示列与行的列表，第二个元素是点的总数。例如。对于上面的电路板，最好的解决方案是从左上角 (5) 开始，然后沿对角线走剩余的步骤（直到 20 点正方形）。这将导致 tuple ([1,2,3,4], 29)。

请记住，这一切都在 Haskell 中，所以它是一个函数范式递归问题。一开始我在想用贪心算法，也就是选择r1中的最大值，然后通过比较接下来的3种可能性进行递归；选择 3 中的最高值。然而，缺点是贪心算法没有能力在下一行之前看到潜力。

我该怎么办？我不是在寻找代码本身，因为我喜欢自己解决问题。但是，非常感谢伪代码或一些算法指导！

4

4 回答 4

3

保留该单元格得分最高的行中每一列的路径列表。

您将从列表开始（在您的示例中）

[([1],5), ([2],4), ([3],3), ([4],1)]

然后，在检查下一行时，对于每一列，您选择前一行中可以到达该列的得分最高的路径，在这里，对于第二行，在第 1 列和第 2 列中，您将选择路径结尾在上一行的第 1 列和第 3 列中，您将选择在上一行中以第 2 列结尾的路径，在第 4 列中，在前一行中以第 3 列结尾的路径，这样会给您

[([1,1],15), ([1,2],7), ([2,3],5), ([3,4],3)]

对于第三行，[0,1,2,0]您将再次为前两列选择以第 1 列结尾的路径，为第三列选择以第 2 列结尾的路径，为第四列选择以第 3 列结尾的路径，

[([1,1,1],15), ([1,1,2],16), ([1,2,3],9), ([2,3,4],5)]

对于第四行，[2,3,4,20]您将为前三列选择以第 2 列结尾的路径，为最后一列选择以第 3 列结尾的路径，

[([1,1,2,1],18), ([1,1,2,2],19), ([1,1,2,3],20), ([1,2,3,4],29)]

然后，当您到达最后一行时，您选择总数最高的路径。

为什么有效：

让得分最高的路径在 column 结束c。最后一列上方的部分必须是在c-1, c, c+1倒数第二行的一列c中结束的得分最高的路径，因为最后一行中的列只能从这些路径中到达。

于 2013-02-05T16:01:10.033 回答
3

我看到了你之前关于同一主题的问题，我开始研究它。
由于您不想要直接的解决方案，我可以为您提供我对您的问题的反思，我想它可以帮助您。

一些基本性质：
1. 移动的次数总是等于列表的长度m = 长度 A
2. 起点的数量等于列表头的长度 n = 长度（头 A）
3.当前位置永远不会是负数，然后：
- 如果当前位置等于 0，您可以向下或向右
- 否则您可以向左、向下或向右

这导致我们这个伪代码 

generate_path :: [[Int]] -> [[Int]]
generate_path [] = [[]] 
generate_path A =  ... -- You have to put something here
        where 
              m = length A
              n = length (head A)

这东西应该看起来像这样 

move pos0 count0
    | count0 == 0 =   
        | pos0 == 0 = move (down count) ++ move (right count)  
        | otherwise = move (left count) ++ move (down count) ++ move (right count)  
            where 
                count = count0 - 1
                down  = position0 
                left  = position0 - 1
                right = position0 + 1

事实上，牢记所有这些并添加(!!)运算符，我们不应该走得太远。说服你玩A + 列表理解 + !! ， 作为 

[A !! x !! y | x <- [1..2], y <- [0..2]] -- I take random range

或者玩另一个版本： 

[[A !! x !! y | x <- [1..2]] | y <- [0..2]]] -- I take random range

实际上，您有两个递归，主要是处理参数 n = length (head A)，您在 (n-1) 处重复从 0 到 (n-1) 的相同操作，检索结果，此递归嵌入另一个在 m 上工作，从 0 到 (m-1) 重复相同的动作。

希望它有所帮助。祝你好运。

于 2013-02-05T16:05:31.867 回答
3

最好的解决方案不是自上而下的贪心算法，而是从最后一行开始向上工作的方法：

import Data.Function
import Data.List

-- All elements of Board are lists of equal lengths
-- valid b = 1 == length (group (map length b))
type Value = Int
type Board = [[Value]]
type Index = Int
type Result = ([Index], Value)

p :: Board
p = [[5,4,3,1],[10,2,1,0],[0,1,2,0],[2,3,4,20]] 

best_from :: Board -> Result
best_from [] = undefined
best_from xs | any null xs = undefined
best_from b = best_of . best_list $ b

best_list :: Board -> [Result]
best_list b = foldr1 layer (map label b)
  where label = zipWith (\index value -> ([index],value)) [1..]
        layer new rest =  zipWith (\(i1,v1) (i2,v2) -> (i1++i2, v1+v2)) new best
          where temp = head rest : map best_pair (zip rest (tail rest))
                best = map best_pair (zip temp (tail rest)) ++ [last temp]

best_pair :: (Result,Result) -> Result
best_pair (a@(_,a1), b@(_,b1)) | a1 >=b1 = a
                               | otherwise = b

best_of :: [Result] -> Result
best_of = maximumBy (compare `on` snd)

main = do
  print (best_from p)

如果有一行就很容易解决。因此，这会将每一行转换为具有简单 [#] 解决方案路径的 Result 列表。

给定一行rest下方的谜题，new然后添加行就是从（通过检查向下、左下、右下）new找到解决方案并与行结合的问题。bestrestnew

这使得foldr, 或这里foldr1成为自然结构。

于 2013-02-05T23:46:20.220 回答
0

我选择了一条不同的道路，没有双关语的意思。我列出了允许的索引组合并将板映射到它们。也许有人可以找到一种方法将其推广到任何规模的董事会。

import Data.List
import Data.Ord
import Data.Maybe

a = [[5,4,3,1],[10,2,1,0],[0,1,2,0],[2,3,4,20]]
r1 = a !! 0
r2 = a !! 1
r3 = a !! 2
r4 = a !! 3

i = [0,1,2,3]
index_combinations = [[a,b,c,d] | a <- i, b <- i, c <- i, d <- i, 
                      abs (b-a) < 2, abs (c-b) < 2, abs (d-c) < 2]

mapR xs = [r1 !! (xs !! 0), r2 !! (xs !! 1), 
           r3 !! (xs !! 2), r4 !! (xs !! 3)]

r_combinations = map mapR index_combinations
r_combinations_summed = zip r_combinations $ map (foldr (+) 0) r_combinations

result = maximumBy (comparing snd) r_combinations_summed
path = index_combinations !! fromJust (elemIndex result r_combinations_summed)
于 2013-02-06T04:16:31.940 回答