Teknologian jakaminen

Algoritmitutkimuksen huomautukset (8) - Dynaamisen ohjelmoinnin perusteet

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Sisällysluettelo

Perussisältö:

Dynaaminen ohjelmointi:

Ongelmia dynaamisen ohjelmoinnin ymmärtämisessä esitellään:

Analyysi: (väkivaltainen perääntyminen)

Esimerkki koodista:

Brutaali haku:

Dfs-koodiesimerkki: (haku)

Raakavoimarekursiolla luotu rekursiopuu:

Muistiin tallennettu haku:

Esimerkki koodista:

Dynaaminen ohjelmointi:

Esimerkki koodista: (dynaaminen ohjelmointi, alkaen pienimmästä osaongelmasta)

Suoritusprosessi (dynaaminen ohjelmointi):

Analyysi: (dynaaminen ohjelmointi)

Tilan optimointi:

Esimerkki koodista:

Analyysi:

Perussisältö:

Mitä on dynaaminen ohjelmointi, mitä ongelmia dynaaminen ohjelmointi voi ratkaista välineenä, dynaamisen ohjelmoinnin luokittelu ja tiettyjen ongelmien luokittelu, jotka tietyt luokitukset voivat ratkaista.

Dynaaminen ohjelmointi:

Se on tärkeä algoritmiparadigma, joka jakaa ongelman sarjaksi pienempiä osaongelmia ja välttää toistuvia laskelmia tallentamalla osaongelmaratkaisuja, mikä parantaa huomattavasti ajan tehokkuutta.

Ongelmia dynaamisen ohjelmoinnin ymmärtämisessä esitellään:

Tämä ongelma esitellään portaiden kiipeämisen kautta, kun otetaan huomioon portaikko, jossa on yhteensä n askelmaa, voit nousta 1 tai 2 askelmaa jokaisessa vaiheessa. Kuinka monta vaihtoehtoa rakennuksen huipulle on?

Analyysi: (väkivaltainen perääntyminen)

Tämän kysymyksen tavoitteena on löytää useita ratkaisuja,Voimme harkita kaikkien mahdollisuuksien tyhjentämistä peruuttamalla . Tarkemmin sanottuna kuvittele portaiden kiipeäminen monen kierroksen valintaprosessina: aloita maasta, valitse yksi tai kaksi askelta jokaisella kierroksella, lisää 1 vaihtoehtojen määrään joka kerta, kun saavut portaiden huipulle, ja lisää vaihtoehtojen määrää, kun pääset portaiden huipulle.

koodiesimerkki：

  1. # python代码示例
  2. def backrack(choices,state,n,res) :
  3.     if state == n :
  4.         res[0] += 1 
  5.     for choice in choices :
  6.         if state + choice > n :
  7.             continue
  8.         backrack(choices,state+choice,n,res)
  9. def climbing_stairs_backrack(n) :
  10.     choices = [1,2]
  11.     state = 0
  12.     res = [0]
  13.     backrack(choices,state,n,res)
  14.     return res[0]
  15. n = int(input())
  16. print(climbing_stairs_backrack(n))
  1. // c++代码示例
  2. void backrack(vector<int> &choices, int state, int n, vector<int> &res)
  3. {
  4.     if (state == n )
  5.     {
  6.         res[0]++ ;
  7.     }
  8.     for (auto &choice : choices)
  9.     {
  10.         if (state + choice > n)
  11.         {
  12.             continue ;
  13.         }
  14.         backrack(choices, state + choice, n, res)
  15.     }
  16. }
  17.  
  18. int climbingStairsBackrack(int n)
  19. {    
  20.     vector<int> choices = {1 , 2 } ;
  21.     int state = 0 ;
  22.     vector<int> res = [0] ;
  23.     backrack(choices, state, n, res) ;
  24.     return res[0] ;
  25. }

Brutaali haku:

Peruutusalgoritmit eivät yleensä pura ongelmaa eksplisiittisesti, vaan käsittelevät ongelmaa sarjana päätöksentekovaiheita ja etsivät kaikkia mahdollisia ratkaisuja heuristiikan ja karsimisen avulla.

Voimme yrittää analysoida tätä kysymystä ongelman hajoamisen näkökulmasta. Oletetaan, että i:nnelle tasolle kiipeämiseen on olemassa dp[i]-ratkaisuja, niin dp[i] on alkuperäinen ongelma ja sen aliongelmia ovat:

dp[i-1], dp[i-2], dp[1], dp[2]

