de Meet Zaveri

O introducere în algoritmi (Partea II): Programare dinamică

O introducere in algoritmi programare dinamica
Fotografie de Helloquence pe Unsplash

Să presupunem că faceți unele calcule folosind o serie adecvată de intrări. Există unele calcule făcute la fiecare instanță pentru a obține un rezultat. Nu știți că ați întâlnit aceeași ieșire când ați furnizat aceeași intrare. Deci, este ca și cum ați face re-calculul unui rezultat care a fost obținut anterior printr-o intrare specifică pentru ieșirea sa respectivă.

Dar care este problema aici? Lucrul este că timpul tău prețios este irosit. Puteți rezolva cu ușurință problema aici ținând evidențe care mapează rezultatele calculate anterior. Cum ar fi utilizarea structurii de date adecvate. De exemplu, puteți stoca intrarea ca cheie și ieșirea ca valoare (parte a mapării).

Cei care nu își pot aminti trecutul sunt condamnați să-l repete. ~ Programare dinamică

Acum, analizând problema, stocați intrarea dacă este nouă (sau nu în structura de date) cu ieșirea respectivă. Altfel verificați acea cheie de intrare și obțineți rezultatul rezultat din valoarea sa. În acest fel, când faceți unele calcule și verificați dacă acea intrare a existat în structura de date respectivă, puteți obține direct rezultatul. Astfel putem raporta această abordare la tehnicile de programare dinamică.

Scufundare în programare dinamică

Pe scurt, putem spune că programarea dinamică este utilizată în primul rând pentru optimizarea problemelor, unde dorim să găsim „cel mai bun” mod de a face ceva.

Un anumit scenariu este ca și cum ar fi subprobleme care reapar, care la rândul lor au propriile subprobleme mai mici. În loc să încerce să rezolve acele subprobleme care reapar, din nou și din nou, programarea dinamică sugerează rezolvarea fiecăreia dintre subproblemele mai mici o singură dată. Apoi înregistrați rezultatele într-un tabel din care poate fi obținută o soluție la problema inițială.

De exemplu, Numere Fibonacci 0,1,1,2,3,5,8,13,… au o descriere simplă în care fiecare termen este legat de cei doi termeni dinaintea acestuia. Dacă F(n) este nal treilea termen al acestei serii, atunci avem F(n) = F(n-1) + F(n-2). Aceasta se numește a formula recursivă sau a relație de recurență. Este nevoie de termeni anteriori pentru a fi calculați pentru a calcula un termen ulterior.

1611981426 709 O introducere in algoritmi programare dinamica

Majoritatea problemelor de programare dinamică pot fi clasificate în două tipuri:

  1. Probleme de optimizare.
  2. Probleme combinatorii.

Problemele de optimizare vă așteaptă să selectați o soluție fezabilă, astfel încât valoarea funcției necesare să fie minimizată sau maximizată. Problemele combinatorii se așteaptă să vă dați seama numărul de modalități de a face ceva sau probabilitatea apariției unui eveniment.

O abordare de rezolvat: de sus în jos vs de jos în sus

Există următoarele două modalități principale de a rezolva problema:

De sus în jos: Începi de sus, rezolvând problema prin descompunerea ei. Dacă vedeți că problema a fost deja rezolvată, trebuie doar să returnați răspunsul salvat. Aceasta este denumită Memorizare.

De jos în sus: Începeți direct să rezolvați subproblemele mai mici care vă îndreaptă spre vârf pentru a obține soluția finală a acelei mari probleme. În acest proces, este garantat că subproblemele sunt rezolvate înainte de rezolvarea problemei. Aceasta poate fi numită Intabulare (algoritm de umplere a tabelelor).

În ceea ce privește iterația vs recursivitatea, de jos în sus utilizează iterația, iar de sus în jos utilizează recursivitatea.

1611981427 349 O introducere in algoritmi programare dinamica
Vizualizarea afișată în imagine nu este corectă. la cunoștințe teoretice, dar am afișat într-o manieră de înțeles

Aici există o comparație între o abordare naivă și o abordare DP. Puteți vedea diferența în funcție de complexitatea temporală a ambelor.

Memorizare: Nu uitați

Jeff Erickson descrie în notele sale, pentru numerele Fibonacci:

Motivul evident al lipsei de viteză a algoritmului recursiv este acela că calculează aceleași numere Fibonacci din nou și din nou.

O introducere in algoritmi programare dinamica
Din notele lui Jeff Erickson CC: http://jeffe.cs.illinois.edu/

