programare dinamica
TRANSCRIPT
Programare Dinamică
A fost descoperită in anii ’40 și ’50 de Richard Bellman.
Ce inseamnă de fapt, programare dinamică ?
Programare este un arhaism aici și are rol de planificare,intrun fel similar cu programare la medic, adica planificare la medic.Nu programare in sensul de scriere de cod.
Programare Dinamică
Planificare(ceva fix) dinamică (e un nonsens) ?
Cum adică să planific(atunci cand fac o programare la medic știu ora dinainte) dar, totuși, dinamic( ?? )?
Adică, ori tiu ora, ori nu o tiu ? ș ș
Programare Dinamică
Eu definesc (care este doar opinia mea personală, eu nu am copiat de nicaieri), formule de recursivitate ca fiind 2 tipuri.
• entitate • relaţieRecurenţa entitate este o formulă recursivă, care este definită de mi carea ș unei singure entităţi.Această entitate poate fi un om, un soldat, un monstru sau orice ce iţi poţi imagina Cealata recurenţa este mai subtila deoarece este data de o relaţie
1. Gândi i-vă la structura de date auxiliare (un tablou, o țmatrice 2D, 3D ), care are numele de C (de obicei)
2. Tu trebuie să faci Diagrama de săge iț 2.1 Marcheaza celulele unde po i vedea căț intră o singură sageată sau nu intră nici o sageată. 2.2 Acum marca i celelalte celule cu o formulă țminimă sau maximă,respectand săgeata.
3. Ca prin magie vei vedea că rezultatul va apărea în locul corespunzător,locului indicat în problemă
Programare Dinamicăpași ce trebuie urmaţi cand sunt implicate entitați
Frate, esti ticnit!! Nu inteleg nimica !!! ezi bland,fiule………….șVei intelege aceste reguli atunci când vei vedea un exemplu
Problema fermierului ce culegea mereA fost odată ca niciodată un biet fermier ce avea o
livadă cu mere codificată sub formă de matrice dreptunghiulară. El porne te de la col ul din stânga, sus al ș țmatricei i vrea să ajungă la col ul din dreapta jos ș ț și să colecteze numărul maxim de mere. Fermierul are numai dreptul de a face aceste 2 miscari ↓ , → (un pas in jos sau unul in dreapta).
Farmer.in Farmer.out Explicatie
3 31 2 11 3 11 1 1
8 În farmer.out,pe prima linie, va fi scris nr maxim de mere ăranul le poate ridica.In cazul acesta va fi țde 8, deoarece 1 +2 +3 +1 +1 = 81 2 11 3 11 1 1
Problema fermierului ce culegea mere1. Vom incepe prin a desena toate sagețile din toate celulele
2. Marcheaza celulele unde po i vedea căț intră ca nu intră nici o sageată.
3. Marcheaza celulele unde po i vedea căț intră doar o singura sageată.
Problema fermierului ce culegea mere
C[1][1] = A[1][1]C[i][1] = C[i-1][1] +A[i][1],i [2,n]C[1][j] = C[1][j-1] +A[1][j],j [2,m]
1 2 1
1 3 1
1 1 1
1 3 4
2 0 0
3 0 0
A C
IN ACEST PUNCT POT AJUNGE DOAR DIN POZITIA 1,1DECI VOR FI SIGUR MAXIM 3 MERE !!!!
IN ACEST PUNCT POT AJUGE DOAR DIN POZITIA 1,2 DECI SIGUR VOR FI 4 MERE
Problema fermierului ce culegea mere
3
2
DE UNDE SE MERITA SA FI VENIT IN
POZITIA 2,2
DIN POZITIA 1 2 CE ARE VALOAREA 3
Problema fermierului ce culegea mere
C[i][j] = MAX(C[i-1][j],C[i][j-1])+A[i][j]
1 2 1
1 3 1
1 1 1
1 3 4
2 6 0
3 0 0
A C
Eu consider ca este simplu de spus ca formula este aceasta:
6 = MAX (2 ,3) de unde poate venii + 3(A[2][2],pomul curent de unde culege mere )
Problema fermierului ce culegea mereC[i][j] = MAX(C[i-1][j],C[i][j-1])+A[i][j]
1 2 1
1 3 1
1 1 1
1 3 4
2 6 7
3 7 8
A C
Matricea completata va arata asa :
Propun un moment de meditație! Un moment in care sa privim matricea C,dupa aceaTrecem la slideul urmator
Problema fermierului ce culegea mere
1 2 1
1 3 1
1 1 1
1 3 4
2 6 7
3 7 8
A C
Un fenomen frumos este acela ca adesea poți reconstrui drumul, dar cum ?
Reconstructia drumului
Problema fermierului ce culegea mere
1. Vom incepe de la coada la cap si vom pleca inspre inceput, din 8 unde e mai normal sa fi venit ?
1 3 4
2 6 7
3 7 8
Problema fermierului ce culegea mere
1 2 1
1 3 1
1 1 1
1 3 4
2 6 7
3 7 8
A C
In cazul de fata oricum nu conteaza caci MAX(7,7) = 7 deci oricare 7 e bun ! Sa il luam pe celalat decat in exemplu
Acum, de unde era normal sa venim din 4 sau din 6?
Reconstructia drumului
Problema fermierului ce culegea mere
1 2 1
1 3 1
1 1 1
1 3 4
2 6 7
3 7 8
A C
Din 6
Acum, de unde era normal sa venim din 2 sau din 3?Si dupa acea din 1
Reconstructia drumului
Problema fermierului ce culegea mere
Multe carti de programare vorbesc despre “starestare” cand vorbesc de programare dinamică. Ce exact este acea stare este greu de definit dar vreau sa ne gandim ca fiecare miscare ii ia fermierului 1 minut. Unde va fi fermierul dupa 2 minute de exemplu ?
Nu pot sa cred , de fapt fermierul e in toate punctele marcate cu cercuri albastre deodată!
In universuri paralele e in toate punctele deodată
Programare Dinamică
Planificare fixă in mod dinamic
EXACT !!! FERMIERUL E IN TOATE CELE 3 PUNCTE DEODATA.
STIM UNDE E, DAR TOTUSI NU STIM.
Problema fermierului ce culegea mere
Am vorbit de universuri paralele , dar ce e starea?
Starea este culoarea diferită, deoarece din culoarea albastra sigur mergi in cea roșie și din cea roșie sigur in cea verde
Problema fermierului ce culegea mere
Ok, ok , ok dar la ce mă ajută “starea” acuma ? Problema era doară rezolvată ? La ce mai am nevoie de stare ?
Dar care e faza cu starea asta ?
Starea este un concept putin mai abstract, aici , acum, nu te ajută cu nimic. In viitor in schimb s-ar putea sa te ajute mult de tot
Din stare nu poti merge decat in alta stare și nu te poti intoarce inapoi in aceasi stare, decat intro stare mai mare, daca te-ai putea intoarce ar fi backtracking.
Gasesti starea, apoi relatia de recurență și te asiguri ca tranzitiile sunt aciclice. …adică ? E exact ce ai scris