Koska voimme nousta vain 1 tai 2 askelmaa joka kierroksella, kun seisomme i:nnessä portaassa, pystyimme seisomaan vain i-1- tai i-2-portailla edellisellä kierroksella. Toisin sanoen voimme siirtyä vain tasolta i-1 tai i-2 tasolle i.

Tästä voimme tehdä tärkeän johtopäätöksen: i-1 tasolle nousseiden suunnitelmien määrä plus i-2 tasolle noussut suunnitelmien määrä on yhtä suuri kuin i-tasolle noussut suunnitelmien määrä. -taso. Kaava on seuraava:

dp[i] = dp[i-1] + dp[i-2]

Tämä tarkoittaa, että rakennuksen kiipeilyongelmassa on rekursiivinen suhde ja alkuperäinen ongelma voidaan ratkaista rakentamalla osaongelmien ratkaisut.

Dfs-koodiesimerkki: (haku)

  1. # python 代码示例
  2. def dfs(i : int) -> int :
  3.     if i == 1 or i == 2 :
  4.         return i
  5.     count = dfs(i - 1) + dfs(i - 2)
  6.     return count
  7. def climbing_stairs_dfs(n : int) -> int :
  8.     retunr dfs(n)
  1. // c++ 代码示例
  2. int dfs(int i)
  3. {
  4.     if (i == 1 || i == 2)
  5.     {
  6.         return i ;
  7.     }
  8.     int count = dfs(i - 1) + dfs(i - 2);
  9.     return count ;
  10. }
  11. int climbingStairsDFS(int n)
  12. {
  13.     retunr dfs(n) ;
  14. }

Väkivaltaisen rekursion luoma rekursiivinen puu：

