贪心算法的改进

Question

我一直在使用Haskell编写一个抽象的国际象棋算法（尝试扩展我对不同范式的理解），但我遇到了一个问题，已经思考了几周。

问题如下：

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

具体要求如下：

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点方块。这将导致元组([1,2,3,4], 29)。

请记住，这是在Haskell中进行的，因此它是一个函数式递归问题。起初，我考虑使用贪心算法，即选择r1中的最高值，并通过比较接下来的3种可能性进行递归；选择其中的最高值。然而，贪心算法的缺点是没有看到下一行前面的潜力。

我该怎么做？我并不是在寻找代码，因为我喜欢自己解决问题。但是，伪代码或一些算法指南将非常感激！

- user2043598

---

这个问题是否可以使用 Dijkstra 算法的改编来解决呢？这些数字是图的节点，每个节点的值将是指向它的每条边的权重，我们可以将其与更长的路径进行比较，而不是与更短的路径进行比较。 - G. Bach

显然，对于一般情况，这种直觉是错误的，因为在一般图中，最长路径问题是NP难的（例如，请参见https://dev59.com/XGkv5IYBdhLWcg3wpCMz）。然而(!)，您的问题等同于在有向无环(!)图中找到最长路径，可以通过在节点的拓扑顺序中找到最长/最短路径来计算最长和最短路径。 - G. Bach

这是 https://dev59.com/oW3Xa4cB1Zd3GeqPk_-o 的重复吗？ - pat

Answer 1

在达到该单元格的最高分数的行中，保留每列路径的列表。

你可以从列表开始（在你的示例中）。

[([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]，你需要选择前三列以第二列结束的路径，并选择最后一列以第三列结束的路径。

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

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

为什么这样做可行：

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

- Daniel Fischer

Answer 2

我看到了你之前关于同一主题的问题，并开始着手解决它。
由于你不希望得到直接的解决方案，我可以提供我的思考过程，我想这可能会对你有所帮助。

一些基本属性：
1. 移动次数始终等于列表长度 m = A的长度
2. 起点数量等于列表头部的长度 n = head 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）上工作，您会重复相同的操作从0到（n-1），在（n-1）检索结果，这个递归嵌入了另一个递归，它在m上工作，重复相同的操作从0到（m-1）。希望这能帮到您。祝你好运。

- zurgl

Answer 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和一个新的row，则添加新的row只需要从rest中找到最佳解（向下、向左下、向右下检查），然后与新的row组合。

这使得foldr，或者在这里是foldr1成为自然的结构。

- Chris Kuklewicz

Answer 4

我选择了另一条路，无意冒犯。我列出了允许的索引组合，并将其映射到棋盘上。也许有人能够找到一种方法将其推广到任意大小的棋盘上。

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)

- גלעד ברקן

---

不错，但是index_combinations非常低效。例如，当a = 0和b = 2时，它将尝试所有c和d的组合，即使是在a和b之间的约束失败了。是否更好（虽然更冗长）在每个级别上自定义允许的范围，如[[a,b,c,d] | a <- [0..3], b <- [max 0 (a-1)..min 3 (a+1)], c <- [max 0 (b-1)..min 3 (b+1)], d <- [max 0 (c-1)..min 3 (c+1)]]？ - pat

看起来这可能是一个有用的调整，对于这个模型的更重的计算——感谢建议，我学到了新东西！看到算法的基准测试将会很有趣。 - גלעד ברקן