algorithm - 贪心算法的改进

Question

我一直在使用 Haskell 研究抽象的国际象棋算法(试图扩展我对不同范式的理解)，并且我遇到了一个我已经思考了数周的挑战。

问题是:

Given a board (represented by a list of lists of integers; each integer represents a subsequent point value), with dimensions n x n, determine the path that provides the most points. If there is a tie for best path, return either of them.

具体情况如下:

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

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

一些基本属性:
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 + list comprehension + !!，如

[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) 检索结果的相同 Action ，这个递归嵌入另一个对 m 起作用的，从 0 到 (m-1) 重复相同的 Action 。

希望对您有所帮助。祝你好运。