Dünaamiline programmeerimine

Dünaamiline programmeerimine on algoritmiline probleemi lahendamise meetod, mis lahendab kõigepealt alamprobleemid ja salvestab need mingisse andmestruktuuri. Neid andmeid kasutatakse üldisema probleemi lahendamiseks. Ehk lahendatakse probleem, mis esialgu tundub keerulisem. Näiteks, kui on vaja leida pikim tee kaaludega graafis punktist A punkti B, siis leitakse pikimad teed kõikidesse punktidesse, mille põhjal leitakse lahendus esialgsele probleemile. On vaieldav, mis moodustab DP probleemi, sest DP ei ole nii selgelt määratud nagu näiteks lineaarne programmeerimine. Dünaamiliseks programmeerimiseks võib nimetada ka algoritme, mis kasutavad vahepealsete tulemuste hoidmiseks puhvreid. Dünaamilist programmeerimist ei rakendata ainult optimeerimise probleemide lahendamisel.

Ajalugu

Dünaamiline programmeerimine kui teooria sai alguse ligi 60 aastat tagasi Richard Bellmanni kirjutatud artiklist. Sellest ajast alates on dünaamiline programmeerimine kasutusel paljudes teadusharudes, nagu arvutiteadus, majandus, kaubandus jt.

Dünaamilise programmeerimise rakendusi

Bioinformaatikas

Sõnede A = a₁a₂...a_m ja B = b₁b₂...b_n pikim ühine alamjada (longest common subsequence, LCS) on C, kui C on pikim sõne, mis on nii A kui B alamjada. Näiteks kui ATTGCTA on jada, siis AGCA ja ATTA on alamjadad, aga TGTT ei ole. ATCTGAT ja TGCATA ühine alamjada on TCTA.

LCS on lihtsaim meetod jadade võrdlemiseks, kus on lubatud ainult sisestamised ja kustutamised. Niimoodi saab pikimat alamjada leida O(n*m) ajaga. Pole tõestatud, et kiiremaid algoritme selle probleemi jaoks ei leidu.

Järgnev kood on pikima ühtse alamjada leidmiseks C# keeles. Kusjuures ta hakkab lugema argumente esimesest elemendist. Maatriksit c kasutatakse vahepealsete tulemuste hoidmiseks.

public StringBuilder LCS(char[] m, char[] n)
        {
            int[,] c = new int[m.Length, n.Length];
            int m_ = m.Length;
            int n_ = n.Length;

            for (int i = 1; i < m.Length; i++)
            {
                for (int j = 1; j < n.Length; j++)
                {
                    if (m[i] == n[j])
                        c[i, j] = c[i - 1, j - 1] + 1;
                    else
                        c[i, j] = Math.Max(c[i, j - 1], c[i - 1, j]);
                }

            }

            return BacktrackLCSNorecursion(c, m, n, m.Length - 1, n.Length - 1, new 

StringBuilder());
        }

StringBuilder BacktrackLCSNorecursion(int[,] c, char[] m, char[] n, int i, int j, 

StringBuilder s)
        {
            while (i != 0 && j != 0)
            {
                if (m[i] == n[j])
                {
                    s.Append(m[i]);
                    i -= 1;
                    j -= 1;
                }
                else
                    if (c[i, j - 1] > c[i - 1, j])
                    {
                        j -= 1;
                    }
                    else
                        i -= 1;
            }
            return s;
        }

Tegemist on lahendusega väga üldisele probleemile. Sest näiteks kui antud jadad koosneks permutatsioonidest, kus ei ole ühtegi korduvat tähte, võiks selle probleemi lahendada ajaga O(n log n). Kui on antud n = 1, 4, 2, 5, 6, 8 ja m = 4, 1, 5, 8, 2, 6, siis saab n-i arvud panna m-i niimoodi (4,2)(1,1)(5,4)(8,6)(2,3)(6,5). Siis iga sellise paari (x,y) y= (2,1,4,6,3,5) pikim kasvav alamjada (Longest increasing subsequence) ongi pikim ühine alamjada ja seda saab leida O(n log n) ajaga. Samuti on pikim ühine kasvav alamjada (mitte segi ajada pikima kasvava alamjadaga) võimalik arvutada kasutades pikimat ühist alamjada.

Seega on paljud dünaamilise programmeerimise algoritmid sarnased.

Masinõppimises

Dünaamiline programmeerimine annab vahendid mõõta ühe sõna kaugust teisest, mis on masinõppimise ja andmekaeve jaoks infoajastul vajalik. On olemas dünaamilisel programmeerimisel põhinevad masinõppe algoritmid, nagu reinforcement learning.

Geoinformaatikas

Dijkstra algoritmi kasutatakse GIS rakendustes leidmaks optimaalset teed.

Mitmeastmeline otsustusprotsess kui matemaatiline mudel

Dünaamiline programmeerimine on mitmeastmelise otsustusprobleemi kehastus. Selles protsessis tuleb teha rida otsuseid, et saavutada soovitud tulemus. Kusjuures iga tehtud otsust mõjutab sellele otsusele eelnev otsus. Nii defineeritud matemaatilised mudelid koosnevad järgmistest komponentidest:

Rida etappe selles otsustusprotsessis.
Hulk, mis kirjeldab protsessi seisundit igal etapil.
Hulkade kogum, kus iga hulk sisaldab teostatavaid otsuseid vastavalt etapile ja seisundile.
Ülemineku funktsioon (transition function), mis kehastab seisundeid, kui need arenevad etappide käigus.
Eesmärk funktsioon (objective function), mis sätestab rea otsuste tasuvuse.

Vaata ka

Viited

Kirjandus

Moshe Sniedovich, 2011, Dynamic Programming Foundations and Principles ISBN 9780824740993
Neil C. Jones, Pavel A. Pevzner, 2004, An Introduction to Bioinformatics Algorithms ISBN 9780262101066

Välislingid

[1] Eestikeelsed seletused jadade võrdlemise meetodite kohta.
[2] LCS lahti seletatud.
[3] Dünaamilise programmeerimise sissejuhatus.
[4] Pikim kasvav alamjada O(n log n) ajaga.