Vikipeedia

Dünaamiline programmeerimine: erinevus redaktsioonide vahel

Sirvi ajalugu interaktiivselt
← Vanem muudatusUuem muudatus →
Eemaldatud sisu Lisatud sisu
VisuaalneVikitekst
P pisitoimetamine
1. rida:
'''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.
 
'''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|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.
 
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<sub>1</sub>a<sub>2</sub>...a<sub>m</sub> ja B =
b<sub>1</sub>b<sub>2</sub>...b<sub>n</sub> 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.
b<sub>1</sub>b<sub>2</sub>...b<sub>n</sub> pikim ühine
 
alamjada (''longest common subsequence'', LCS) on C, kui C on pikim sõne, mis on nii A kui B
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.▼
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.
argumente esimesest elemendist. Maatriksit c kasutatakse vahepealsete tulemuste hoidmiseks.
 
<source lang="c#">
76. rida ⟶ 61. rida:
</source>
 
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.
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.
 
<u>Seega on paljud dünaamilise programmeerimise algoritmid sarnased.</u>
 
=== Masinõppimises ===
Dünaamiline programmeerimine annab vahendid mõõta ühe sõna kaugust teisest, mis on [[Masinõppimine|masinõppimise]] ja [[Andmekaeve|andmekaeve]] jaoks infoajastul vajalik. On olemas dünaamilisel programmeerimisel põhinevad masinõppe algoritmid, nagu ''reinforcement learning''.
 
===Geoinformaatikas===
[[Dijkstra_algoritm|Dijkstra algoritmialgoritm]]i 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. Selliselt defineeritud matemaatilised mudelid koosnevad
järgmistest komponentidest:
 
▲== 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. Selliselt defineeritud matemaatilised mudelid koosnevad järgmistest komponentidest:
 
#Rida etappe selles otsustusprotsessis.
104. rida ⟶ 81. rida:
 
==Vaata ka==
*[[algoritm|Algoritm]]
*[[algoritmide loend|Algoritmide loend]]▼
<br />
 
▲[[algoritmide loend|Algoritmide loend]]
==Viited==
{{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==
*[http://biit.cs.ut.ee/~vilo/edu/2002-03/Tekstialgoritmid_I/Loengud/Loeng3_Edit_Distance/] Eestikeelsed seletused jadade võrdlemise meetodite kohta.
*[http://www.columbia.edu/~cs2035/courses/csor4231.F15/lcs.pdf] LCS lahti seletatud.
*[https://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf] Dünaamilise programmeerimise sissejuhatus.
*[http://www.bcs.org/upload/pdf/ewic_vs08_s2paper2.pdf] Pikim kasvav alamjada O(n log n) ajaga.
 
[[Kategooria:Programmeerimine]]
Pärit leheküljelt "https://et.wikipedia.org/wiki/Dünaamiline_programmeerimine"