贪心算法的改进

Question

我一直在研究使用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点方形).这将导致元组([1,2,3,4], 29).

记住,这一切都在Haskell中,因此它是一个功能范式的递归问题.起初,我正在考虑使用贪婪算法,即选择r1中的最高值,并通过比较接下来的3种可能性进行递归; 选择3中的最高值.然而,垮台是贪婪算法无法在下一行之前看到潜力.

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

Answer 1

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

一些基本属性：
1. 移动次数总是等于列表的长度m = length A
2. 起始点的数量等于列表头的长度n = length (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（头 A），你在 (n-1) 处从 0 到 (n-1) 重复相同的操作检索结果，这个递归嵌入了另一个递归对 m 进行操作，从 0 到 (m-1) 重复相同的动作。

希望有帮助。祝你好运。