Edellä mainitun rekursiivisen puun monistusongelman ratkaisemiseksi voidaan muistihakumenetelmällä poistaa suuri määrä identtisiä alipuita, joita konstruoidaan toistuvasti, mikä parantaa laskennan tehokkuutta. (päällekkäisiä aliongelmia）

Muistiin tallennettu haku:

Jos haluat laskea kaikki päällekkäiset aliongelmat vain kerran, sinun on määritettävä taulukko nem tallentamaan kunkin osaongelman ratkaisu ja karsimaan päällekkäiset aliongelmat hakuprosessin aikana.

  1. Kun dp[i] lasketaan ensimmäisen kerran, se tallennetaan arvoon nem[i] myöhempää käyttöä varten.
  2. Kun dp[i] lasketaan uudelleen, tulos saadaan suoraan nem[i]:ssä, jotta vältetään osaongelmien toistuvat laskelmat.

Esimerkki koodista:

  1. # python 代码示例
  2. def dfs(i : int, mem : list[int]) -> int :
  3.     if i == 1 or i == 2 :
  4.         return i
  5.     if mem[i] != -1 :
  6.         return mem[i]
  7.     count = dfs(i - 1, mem) + dfs(i - 2, mem)
  8.     # 记录dfs(i)
  9.     mem[i] = count
  10.     return count
  11. def climbing_stairs_dfs_mem(n : int) -> int :
  12.     mem = [-1] * (n + 1)
  13.     return dfs(n, mem)
  1. // c++ 代码示例
  2. int dfs(int i, vector<int> &mem)
  3. {
  4.     if (i == 1 || i == 2)
  5.     {
  6.         return i ;
  7.     }
  8.     if (mem != -1)
  9.     {
  10.         return mem[i] ;
  11.     }
  12.     int count = dfs(i - 1, mem) + dfs(i - 2, mem) ;
  13.     mem[i] = count ;
  14.     return count ;
  15. }
  16. int climbingStairsDFSMem(int n)
  17. {
  18.     vector<int> mem(n + 1, -1) ;
  19.     return dfs(n, mem) ; 
  20. }

Memoisoinnin jälkeen kaikki päällekkäiset aliongelmat lasketaan vain kerran, ja aikamonimutkaisuus optimoidaan arvoon O(n).

Dynaaminen ohjelmointi:

Muistettu haku on "ylhäältä alas" -menetelmä. Aloitamme alkuperäisestä ongelmasta (juurisolmu) ja hajotamme rekursiivisesti pienemmät osaongelmat, kunnes ratkaisemme pienimmän tunnetun aliongelman (lehtisolmu). . Jälkeenpäin aliongelmien ratkaisuja kerätään kerros kerrokselta takaisinperinnön kautta ratkaisun rakentamiseksi alkuperäiseen ongelmaan.

Sitä vastoin dynaaminen ohjelmointi on "alhaalta ylös" -lähestymistapa: aloitetaan ratkaisusta pienimpään osaongelmaan ja rakennetaan iteratiivisesti ratkaisuja suurempiin osaongelmiin, kunnes alkuperäiseen ongelmaan saadaan ratkaisu.

Koska dynaaminen ohjelmointi ei sisällä paluuprosessia, se tarvitsee vain toteuttaa silmukkaiteraatiolla ilman rekursiota.

Esimerkki koodista: (dynaaminen ohjelmointi, alkaen pienimmästä osaongelmasta)

  1. # python 代码示例
  2. def clibing_stairs_dp(n) :
  3.     if n == 1 or n == 2 :
  4.         return n
  5.     dp = [0] * (n + 1)
  6.     dp[1], dp[2] = 1, 2
  7.     for i in range(3,n + 1) :
  8.         dp[i] = dp[i-1] + dp[i- 2]
  9.     return dp[n]
  1. // c++ 代码示例
  2.  
  3. int climbingStairsDP(int n) 
  4. {
  5.     if (n == 1 || n == 2)
  6.     {
  7.         retunr n ;
  8.     }
  9.     vector<int> dp(n + 1, -1) ;
  10.     dp[1] = 1 ;    
  11.     dp[2] = 2 ;
  12.     for (int i = 3 ; i <= n ; i++)
  13.     {
  14.         dp[i] = dp[i - 1] + dp[i- 2] ;
  15.     }
  16.     return dp[n] ;
  17. }

Suoritusprosessi (dynaaminen ohjelmointi):

Analyysi: (dynaaminen ohjelmointi)

Kuten backtracking-algoritmi, dynaaminen ohjelmointi käyttää myös "tilan" käsitettä edustamaan tiettyä ongelmanratkaisuvaihetta. Jokainen tila vastaa aliongelmaa ja vastaavaa paikallista optimaalista ratkaisua. Esimerkki: Portaiden kiipeämisongelman tila määritellään nykyisen portaikon järjestykseksi i.

Yllä olevan perusteella voimme tiivistää dynaamisten termien yleiset termit:

  1. Taulukko dp on nimeltään {dp table}, dp[i] edustaa tilaa i vastaavan aliongelman ratkaisua.
  2. Tilaa, joka vastaa minimialiongelmaa (ensimmäinen ja toinen portaat), kutsutaan alkutilaksi
  3. Rekursiivista kaavaa dp[i] = dp[i-1] + dp[i-2] kutsutaan tilayhtälöksi

Tilan optimointi:

dp[i] liittyy vain arvoihin dp[i-1] ja dp[i-2]

Sen sijaan, että käyttäisit taulukkoa kaikkien aliongelmien ratkaisujen tallentamiseen, tarvitaan vain kaksi muuttujaa eteenpäin vierimiseen.

Esimerkki koodista:

  1. # python 代码示例
  2. def clibing_stairs_dp_comp(n) :
  3.     if n == 1 or n == 2 :
  4.         return n
  5.     a, b = 1, 2
  6.     for _ in range(3, n + 1) :
  7.         a, b = b , a + b
  8.     return b
  1. // c++ 代码示例
  2. int climbingStairsComp(int n) 
  3. {
  4.     if (n == 1 || n == 2)
  5.     {
  6.         return n ;
  7.     }
  8.     int a = 1 , b = 2 ;
  9.     for (int i = 3 ; i <= n ; i++)
  10.     {
  11.         int temp = b ;
  12.         b = a + b ;
  13.         a = temp ;
  14.     }
  15.     return b ;
  16. }

Analyysi:

Taulukon dp viemä tila jätetään pois ja tilan monimutkaisuus pienennetään arvosta O(n) arvoon O(1)

Dynaamisissa ohjelmointiongelmissa nykyinen tila liittyy vain rajoitettuun määrään aikaisempia tiloja. Tällä hetkellä voimme säilyttää vain tarvittavat tilat ja säästää muistitilaa "ulottuvuuden vähentämisen" avulla. . Tätä tilan optimointitekniikkaa kutsutaan "rullaviksi muuttujiksi" tai "rullaviksi taulukoiksi".

Henkilökohtainen profiili

Hän on omistautunut teknologian tutkimukselle yli 30 vuoden ajan ja hallitsee useita kieliä, kuten java, linux, javascript, php, css jne. Hän on tehnyt paljon työtä avoimen lähdekoodin alalla Kehittäjän dokumentaatioasema, jossa voit jakaa joitakin teknologian kehittämisen ongelmia myöhempää käyttöä varten

yhteystietoni

Mail