我一直在使用 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.
规则是:
您可以从顶行的任意位置开始
您一次可以移动一格,直线向下、左下(对角线)或右下(对角线)。
输出必须是一个整数元组。
第一个元素是表示列与行的列表,第二个元素是总点数。例如。对于上面的棋盘,最好的解决方案是从左上角 (5) 开始,沿对角线走剩余的步数(直到 20 点正方形)。这将生成元组 ([1,2,3,4], 29)
。
请记住,这一切都在 Haskell 中,因此它是一个函数范式递归问题。一开始我想的是用贪心算法,即在r1中选择最大值,通过比较接下来的3种可能性递归;选择 3 个中最高的一个。但是,缺点是贪心算法无法在下一行之前看到潜力。
我该怎么做?我本身并不是在寻找代码,因为我喜欢自己解决问题。但是,伪代码或一些算法指导将不胜感激!
最佳答案
我看到你之前关于同一主题的问题,我开始研究它。
由于您不想要直接的解决方案,我可以为您提供我对您的问题的反射(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 。
希望对您有所帮助。 祝你好运。
关于algorithm - 贪心算法的改进,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14711328/