试图在Haskell的函数创建一个高效的算法 [英] Trying to create an efficient algorithm for a function in Haskell
问题描述
我在寻找一个有效的多项式时间解决了以下问题：
I'm looking for an efficient polynomial-time solution to the following problem:
实现一个递归函数节点的xy用于计算（X，Y）个中定义为
Implement a recursive function node x y for calculating the (x,y)-th number in a number triangle defined as
g(x,y) = 0 if |x| > y
= 1 if (x,y) = (0,0)
= sum of all incoming paths otherwise
所有传入路径到节点的总和被定义为从根节点到所考虑的节点，所有可能的路径（X，Y）=（0，0）的值的总和，其中在每个节点（的x，y）的路径可以继续对角向下和向左（X-1，Y + 1），垂直向下（X，Y + 1），或对角向下和向右（X + 1，Y + 1）。的路径的节点的值被定义为沿着该路径上所有节点的总和，但不包括所考虑的节点。
The sum of all incoming paths to a node is defined as the sum of the values of all possible paths from the root node (x, y) = (0, 0) to the node under consideration, where at each node (x,y) a path can either continue diagonally down and left (x−1,y+1), straight down (x,y+1), or diagonally down and right (x+1,y+1). The value of a path to a node is defined as the sum of all the nodes along that path up to, but not including, the node under consideration.
在一些三角形的前几个条目在表中给出：
The first few entries in the number triangle are given in the table:
\ x -3 -2 -1 0 1 2 3
\
y \ _________________________
|
0 | 0 0 0 1 0 0 0
|
1 | 0 0 1 1 1 0 0
|
2 | 0 2 4 6 4 2 0
|
3 | 4 16 40 48 40 16 4
我试图找出一个天真的解决方案首先，这里是我有：
I am trying to work out a naive solution first, here is what I have:
node x y | y < 0 = error "number cannot be negative"
| (abs x) > y = 0
| (x == 0) && (y == 0) = 1
| otherwise = node (x+1) (y-1) + node x (y-1) + node (x-1) (y-1)
每当我运行此我得到的：
Whenever I run this I get:
的 * 的异常：堆栈溢出？
推荐答案
我相信你的问题是比较复杂一点比你的例子code暗示。首先，我们要明确一些定义在这里：
I believe your problem is a bit more complicated than your example code suggests. First, let's be clear about some definitions here:
让 pathCount XY 是，在（X，Y）结束路径的数量。我们有
Let pathCount x y be the number of paths that end at (x, y). We have
pathCount :: Int -> Int -> Integer
pathCount x y
| y == 0 = if x == 0 then 1 else 0
| otherwise = sum [ pathCount (x + d) (y - 1) | d <- [-1..1]]
现在，让我们 pathSum XY 是所有结束（X，Y）路径的总和。我们有：
Now let's pathSum x y be the sum of all paths that end in (x, y). We have:
pathSum :: Int -> Int -> Integer
pathSum x y
| y == 0 = if x == 0 then 1 else 0
| otherwise = sum [ pathSum (x + d) (y - 1) + node x y * pathCount (x + d) (y - 1)
| d <- [-1..1] ]
有了这个帮手，我们终于可以定义节点XY 正确：
node :: Int -> Int -> Integer
node x y
| y == 0 = if x == 0 then 1 else 0
| otherwise = sum [ pathSum (x + d) (y - 1) | d <- [-1..1]]
这个算法，因此是指数时间在其目前的形式。但是，我们可以将记忆化作出补充二次数。该 memoize的 包就Hackage使得这个简单如饼图。完整的例子：
This algorithm as such is exponential time in its current form. We can however add memoization to make the number of additions quadratic. The memoize package on Hackage makes this easy as pie. Full example:
import Control.Monad
import Data.List (intercalate)
import Data.Function.Memoize (memoize2)
node' :: Int -> Int -> Integer
node' x y
| y == 0 = if x == 0 then 1 else 0
| otherwise = sum [ pathSum (x + d) (y - 1) | d <- [-1..1]]
node = memoize2 node'
pathCount' :: Int -> Int -> Integer
pathCount' x y
| y == 0 = if x == 0 then 1 else 0
| otherwise = sum [ pathCount (x + d) (y - 1) | d <- [-1..1]]
pathCount = memoize2 pathCount'
pathSum' :: Int -> Int -> Integer
pathSum' x y
| y == 0 = if x == 0 then 1 else 0
| otherwise = sum [ pathSum (x + d) (y - 1) + node x y * pathCount (x + d) (y - 1)
| d <- [-1..1] ]
pathSum = memoize2 pathSum'
main =
forM_ [0..n] $ \y ->
putStrLn $ intercalate " " $ map (show . flip node y) [-n..n]
where n = 5
输出：
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0
0 0 0 2 4 6 4 2 0 0 0
0 0 4 16 40 48 40 16 4 0 0
0 8 72 352 728 944 728 352 72 8 0
16 376 4248 16608 35128 43632 35128 16608 4248 376 16
正如你所看到的算法的数字的大小将走出手中相当快。所以运行时的没有的为O（n ^ 2），而算术运算的数量。
As you can see the algorithm the size of the numbers will get out of hands rather quickly. So the runtime is not O(n^2), while the number of arithmetic operations is.
这篇关于试图在Haskell的函数创建一个高效的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
