Brutālais spēks pret dinamisko programmēšanu: atšķirība un salīdzinājums

Mūsu ikdienas dzīvē ir daudz problēmu. Tāpat arī programmēšanas jomā ir daudz problēmu.

Ir daudz metožu, lai atrisinātu noteiktu problēmu, kas saistīta ar algoritmiem un programmēšanu. Gan brutālais spēks, gan dinamiskā programmēšana ir paņēmienu veidi, lai atrisinātu problēmu un atrastu risinājumu.

Atslēgas

1. Brutālā spēka algoritmi izsmeļoši meklē visus iespējamos risinājumus, savukārt dinamiskā programmēšana sadala problēmas mazākās apakšproblēmās, kas pārklājas, un saglabā risinājumus atkārtotai izmantošanai.
2. Dinamiskā programmēšana piedāvā uzlabotu efektivitāti un samazinātu skaitļošanas sarežģītību salīdzinājumā ar brutālā spēka pieejām.
3. Brutālā spēka metodes ir vieglāk īstenojamas, savukārt dinamiskai programmēšanai nepieciešama dziļāka problēmas izpratne, lai noteiktu optimālo apakšstruktūru un pārklājošās apakšproblēmas.

Brutālais spēks pret dinamisko programmēšanu

Starpība starp Brute Force un dinamiskā programmēšana ir efektivitāte. Abām metodēm ir sava efektivitāte. The brutālu spēku metode atkārtojas pa doto datu kopu daudzas reizes, tādējādi radot zemu efektivitāti, turpretim dinamiskās programmēšanas metode atkārto datu kopu tikai vienu reizi, tādējādi nodrošinot labu efektivitāti. Bet jā, abas metodes ir noderīgas dažādās situācijās.

Brutālā spēka pieeja atrod visus iespējamos risinājumus, kas saistīti ar konkrēto problēmu, līdz tiek atrasts apmierinošs risinājums. Tas vienmēr ir vienkāršākais veids, kā ieviest un garantēt risinājumu, ja tāds pastāv.

Šāda brutālā spēka tehnikas būtība palēninās tās darbību. Brutālā spēka pieeja vienmēr ir vienkāršākā pieeja risinājuma iegūšanai.

Dinamiskā programmēšana ir optimizēta problēmas risināšanas versija īsākā laikā un ar mazāku piepūli. Tā ir rekursijas optimizācija, jo rekursijā mēs vairākas reizes risinām vienu un to pašu ievades kopu, savukārt ar dinamisko programmēšanu mēs risinām tikai neatrisinātus dotās problēmas gadījumus.

Salīdzināšanas tabula

Salīdzināšanas parametri	Brute Force	Dinamiskā programmēšana
Metodoloģija	Tas atrod visus iespējamos problēmas risinājumus.	Tā atrod tikai vienu optimālo risinājumu.
Laika sarežģītība	O(mn), kur m ir atrodamās rakstzīmes skaits un n ir ievades lielums.	O(n), kur n ir unikālo apakšproblēmu skaits
Piemērs	Izlases liktenis	Floids Voršels
Atkārtojumi	Atkārtojumu skaits ir lielāks	Atkārtojumu skaits ir mazāks
Efektivitāte	Mazāk efektīva	Efektīvāks

Kas ir brutālais spēks?

Jomā Datorzinātnes, Brute Force ir populārs paņēmiens risinājuma atrašanai. Brutālā spēka metode garantē konkrētas problēmas risinājumu, taču tās palaišana prasa daudz laika un ir neefektīva.

Tas sākas ar visu gadījumu sistemātisku uzskaiti un pārbaudi, vai tie atbilst nosacījumam vai nē.

Ja mēs ņemam piemēru par masīva elementu šķirošanu, tad, izmantojot brutālā spēka pieeju, mēs šķērsosim masīvu daudzas reizes, līdz iegūsim vēlamo risinājumu. Tas novedīs pie laika izšķērdēšanas.

Šī iemesla dēļ to sauc par laikietilpīgu.

