DYNAMIC NA PROGRAMMING: MGA KATANGIAN, HALIMBAWA, KALAMANGAN, KAWALAN - TEKNOLOHIYA - 2025

Ang dynamic na programming ay isang modelo ng algorithm na malulutas ang isang kumplikadong problema sa pamamagitan ng paghati nito sa mga subproblem, pag-iimbak ng mga resulta nito upang maiwasan ang pagkalkula ng mga resulta.

Ginagamit ang iskedyul na ito kung mayroon kang mga problema na maaaring nahahati sa mga katulad na subproblema, upang ang kanilang mga resulta ay maaaring magamit muli. Para sa karamihan, ang iskedyul na ito ay ginagamit para sa pag-optimize.

Dynamic na programming. Ang mga subproblem na superimposed sa pagkakasunud-sunod ng Fibonacci. Pinagmulan: Wikimedia commons, en: Gumagamit: Dcoatzee, sinubaybayan ng Gumagamit: Stannered / Public domain

Bago lutasin ang magagamit na subproblem, susubukan ng dynamic algorithm na suriin ang mga resulta ng dati nang nalutas na mga subproblem. Ang mga solusyon sa mga subproblem ay pinagsama upang makamit ang pinakamahusay na solusyon.

Sa halip na pagkalkula nang paulit-ulit ang parehong subproblem, maaari mong maimbak ang iyong solusyon sa ilang memorya, kapag una mong nakatagpo ang subproblem na ito. Kapag lumilitaw muli sa panahon ng solusyon ng isa pang subproblem, dadalhin ang solusyon na naka-imbak sa memorya.

Ito ay isang kahanga-hangang ideya para sa pag-aayos ng oras ng memorya, kung saan ang paggamit ng karagdagang puwang ay maaaring mapabuti ang oras na kinakailangan upang makahanap ng solusyon.

Mga tampok ng mga dynamic na programming

Ang mga sumusunod na mahahalagang katangian ay kung ano ang dapat mong magkaroon ng isang problema sa bago ang dynamic na programming ay maaaring mailapat:

Optimum na istruktura

Ang katangian na ito ay nagpapahiwatig na ang isang problema sa pag-optimize ay maaaring malutas sa pamamagitan ng pagsasama ng mga pinakamainam na solusyon ng pangalawang problema na bumubuo dito. Ang mga pinakamainam na substructure ay inilarawan sa pamamagitan ng pag-urong.

Halimbawa, sa isang graph ang isang pinakamainam na substraktura ay ihaharap sa pinakamaikling landas r na mula sa isang vertex s sa isang vertex t:

Iyon ay, sa pinakamaikling landas na ito sa anumang intermediate na vertex na maaari kong makuha. Kung ang r ay talagang pinakamaikling ruta, kung gayon maaari itong nahahati sa subroutes r1 (mula s hanggang i) at r2 (mula sa i t t), sa paraang ito ay sa pinakamaikling pinakamaikling ruta sa pagitan ng mga kaukulang mga vertice.

Samakatuwid, upang mahanap ang pinakamaikling mga landas, ang solusyon ay maaaring madaling nabalangkas nang maingat, na kung ano ang ginagawa ng Floyd-Warshall algorithm.

Pag-overlay ng mga subproblem

Ang puwang ng subproblem ay dapat maliit. Iyon ay, ang anumang recursive algorithm na malulutas ang isang problema ay kailangang malutas ang parehong subproblems nang paulit-ulit, sa halip na makabuo ng mga bagong subproblema.

Halimbawa, upang makabuo ng serye ng Fibonacci, maaaring isaalang-alang ang pagbabalangkas na ito: Fn = F (n - 1) + F (n - 2), ang pagkuha bilang isang baseng kaso na F1 = F2 = 1. Pagkatapos ay magkakaroon tayo: F33 = F32 + F31, at F32 = F31 + F30.

Tulad ng nakikita mo, ang F31 ay nalulutas sa recursive subtrees ng parehong F33 at F32. Kahit na ang kabuuang bilang ng mga subproblem ay talagang maliit, kung magpatibay ka ng isang recursive solution na tulad nito tatapusin mo ang paulit-ulit na mga problema.

Ito ay isinasaalang-alang sa pamamagitan ng mga dynamic na programming, kaya lutasin nito ang bawat subproblem nang isang beses lamang. Magagawa ito sa dalawang paraan:

Diskarte sa top-down

Kung ang solusyon sa anumang problema ay maaaring maingat na pormulahin gamit ang solusyon ng mga subproblema nito, at kung ang mga subproblemong ito ay magkakapatong, ang mga solusyon sa mga subproblem ay madaling maisaulo o maiimbak sa isang mesa.

Sa bawat oras na ang isang bagong solusyon sa subproblem ay hinanap, ang talahanayan ay susuriin upang makita kung nauna itong nalutas. Kung sakaling ang isang solusyon ay nakaimbak, gagamitin ito sa halip na makalkula muli. Kung hindi, malulutas ang subproblem, na iniimbak ang solusyon sa talahanayan.

