Вычисление рекуррентных отношений в Хаскеле - PullRequest
Новая
       27

Вычисление рекуррентных отношений в Хаскеле

4 голосов
/ 22 марта 2011

Привет, StackOverflow.

Допустим, у меня есть два следующих рекуррентных соотношения для вычислений S (i, j)

S_{i,j+1} = X_{PA}S_{i,j} + \frac{1}{2p}(iS_{i-1,j}+jS_{i,j-1}) \\ S_{i+1,j} = X_{PB}S_{i,j} + \frac{1}{2p}(iS_{i-1,j}+jS_{i,j-1})

Я хотел бы вычислить значения S (0,0) , S (0,1) , S (1,0) , S (2,0) и т. Д. ... асимптотически оптимальным образом.Несколько минут с карандашом и бумагой показывают, что он разворачивается в древовидную структуру, которую можно пересечь несколькими способами.Теперь маловероятно, что дерево будет полезно позже, поэтому сейчас я собираюсь создать вложенный список, например [[S(00)],[S(10),S(01)],[S(20),S(21),S(12),S(02)],...].Я создал функцию для создания плоского списка S (i, 0) (или S (0, j) , в зависимости от первого аргумента): 

osrr xpa p predexp = os00 : os00 * (xpa + rp) : zipWith3 osrr' [1..] (tail osrr) osrr
  where
    osrr' n a b = xpa * a + rp * n * b
    os00  = sqrt (pi/p) * predexp
    rp    = recip (2*p)

Я, однако, в растерянности, что делать дальше.

Ответы [ 2 ]

8 голосов
/ 23 марта 2011

Я бы предложил написать его в прямом рекурсивном стиле и использовать памятку для создания обхода: 

import qualified Data.MemoCombinators as Memo

osrr p = memoed
    where
    memoed = Memo.memo2 Memo.integral Memo.integral osrr'
    osrr' a b = ...  -- recursive calls to memoed (not osrr or osrr')

Библиотека создаст бесконечную таблицу для хранения значений, которые вы уже вычислили. Поскольку конструкторы memo находятся под параметром p, таблица существует для области действия p; то есть osrr 1 2 3 создаст таблицу для вычисления A (2,3), а затем очистит ее. Вы можете повторно использовать таблицу для определенного p, применив частично: 

osrr1 = osrr p

Теперь osrr1 поделится таблицей между всеми своими вызовами (что, в зависимости от вашей ситуации, может быть или не быть тем, что вы хотите).

1 голос
/ 23 марта 2011

Во-первых, должны быть некоторые граничные условия, о которых вы нам не сказали.

Как только вы их получите, попробуйте указать решение в виде рекурсивно определенного массива. Это работает до тех пор, пока вы знаете верхнюю границу для i и j. В противном случае используйте мемо-комбинаторы.

...