Ne putem accelera considerabil algoritmul recursiv doar notând rezultatele apelurilor noastre recursive. Apoi îi putem căuta din nou dacă avem nevoie mai târziu de ei.

Memorizare se referă la tehnica de cache și reutilizare a rezultatelor calculate anterior.

Dacă utilizați memoizarea pentru a rezolva problema, o faceți menținând o hartă a subproblemelor deja rezolvate (așa cum am vorbit mai devreme despre cartografiere de cheie și valoare). Tu faci “de sus în jos”În sensul că rezolvați mai întâi problema„ de sus ”(care se repetă de obicei pentru a rezolva subproblemele).

Pseudocod pentru memoizare:

1611981427 473 O introducere in algoritmi programare dinamica

Deci, folosind recursivitatea, realizăm acest lucru cu o memorie suplimentară (de exemplu, aici) pentru a stoca rezultatele. Dacă există o valoare stocată în căutare, o returnăm direct sau o adăugăm la căutare pentru acel index specific.

Amintiți-vă că există o compensare a cheltuielilor suplimentare în raport cu metoda de întabulare.

Cu toate acestea, dacă doriți mai multe vizualizări pentru memorie, atunci vă sugerez să căutați acest video.

1611981427 330 O introducere in algoritmi programare dinamica
În mod de sus în jos.

Intabulare: completare sub formă de tabelă

Dar odată ce vedem cum se completează matricea (soluția memoizată), putem înlocui recursivitatea cu o buclă simplă care umple matricea în mod intenționat, în loc să ne bazăm pe recursiunea complicată pentru a o face pentru noi „accidental”.

1611981428 98 O introducere in algoritmi programare dinamica
Din notele lui Jeff Erickson CC: http://jeffe.cs.illinois.edu/

Tabelarea o face în “de jos în sus” Modă. Este mai simplu, calculează toate valorile. Necesită mai puține cheltuieli generale, deoarece nu trebuie să mențină cartarea și stochează date sub formă de tabel pentru fiecare valoare. De asemenea, poate calcula valori inutile. Aceasta poate fi utilizată dacă tot ce doriți este să calculați toate valorile pentru problema dvs.

Pseudocod pentru intabulare:

1611981428 533 O introducere in algoritmi programare dinamica
Pseudocod cu arborele Fibonacci

După cum puteți vedea pseudocodul (partea dreaptă) într-o imagine, acesta face iterație (adică bucle până la sfârșitul unei matrice). Pur și simplu începe cu fib (0), fib (1), fib (2), … Deci, cu abordarea tabelării, putem elimina nevoia de recursivitate și pur și simplu returnăm rezultatul cu un looping peste elemente.

Privind în urmă în istorie

Richard Bellman a fost omul din spatele acestui concept. El a venit cu asta când lucra pentru RAND Corporation la mijlocul anilor 1950. Motivul pentru care a ales acest nume „programare dinamică” a fost să ascundă munca de matematică pe care a făcut-o pentru această cercetare. Se temea că șefii săi se vor opune sau nu le vor plăcea niciun fel de cercetare matematică.

Bine, deci cuvântul „programare” este doar o referință pentru a clarifica că acesta a fost un mod de modă veche de planificare sau planificare, de obicei prin completarea unui tabel (într-un mod dinamic mai degrabă decât într-un mod liniar) de-a lungul timpului, mai degrabă decât dintr-o dată.

Înfășurându-se

Asta este. Aceasta este partea 2 a seriei de algoritmi pe care am început-o anul trecut. In al meu postarea anterioară, am discutat despre ce sunt algoritmii de căutare și sortare. Îmi cer scuze că nu am putut livra acest lucru într-un timp mai scurt. Dar sunt dispus să fac lucrurile mai rapide în următoarele luni.

Sper că ți-a plăcut și în curând voi căuta să adaug un al treilea din serie în curând. Codificare fericită!

Resurse:

Introducere în programare dinamică 1 Tutoriale și note | Algoritmi | HackerEarth
Imaginea de mai sus spune multe despre programarea dinamică. Deci, repetă lucrurile pentru care ai deja …www.hackerearth.comComunitate – Programare competitivă – Tutoriale de programare competitivă – Programare dinamică: de la …
Comunitate – Programare competitivă – Tutoriale de programare competitivă – Programare dinamică: de la începător la avansatwww.topcoder.com

https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Recuzită specială pentru Jeff Erickson și notele sale pentru algoritm – http://jeffe.cs.illinois.edu/

1611981428 511 O introducere in algoritmi programare dinamica