Diskarte sa ibaba

Matapos ang solusyon ng isang problema ay pormulahin na pormulahin sa mga tuntunin ng mga subproblems nito, posible na subukang baguhin ang problema sa isang paitaas na fashion: una, susubukan nating lutasin ang mga subproblem at gamitin ang kanilang mga solusyon upang makarating sa mga solusyon sa mas malaking subproblems.

Kadalasan ito ay ginagawa sa form ng talahanayan, mas malilikha ang mga solusyon sa mas malaki at mas malaking subproblems sa pamamagitan ng paggamit ng mga solusyon sa mas maliit na subproblem. Halimbawa, kung ang mga halaga ng F31 at F30 ay alam na, ang halaga ng F32 ay maaaring kinakalkula nang direkta.

Paghahambing sa iba pang mga pamamaraan

Ang isang makabuluhang tampok ng isang problema na maaaring malutas sa pamamagitan ng mga dynamic na programming ay dapat itong magkaroon ng mga subproblem na overlay. Ito ang nakikilala sa mga dynamic na programming mula sa diskarte ng paghati at manakop, kung saan hindi kinakailangan na mag-imbak ng pinakasimpleng mga halaga.

Ito ay katulad ng pag-urong, dahil kapag kinakalkula ang mga kaso ng batayan, ang pangwakas na halaga ay maaaring matukoy nang hindi sinasadya. Ang diskarte sa ibaba na ito ay gumagana nang maayos kapag ang isang bagong halaga ay nakasalalay lamang sa dati nang kinakalkula na mga halaga.

Halimbawa

Minimum na mga hakbang upang maabot ang 1

Para sa anumang positibong integer "e" alinman sa mga sumusunod na tatlong hakbang ay maaaring isagawa.

- Magbawas ng 1 mula sa bilang. (e = e-1).

- Kung nahahati ito ng 2, nahahati ito ng 2 (kung e% 2 == 0, kung gayon e = e / 2).

- Kung nahahati ito ng 3, nahahati ito ng 3 (kung e% 3 == 0, pagkatapos ay e = e / 3).

Batay sa mga hakbang sa itaas, ang minimum na bilang ng mga hakbang na ito ay dapat matagpuan upang dalhin ang e sa 1. Halimbawa:

- Kung e = 1, resulta: 0.

- Kung e = 4, resulta: 2 (4/2 = 2/2 = 1).

- Kapag e = 7, resulta: 3 (7-1 = 6/3 = 2/2 = 1).

Tumutok

Maaaring isipin ng isa na palaging pumili ng hakbang na ginagawang n bilang mababang hangga't maaari at magpapatuloy tulad nito hanggang sa umabot ito sa 1. Gayunpaman, makikita na ang diskarte na ito ay hindi gumagana dito.

Halimbawa, kung e = 10, ang mga hakbang ay: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 na mga hakbang). Gayunpaman, ang pinakamainam na form ay: 10-1 = 9/3 = 3/3 = 1 (3 mga hakbang). Samakatuwid, ang lahat ng posibleng mga hakbang na maaaring gawin para sa bawat halaga ng n natagpuan ay dapat na subukan, pagpili ng pinakamababang bilang ng mga posibilidad na ito.

Nagsisimula ang lahat sa pag-urong: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} kung e> 1, na kumukuha bilang base case: F (1) = 0. Ang pagkakaroon ng equation ng pag-ulit, maaari mong simulan ang code sa recursion.

Gayunpaman, makikita na mayroon itong overlay na mga subproblem. Bukod dito, ang pinakamainam na solusyon para sa isang naibigay na input ay nakasalalay sa pinakamainam na solusyon ng mga subproblems nito.

Tulad ng sa pagsasaulo, kung saan ang mga solusyon ng mga subproblem na nalulutas ay naka-imbak para magamit sa ibang pagkakataon. O tulad ng sa pabago-bagong programming, magsisimula ka sa ilalim, gumagana ang iyong paraan hanggang sa ibinigay na e. Pagkatapos ang parehong mga code:

Pag-alaala

Programa ng pabrika ng pabrika

Kalamangan

Ang isa sa mga pangunahing bentahe ng paggamit ng dynamic na programming ay ang pagpapabilis sa pagproseso, dahil ang mga sanggunian na dati nang kinakalkula ay ginagamit. Dahil ito ay isang recursive na diskarte sa programming, binabawasan nito ang mga linya ng code sa programa.

Malaking algorithm kumpara sa mga dynamic na programming

Ang mga matakaw na algorithm ay katulad ng pabago-bagong programming sa gayon ay pareho silang mga tool para sa pag-optimize. Gayunpaman, ang greedy algorithm ay naghahanap para sa isang pinakamainam na solusyon sa bawat lokal na hakbang. Iyon ay, naghahanap ito ng isang sakim na pagpipilian sa pag-asa na makahanap ng isang global na pinakamabuting kalagayan.

