Programarea dinamică este un concept dezvoltat de Richard Bellman, un matematician și economist.
La acea vreme, Bellman căuta o modalitate de a rezolva probleme complexe de optimizare. Problemele de optimizare necesită să alegeți cea mai bună soluție dintr-un set de opțiuni.
Un exemplu de problemă de optimizare este problema vânzătorului călător. Scopul este de a găsi cel mai scurt traseu pentru a permite vânzătorului să viziteze fiecare oraș exact o dată și să se întoarcă în orașul de plecare.
Abordarea lui Bellman asupra acestor probleme a fost de a le împărți în sub-probleme mai mici și de a rezolva sub-problemele de la cea mai mică la cea mai mare. Apoi a stocat rezultatele sub-problemelor și le-a reutilizat pentru a rezolva sub-probleme mai mari. Aceasta este ideea principală din spatele programării dinamice.
Cuprins
Ce este programarea dinamică?
Programarea dinamică rezolvă problemele de optimizare, împărțindu-le în sub-probleme mai mici, rezolvând fiecare sub-problemă o dată și stocând soluțiile lor astfel încât să poată fi reutilizate și combinate pentru a rezolva problema mai mare. Problemele sunt rezolvate de la cel mai mic la cel mai mare, permițând reutilizarea soluțiilor.
Cum funcționează programarea dinamică?
Rezolvarea unei probleme folosind programarea dinamică implică următorii pași:
Pentru a vedea acest lucru în acțiune, calculăm al șaselea număr Fibonacci, F(6), folosind acest proces.
Mai întâi, definiți subproblemele care trebuie rezolvate.
F(n) = F(n-1) + F(n-2) pentru n > 1
Prin urmare: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Al doilea pas implică rezolvarea fiecărei sub-probleme folosind o funcție recursivă sau un proces iterativ. Rezolvăm sub-problemele de la cea mai mică la cea mai mare, reutilizand rezultatele de la sub-probleme mai mici. Acest lucru ne oferă următoarele:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Pe măsură ce rezolvăm fiecare dintre sub-probleme, stocăm soluțiile într-o matrice sau tabel, astfel încât să poată fi reutilizate în rezolvarea sub-problemelor mai mari, astfel:
Odată ce toate subproblemele au fost rezolvate, folosim soluțiile pentru a construi soluția problemei inițiale.
În acest caz, soluția problemei inițiale este al 6-lea număr Fibonacci, care se găsește prin însumarea rezultatelor lui F(5) și F(4), subprobleme identificate din cea mai mare problemă. Rezultatul ne dă 8.
Unde și de ce este folosită programarea dinamică?
Programarea dinamică este folosită în domeniile în care avem probleme care pot fi împărțite în sub-probleme mai mici, iar soluțiile acestora sunt folosite pentru a rezolva probleme mai mari.
Aceste domenii includ informatică, economie, matematică și inginerie. În informatică, este folosit pentru a rezolva probleme care implică secvențe, grafice și valori întregi și în programarea competitivă.
În economie, este folosit pentru a rezolva probleme de optimizare în finanțe, producție și alocarea resurselor. În matematică, programarea dinamică este folosită în teoria jocurilor, statistică și probabilitate, unde este folosită pentru a rezolva probleme de optimizare.
În inginerie, este folosit pentru a rezolva probleme în alocarea resurselor, programare, producție, comunicare și sisteme de control.
Există mai multe avantaje în utilizarea programării dinamice pentru a rezolva probleme de optimizare:
Când vine vorba de rezolvarea problemelor de optimizare, programarea dinamică este un instrument foarte util pentru a asigura eficiența soluțiilor.
Abordări utilizate în programarea dinamică
În programarea dinamică, sunt utilizate două abordări pentru a rezolva problemele de optimizare. Acestea sunt abordarea de sus în jos și abordarea de jos în sus.
Abordare de sus în jos
Această abordare este cunoscută și sub numele de memorare. Memorizarea este o tehnică de optimizare utilizată în principal pentru a face programele de calculator mai rapide, prin stocarea rezultatelor apelurilor de funcții în cache și returnarea rezultatelor din cache data viitoare când sunt necesare, în loc să le calculeze din nou.
Abordarea de sus în jos implică recursiunea și stocarea în cache. Recursiunea implică o funcție care se numește ea însăși cu versiuni mai simple ale problemei ca argument. Recursiunea este folosită pentru a împărți problema în sub-probleme mai mici și pentru a rezolva sub-problemele.
Odată ce o sub-problemă este rezolvată, rezultatul acesteia este stocat în cache și reutilizat ori de câte ori apare o problemă similară. De sus în jos este ușor de înțeles și implementat și rezolvă o sub-problemă o singură dată. Cu toate acestea, un dezavantaj este că ocupă multă memorie din cauza recursiunii. Acest lucru poate duce la o eroare de depășire a stivei.
Abordarea de jos în sus
Abordarea de jos în sus, cunoscută și sub numele de tabulare, elimină recursiunea, înlocuind-o cu iterație, evitând astfel erorile de depășire a stivei.
În această abordare, o problemă mare este împărțită în sub-probleme mai mici, iar soluțiile pentru sub-probleme sunt folosite pentru a rezolva problema mai mare.
Sub-problemele mai mici sunt rezolvate mai întâi de la cea mai mare la cea mai mică, iar rezultatele lor sunt stocate într-o matrice, matrice sau tabel, de unde și numele tabulare.
Rezultatele stocate rezolvă probleme mai mari care depind de sub-probleme. Rezultatul problemei inițiale este apoi găsit prin rezolvarea celei mai mari sub-probleme folosind valorile calculate anterior.
Această abordare are avantajul de a fi eficientă în memorie și timp prin eliminarea recursiunii.
Exemple de probleme care pot fi rezolvate prin programare dinamică
Următoarele sunt câteva probleme de programare care pot fi rezolvate folosind programarea dinamică:
#1. Problemă la rucsac
Sursa: Wikipedia
Un rucsac este o geantă făcută din pânză, nailon sau piele, de obicei legată pe spate și folosită de soldați și drumeți pentru a transporta provizii.
În problema rucsacului, vi se prezintă un rucsac și, având în vedere capacitatea de transport, vi se cere să alegeți articole, fiecare cu valoarea sa. Selecția dvs. ar trebui să fie astfel încât să obțineți valoarea totală maximă a articolelor culese, iar greutatea articolelor să fie mai mică sau egală cu capacitatea rucsacului.
Un exemplu de problema rucsacului este dat mai jos:
Imagineaza-ti ca mergi intr-o drumetie si ai un rucsac cu o capacitate de 15 kilograme. Aveți o listă de articole pe care le puteți aduce cu dvs., împreună cu valorile și greutățile acestora, așa cum se arată în tabelul de mai jos:
ArticolValoareGreutateCort2003Sac de dormit1502Soba501Mâncare1002Sticlă de apă100,5Trusă de prim ajutor251
Alegeți un subset de articole pentru a aduce astfel încât valoarea totală a articolelor să fie maximizată, în timp ce greutatea totală este mai mică sau egală cu capacitatea rucsacului, care este de 15 kilograme.
Aplicațiile din lumea reală ale problemei rucsacului implică selectarea titlurilor de valoare pe care să le adăugați la un portofoliu pentru a minimiza riscul și a maximiza profitul și găsirea celor mai puțin risipitoare modalități de a reduce materiile prime.
#2. Problemă de programare
O problemă de planificare este o problemă de optimizare în care scopul este alocarea optimă a sarcinilor unui set de resurse. Resursele pot fi mașini, personal sau alte resurse utilizate pentru a finaliza sarcinile.
Un exemplu de problemă de programare este prezentat mai jos:
Imaginați-vă că sunteți un manager de proiect responsabil de programarea unui set de sarcini care trebuie îndeplinite de o echipă de angajați. Fiecare sarcină are o oră de început, o oră de sfârșit și o listă de angajați care sunt calificați să o finalizeze.
Iată un tabel care descrie sarcinile și caracteristicile acestora:
Sarcină Ora de începereOra de sfârșitAngajați calificațiT1911A, B, CT21012A, CT31113B, CT41214A, B
Atribuiți fiecare sarcină unui angajat pentru a minimiza timpul total de finalizare.
Problema de programare poate fi întâlnită în industria prelucrătoare atunci când se încearcă optimizarea alocării resurselor, cum ar fi mașini, materiale, unelte și forță de muncă.
Poate fi întâlnit și în asistența medicală atunci când se optimizează utilizarea patului, a personalului și a materialelor medicale. Alte industrii în care poate apărea această problemă sunt managementul proiectelor, managementul lanțului de aprovizionare și educația.
#3. Problema vânzătorului călător
Sursa: Wikipedia
Aceasta este una dintre cele mai studiate probleme de optimizare care poate fi rezolvată folosind programarea dinamică.
Problema vânzătorului ambulant oferă o listă de orașe și distanțele dintre fiecare pereche de orașe. Vi se cere să găsiți cel mai scurt traseu posibil care vizitează fiecare oraș exact o dată și se întoarce la orașul de origine.
Un exemplu de problemă de vânzător ambulant este prezentat mai jos:
Imaginează-ți că ești un agent de vânzări care trebuie să viziteze un set de orașe în cel mai scurt timp posibil. Aveți o listă cu orașele pe care trebuie să le vizitați și distanțele dintre fiecare pereche de orașe, așa cum se arată în tabelul de mai jos:
OrașABCDEA010152030B100352515C153503020D202530010E301520100
Problema vânzătorului ambulant poate fi întâlnită în industria de agrement atunci când se încearcă planificarea rutelor pentru turiști, logistică la planificarea transportului de mărfuri, transportul la planificarea rutelor de autobuz și în industria vânzărilor, printre altele.
În mod clar, programarea dinamică are multe aplicații din lumea reală, ceea ce vă ajută să aflați mai multe despre ea.
Luați în considerare următoarele resurse pentru a vă expune cunoștințele despre programarea dinamică.
Resurse
Programare dinamică de Richard Bellman
Programarea dinamică este o carte a lui Richard Bellman, care a venit cu programarea dinamică și a dezvoltat-o în stadiile incipiente.
Cartea este scrisă într-un mod ușor de înțeles, care necesită doar cunoștințe de bază de matematică și calcul pentru a înțelege textul. În carte, Bellman introduce teoria matematică a unui proces de decizie în mai multe etape, care este cheia în programarea dinamică.
Cartea examinează apoi problemele de blocaj în procesele de producție în mai multe etape, teoremele de existență și unicitate și ecuația optimă a inventarului.
Cel mai bun lucru despre carte este că Bellman oferă exemple de multe probleme complexe în domenii precum logistica, teoria programării, teoria comunicării, economia matematică și procesele de control și arată modul în care programarea dinamică poate rezolva problemele.
Cartea este disponibilă în versiuni Kindle, hardcover și paperback.
Curs de master în algoritmi de programare dinamică
Acest curs de master în algoritmi de programare dinamică de la Udemy este oferit de Apaar Kamal, inginer software la Google, și Prateek Narang, care a lucrat și cu Google.
Cursul este optimizat pentru a ajuta cursanții să exceleze în competiția de programare, care prezintă o mulțime de probleme care necesită programare dinamică.
Pe lângă competitorii de programare, cursul este ideal pentru programatorii care doresc să-și îmbunătățească înțelegerea algoritmilor și oamenii care se pregătesc pentru interviuri de programare și runde de codare online.
Cursul, care are o durată de peste 40 de ore, acoperă programarea dinamică în profunzime. Cursul oferă mai întâi o reîmprospătare a conceptelor precum recursiunea și backtracking.
Apoi acoperă programarea dinamică în teoria jocurilor, șiruri, arbori și grafice, exponențierea matricei, măști de biți, combinatorie și subsecvențe, probleme de partiție și programare dinamică multidimensională, printre multe alte concepte.
Elemente esențiale de programare competitivă, algoritmi master
Udemy oferă un curs esențial de programare competitivă susținut de Prateek Narang și Amal Kamaar, care acoperă programarea dinamică, matematica, teoria numerelor și structurile de date și algoritmi avansati într-un mod util și relevant pentru programatorii concurenți.
Cursul oferă o reîmprospătare a structurilor de date și a algoritmilor înainte de a se scufunda în algoritmi și tehnici mai complexe care sunt utile în programarea competitivă.
Cursul acoperă programarea dinamică, matematică, teoria jocurilor, potrivirea modelelor, Bitmasking și o multitudine de algoritmi avansați utilizați și testați în competițiile de programare.
Cursul Udemy este împărțit în 10 module și 42 de secțiuni și oferă o mulțime de întrebări practice după fiecare secțiune. Acest curs de bestseller este un must-have pentru oricine este interesat de programare competitivă.
Cuvinte finale
Programarea dinamică este o abilitate benefică pentru orice programator de a învăța să își îmbunătățească rezolvarea problemelor din lumea reală. Prin urmare, programatorii ar trebui să ia în considerare să parcurgă resursele sugerate pentru a adăuga acest instrument crucial la cutia lor de instrumente.
Apoi, puteți verifica limbaje de programare pe care să le utilizați în știința datelor.