Calcolo delle relazioni di ricorrenza in Haskell

StackOverflow https://stackoverflow.com/questions/5397578

  •  28-10-2019
  •  | 
  •  

Domanda

Saluti, stackoverflow.

Diciamo che ho due relazioni di ricorrenza seguenti per il calcolo 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})

Vorrei calcolare i valori S (0,0), S (0,1), S (1,0), S (2,0), ecc ... in modo asintoticamente ottimale. Pochi minuti con matita e carta rivelano che si svolge in una struttura treelike che può essere trasversata in diversi modi. Ora, è improbabile che Tree sarà utile in seguito, quindi per ora sto cercando di produrre una lista nidificata come [[S(00)],[S(10),S(01)],[S(20),S(21),S(12),S(02)],...]. Ho creato una funzione per produrre un elenco piatto di S (i, 0) (o S (0, J), a seconda del primo argomento):

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)

Tuttavia, sono in perdita come come procedere ulteriormente.

È stato utile?

Soluzione

Suggerirei di scriverlo in uno stile ricorsivo diretto e di usare la memorizzazione per creare il tuo attraversamento:

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')

La libreria creerà una tabella infinita per archiviare i valori che hai già calcolato. Perché i costruttori di memo sono sotto il p parametro, la tabella esiste per l'ambito di p; IE OSRR 1 2 3 creerà una tabella ai fini del calcolo A (2,3), quindi pulirla. Puoi riutilizzare la tabella per uno specifico p applicando parzialmente:

osrr1 = osrr p

Adesso osrr1 Condividerà la tabella tra tutte le sue chiamate (che, a seconda della tua situazione, possono o meno essere ciò che desideri).

Altri suggerimenti

Innanzitutto, ci devono essere alcune condizioni al contorno di cui non ci hai parlato.

Una volta che hai quelli, prova a dichiarare la soluzione come array definito in modo ricorsivo. Funziona fintanto che conosci un limite superiore su I e J. Altrimenti, usa i combinatori di memo.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top