Dünaamiline programmeerimine, põhimõtted

Programmiülesannete optimaalse lahenduse valimiseks on mõnikord vaja läbi viia arvukalt andmekombinatsioone, mis laadivad personaalarvuti mälu. Sellised meetodid hõlmavad näiteks programmeerimismeetodit "jagada ja vallutada". Sellisel juhul näeb algoritm ette ülesande eraldamise üksikutesse väikestesse alamülesannetesse. Seda meetodit kasutatakse ainult juhul, kui väikesed alamülesanded on üksteisest sõltumatud. Selleks et vältida ebavajaliku töö tegemist juhul, kui alamülesanded on üksteisest sõltuvad, kasutatakse 1950ndatel Ameerika R. Bellmani poolt välja pakutud dünaamilist programmeerimismeetodit.

Meetodi olemus

Dünaamiline programmeerimine seisneb n-mõõtmelise probleemi optimaalse lahenduse määramises, jagades selle n eraldi sammud. Igaüks neist on alamülesanne ühe muutuja suhtes.

Selle lähenemisviisi peamiseks eeliseks võib pidada, et arendajad tegelevad n-dimensioonilise probleemi asemel üheteistmiliste optimeerimisülesannetega alamülesannete täitmisel ja põhitöö ülesanne läheb "alt ülespoole".

Soovitav on rakendada dünaamilist programmitööd juhtudel, kui alamülesanded on omavahel seotud, st Omavad ühiseid mooduleid. Algoritm annab lahenduse igale alamülesannetele üks kord ja vastused salvestatakse eraldi tabelisse. See muudab vastuse arvutamiseks sarnase alamülesande täitmisel uuesti uuesti.

Dünaamilise programmitöö ülesanne lahendab optimeerimise probleemi . Selle meetodi autor R. Bellman sõnastas optimaalsuse põhimõtte: olenemata iga etapi algseisundist ja selles etapis kindlaksmääratud lahendusest, valitakse kõik alljärgnevad elemendid optimaalsena selle seisundi suhtes, mida süsteem võtab etapi lõpus.

Meetod parandab otsingute variantide või rekursioonide abil lahendatud ülesannete täitmist.

Probleemi algoritmi ülesehitus

Dünaamiline programmeerimine eeldab sellise ülesannete algoritmi loomist, kus ülesanne on jagatud kahte või enamasse alamülesandesse, nii et selle lahendus moodustatakse kõigis selles sisalduvatest alamülesannete optimaalsest lahendusest. Lisaks esineb vajadus kirjutada kordussuhe ja arvutada optimaalne parameetri väärtus probleemile tervikuna.

Mõnikord peate kolmanda sammuna täiendavalt mäletama mõnda lisateavet iga alamülesande edenemise kohta. Seda nimetatakse vastupidiseks.

Meetodi rakendamine

Dünaamilist programmeerimist kasutatakse siis, kui on kaks iseloomulikku tunnust:

• Alamülesannete optimaalsus;
• Kattuvate alamülesannete olemasolu probleemis.

Optimeerimisprobleemi lahendamine dünaamilise programmitöö meetodi abil on kõigepealt vaja kirjeldada lahenduse struktuuri. Probleem on optimaalne, kui probleemi lahendus koosneb tema alamülesannete optimaalsetest lahendustest. Sellisel juhul on soovitav kasutada dünaamilist programmeerimist.

Probleemi teine omadus, mis on selle meetodi jaoks oluline, on väike hulk alamülesandeid. Probleemi rekursiivne lahendus kasutab samu kattuvaid alamülesandeid, mille arv sõltub algse teabe suurusest. Vastus salvestatakse spetsiaalsesse tabelisse, programm salvestab aja, kasutades neid andmeid.

Eriti tõhus on dünaamilise programmitöö kasutamine, kui sisuliselt on vaja ülesandeid võtta järk-järgult. Näiteks kaaluge lihtsa näitena seadmete asendamise ja parandamise ülesandest. Oletame, et rehvi tootmistehase valamismasinas valmistatakse rehve korraga kahes erinevas vormis. Kui üks vormidest ebaõnnestub, peate masina lahti võtma. On selge, et mõnikord on teise vormi asendamine parem, et mitte masinat lahti monteerida, ja see vorm on järgmises etapis võimatu. Pealegi on mõlemad tegevusvormid lihtsam vahetada enne, kui nad hakkavad ebaõnnestuma. Dünaamilise programmitöö meetod määratleb nende vormide asendamise küsimuses parima strateegia, võttes arvesse kõiki tegureid: vormide toimimise jätkamise kasu, tühikäigul töötavate masinate kadu, tagasi lükatud rehvide maksumus jne.