Brutālā spēka paņēmiens tiek izmantots, ja datu kopa ir ierobežota, jo tas radīs daudz sarežģījumu, ja mēs izmantosim daudz aprēķinu daudzas skaitļus reizes lielam datu apjomam. Ikreiz, kad rodas jauna problēma, kuras atbilstošais risinājums nav zināms, brute Force tehnika tiek izmantota kā bāzes metode.

Brute Force galvenais trūkums reālu problēmu risināšanā ir tas, ka tas palielina pārbaudāmo lietu skaitu. Piemēram, ja mēs vēlamies atrast skaitļa dalītāju un pieņemsim, ka tā dalītājs ir 16, tad brutālais spēks veiks 10^15 aprēķinus, lai atrastu risinājumu.

Kas ir dinamiskā programmēšana?

Dinamiskā programmēšana ir optimizēta metode matemātisko, kā arī datorzinātņu problēmu risināšanai. To 1950. gados izstrādāja Ričards Belmans.

Mūsdienās tam ir pielietojums dažādās jomās, pateicoties tā optimizācijas jaudai.

Tas atrisina sarežģītu problēmu, sadalot to vienkāršākos apakšproblēmās rekursīvā veidā. Tad katra apakšproblēma tiek atrisināta rekursīvi.

Galvenais ir tas, ka, ja sarežģītā uzdevumā apakšgadījums “a” parādās 4 reizes, tad dinamiskā programmēšana to atrisinās tikai vienu reizi, savukārt rekursija to atrisinās 4 reizes.

Tas ir iemesls, kāpēc priekšroka tiek dota dinamiskajai programmēšanai. Matemātikas gadījumā dinamiskā programmēšana attiecas uz lēmuma vienkāršošanu, sadalot to apakšproblēmās.

Datorzinātnes gadījumā mums ir divi svarīgi termini, kuros mēs izmantojam dinamisko programmēšanu, pirmkārt, optimāla apakšstruktūra, un otra ir apakšproblēma, kas pārklājas.

Optimāla apakšstruktūra nozīmē, ka optimizācijas problēmas risinājums tiek iegūts, apvienojot visu apakšproblēmu optimizētu risinājumu. Apakšproblēmu pārklāšanās nozīmē, ka apakšproblēmu vietai jābūt mazai.

Tam ir arī mīnusi, tāpat kā katrai monētai ir divas puses. Kā mēs zinām, tas saglabā starprezultātu, vienlaikus risinot apakšproblēmu, kas izraisa daudz atmiņas.

Galvenās atšķirības starp brutālu spēku un dinamisko programmēšanu

1. Brutālā spēka pieeja atrisina problēmu, atkārtojot datu kopu lielu skaitu reižu. Savukārt dinamiskā programmēšana atkārtojas tikai vienu reizi un sniedz optimālu risinājumu.
2. Brute Force piedāvātais risinājums nav garantēts, ka tas būs optimāls, jo tas nodrošina visus iespējamos risinājumus. Savukārt Dynamic Programming piedāvātais risinājums vienmēr būs optimāls.
3. Brutālā spēka metode tiek atrisināta, vienlaikus apsverot visas datu kopas, savukārt dinamiskā programmēšana atrisina problēmu, sadalot doto problēmu vairākās apakšproblēmās.
4. Brutālā spēka pieeja neizmanto optimālas apakšstruktūras un pārklājošu apakšproblēmu jēdzienu. Dinamiskā programmēšana izmanto šos jēdzienus.
5. Brutālā spēka metode nav optimāla un efektīva. Tas atrisina vienu un to pašu aprēķinu vairākas reizes, savukārt Dynamin programmēšana ir optimāla un efektīva, jo tā atrisina vienu aprēķinu tikai vienu reizi un izmanto memoizāciju.

Atsauces

1. https://www.science.org/doi/abs/10.1126/science.153.3731.34
2. https://dl.acm.org/doi/fullHtml/10.1145/3107239

Pēdējo reizi atjaunināts: 14. gada 2023. jūlijā