Samakatuwid, ang matakaw algorithm ay maaaring gumawa ng isang palagay na mukhang pinakamainam sa oras, ngunit nagiging mahal sa hinaharap at hindi ginagarantiyahan ang isang pandaigdigang optimal.

Sa kabilang banda, natuklasan ng mga dynamic na programming ang pinakamainam na solusyon para sa mga subproblems at pagkatapos ay gumawa ng isang napiling kaalaman sa pamamagitan ng pagsasama ng mga resulta ng mga subproblem na talagang hanapin ang pinakamainam na solusyon.

Mga Kakulangan

- Kailangan ng maraming memorya upang maiimbak ang kinakalkula na resulta ng bawat subproblem, nang hindi magagarantiyahan na ang naka-imbak na halaga ay gagamitin o hindi.

- Maraming mga beses, ang halaga ng output ay nakaimbak nang hindi gagamitin sa mga sumusunod na subproblem sa panahon ng pagpapatupad. Ito ay humahantong sa hindi kinakailangang paggamit ng memorya.

- Sa dynamic na programming, ang mga pag-andar ay tinatawag na recursively. Pinapanatili nito ang memorya ng stack na patuloy na tumataas.

Recursion vs dynamic na programming

Kung mayroon kang limitadong memorya upang patakbuhin ang iyong code at bilis ng pagproseso ay hindi isang pag-aalala, maaari mong gamitin ang pag-urong. Halimbawa, kung nagkakaroon ka ng isang mobile application, ang memorya ay napaka limitado upang patakbuhin ang application.

Kung nais mo ang programa na tumakbo nang mas mabilis at walang mga paghihigpit sa memorya, mas mainam na gumamit ng mga dynamic na programming.

Aplikasyon

Ang dinamikong programming ay isang epektibong pamamaraan sa paglutas ng mga problema na kung hindi man ay tila napakahirap malutas sa isang makatuwirang halaga ng oras.

Ang mga algorithm batay sa pabago-bagong paradigma ng programming ay ginagamit sa maraming mga lugar ng agham, kabilang ang maraming mga halimbawa sa artipisyal na intelektwal, mula sa pagpaplano ng paglutas ng problema sa pagkilala sa pagsasalita.

Algorithms batay sa dynamic na programming

Ang dinamikong programming ay lubos na epektibo at mahusay na gumagana para sa isang malawak na hanay ng mga problema. Maraming mga algorithm ang maaaring makita bilang mga raket na aplikasyon ng algorithm, tulad ng:

- serye ng numero ng Fibonacci.

- Mga Towers ng Hanoi.

- Lahat ng mga pares ng mas maikling mga ruta sa pamamagitan ng Floyd-Warshall.

- problema sa backpack.

- Pag-iskedyul ng proyekto.

- Ang pinakamaikling paraan sa pamamagitan ng Dijkstra.

- Pagkontrol ng flight at kontrol ng robotics.

- Mga problema sa pag-optimize sa matematika.

- Timeshare: iskedyul ng trabaho upang ma-maximize ang paggamit ng CPU.

Mga serye ng numero ng Fibonacci

Ang mga numero ng Fibonacci ay ang mga numero na matatagpuan sa mga sumusunod na pagkakasunod-sunod: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, atbp.

Sa terminolohiya ng matematika, ang pagkakasunud-sunod ng Fn ng mga numero ng Fibonacci ay tinukoy ng formula ng pag-ulit: F (n) = F (n -1) + F (n -2), kung saan F (0) = 0 at F ( 1) = 1.

Diskarte sa top-down

Sa halimbawang ito, ang isang hanay ng paghahanap sa lahat ng mga paunang halaga ay sinimulan ng -1. Kailan kinakailangan ang solusyon sa isang subproblem, hahanapin muna ang search matrix na ito.

Kung ang kinakalkula na halaga ay nariyan, ibabalik ang halagang iyon. Kung hindi man, ang resulta ay makakalkula na maiimbak sa hanay ng paghahanap upang maaari itong magamit muli.

Diskarte sa ibaba

Sa kasong ito, para sa parehong serye ng Fibonacci, f (0) ay kinakalkula una, pagkatapos f (1), f (2), f (3), at iba pa. Kaya, ang mga solusyon ng mga subproblem ay itinatayo mula sa ibaba hanggang.

Mga Sanggunian

1. Vineet Choudhary (2020). Panimula sa Dynamic na Programming. Developer Insider. Kinuha mula sa: developerinsider.co.
2. Alex Allain (2020). Dynamic na Programming sa C ++. C Programming. Kinuha mula sa: cprogramming.com.
3. Pagkatapos ng Academy (2020). Ideya ng Dynamic na Programming. Kinuha mula sa: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dinamikong Programming at Recursion - Pagkakaiba, Mga kalamangan na may Halimbawa. CSE Stack. Kinuha mula sa: csestack.org.
5. Code ng Chef (2020). Tutorial Para sa Dynamic na Programming. Kinuha mula sa: codechef.com.
6. Programiz (2020). Dinamikong Programming. Kinuha mula sa: programiz.com.