Programare dinamica

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.


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 ? ș ș


Planificare fixa in mod 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


3

2

DE UNDE SE MERITA SA FI VENIT IN

POZITIA 2,2

DIN POZITIA 1 2 CE ARE VALOAREA 3


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


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


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


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?



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



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ă


Planificare fixă in mod dinamic

EXACT !!! FERMIERUL E IN TOATE CELE 3 PUNCTE DEODATA.

STIM UNDE E, DAR TOTUSI NU STIM.


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


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


Matricea C este mereu in orice punct adevarată!! Nu are dreptul să fiefalsă in nici un punct.Nu, nici măcar la inceput sau cumva la sfarsit1 3 4

2 6 7

3 7 8

De aceea poti trece dintro stare in alta

Programare dinamica

Documents

Transcript of Programare dinamica