贪婪算法的改进 [英] Improvement of the Greedy Algorithm
问题描述
我一直使用哈斯克尔（试图扩大我的不同范式的理解）一个抽象的国际象棋的算法，我已经打了，我一直在琢磨一下几个星期是一个挑战。
I've been working on an abstract chess algorithm using Haskell (trying to expand my understanding of different paradigms), and I've hit a challenge that I've been pondering about for weeks.
下面的问题：
由于电路板（再由整数列表清单psented $ P $;每个 再$ P $整数psents随后的点值），尺寸为n×n个， 确定提供了最高分的路径。如果出现平局 最佳路径，返回它们的任何。
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.
的规则是：
-
您可以开始在首行的任何地方
You may start anywhere on the top row
您可以移动一格的时间，无论是直线向下，向下，向左（对角线），或右下方（对角线）。
You may move one square at a time, either straight down, down-left (diagonal) , or down-right (diagonal).
输出必须是整数的元组。
The output must be a tuple of integers.
第一个元素是一个列表重新presenting列与行，以及第二元件是一个点的总数。例如。对于上述板，最好的解决办法是从左上角（5）旅行，走对角线的其余步骤（直到20点多）。这将导致元组（[1,2,3,4]，29）。
First element is a list representing the columns vs. row, and the second element is the total number of points. Eg. for the above board, the best solution is to travel from top-left (5) and go diagonally for the remaining steps (until the 20 point square). This would result in the tuple ([1,2,3,4], 29).
请记住，这是所有在Haskell所以它是一个功能性范式递归问题。起初，我想使用贪心算法，也就是选择在R1的最高值，并通过对比未来3的可能性递归;选择最高3然而，垮台是贪心算法没有看到下一行的潜在未来的能力。
Remember, this is all in Haskell so it is a functional-paradigm recursive problem. At first, I was thinking about using the greedy algorithm, that is, choosing the highest value in r1, and recursing through comparing the next 3 possibilities; choosing the highest of the 3. However, the downfall is that the greedy algorithm doesn't have the ability to see potential ahead of the next row.
我会如何呢？我不是在寻找code本身，因为我喜欢解决我自己的事情。然而，伪code或者一些算法的指导会大大AP preciated！
How would I go about this? I'm not looking for code per se, since I enjoy solving things on my own. However, pseudocode or some algorithmic guidance would be much appreciated!
推荐答案
我看到了同一主题的previous问题，我开始工作就可以了。
当你不希望直接的解决方案，我可以为你提供我的反思你的问题，我想这可以帮助你。
I saw your previous question on the same topic, and I start to work on it.
As you doesn't want the direct solution, I can provide you my reflexion about your problem, I guess it could help you.
一些基本属性：
1.运动的人数常是伊盖尔到列表中的 M =长度A 的长度
2.出发点的数量伊盖尔到列表头的长度 N =长度（头A）
3.目前的位置永远不会为负，则：
- 如果当前位置是伊盖尔为0，你可以走下来，右
- 否则你可以去左，下，右
Some basic property :
1. The number of movement is alway egal to the length of the list m = length A
2. The number of starting point is egal to the length of the head of the list n = length (head A)
3. The current position could never be negative, then :
- if the current position is egal to 0 you can either go down or right
- else you can go to left, down or right
这导致我们这个伪code
Which lead us to this pseudo code
generate_path :: [[Int]] -> [[Int]]
generate_path [] = [[]]
generate_path A = ... -- You have to put something here
where
m = length A
n = length (head A)
这东西看起来应该像什么，因为这
This things should look like something as this
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 +列表COM prehension + !! ，发挥
In fact keeping all of this in mind and adding the (!!) operator, we shouldn't be so far of the solution. To convince you play with A + list comprehension + !!, as
[A !! x !! y | x <- [1..2], y <- [0..2]] -- I take random range
或与其他版本的玩法：
Or play with another version :
[[A !! x !! y | x <- [1..2]] | y <- [0..2]]] -- I take random range
其实你有两个递归主要的一个工作参数n =长度（头A），你重复从0到（n-1）（N-1）检索结果，这个递归嵌入式同样的动作另一个在米其工作，重复从0相同的动作，以（M-1）。
In fact you have two recursion the main one working on the parameter n = length (head A), you repeat the same action from 0 to (n-1) at (n-1) retrieve the result, this recursion embedded another one which work on m, repeat the same action from 0 to (m-1).
希望它能帮助。 祝你好运。
Hope it help. Good luck.
这篇关于贪婪算法的改进的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
