Dinamiskās programmēšanas paradigma problēmu un iegaumēšana

Veidojot dinamisku programmēšanu, jūs uzzinājāt par “Skaldi un valdi” paradigmu un rekursiju. Šajā rakstā jūs uzzināsiet par iegaumēšanas (Memorization) un dinamiskās programmēšanas (Dynamic programming) jēdzieniem.

Dinamiskā programmēšana ir programmēšanas paradigma, kas veicina problēmu risināšanu, sadalot tās mazākās problēmās un risinot tās. Pēc tam risinājumi tiek saglabāti atbilstošā datu struktūrā vēlākai lietošanai. Priekšrocība ir tāda, ka, ja šīs apakšproblēmas ir jāaprēķina vēlreiz, tiek meklēta tikai atbilde, nevis jāaprēķina problēma vēlreiz. Apakšproblēmu risināšanas un uzglabāšanas tehnika, lai ietaupītu laiku potenciālai nākotnes meklēšanai, ir pazīstama kā iegaumēšana. Dinamiskā programmēšana attiecas uz diviem jēdzieniem, kas jau ir sastopami iepriekšējos rakstos…

Īsi atsvaidzināsim šos jēdzienus.

• Pirmais ir “Skaldi un valdi”, proti, uzņemties vienu lielu problēmu un sadalīt to mazākā apakšproblēmu kopā un pēc tam tās atrisināt.
• Otrā ir tās apakškopa, kas pazīstama kā Rekursija. Rekursija ir risinājuma kodēšanas prakse, kas ļauj izvairīties no cilpu palaišanas, bet tā vietā izmanto vairākus “pašzvanus” (SelfCalls), lai atrastu risinājumu.

Dinamiskā programmēšana ir šo pieeju paplašinājums, kas papildus ietver to rezultātu uzskaiti, kas iegūti, izpildot apakšproblēmas katru reizi, kad tās tiek palaistas no jauna. Turpmākajās darbībās rezultātu atkārtotas aprēķināšanas vietā uzmeklēšana tiek uzdota pēdējo reizi, kad jautājums tika uzdots, kā jau minēts, šo pieeju sauc par iegaumēšanu (Memorization).

Un, lai nostiprinātu koncepciju, tas ir tad, kad iepriekšējo aprēķinu rezultāti tiek saglabāti un izmantoti aprēķinu atkārtotas palaišanas vietā, kad kompilators nosaka, ka aprēķins ir veikts iepriekšējam uzdevumam.

Lai to ilustrētu, atsauciet atmiņā rakstu par binārajiem skaitļiem. Cik kombinācijas bija iespējamas ar sešu ciparu bināro slēdzeni? Rakstā tika parādīts, ka to var atklāt, izmantojot eksponenci vai skaitļa spēka atrašanu. Tātad tai pašai slēdzenei ar sešiem cipariem būtu 2^6 vai līdz 64 kombinācijām.

Tātad 2^6 = 2 x 2 x 2 x 2 x 2 x 2 Varat arī sadalīt tos divās grupās, kur esat aprēķinājis (2 x 2 x 2 x 2 x 2 x 2). Tā rezultātā tiks iegūtas (2 x 2 x 2) x (2 x 2 x 2) = 2^6 = 64 un 8 x 8 = 64 atkal dod to pašu rezultātu. Piemērojot “Skaldi un valdi” pieeju, lai to efektīvi aprēķinātu.

Izmantojot iegaumēšanu, aprēķini tiktu samazināti, vispirms aprēķinot (2^3) x (2^3) = 64. Piemērojot iegaumēšanu, tiktu aprēķināti pirmie 2 ar 3 pakāpi, pēc tam atkārtoti izmantota otrajai iekavai, samazinot kopējo nepieciešamo aprēķinu.

Tātad, kāda veida problēmas ir piemērotas dinamiskam risinājumam?

Dinamiskās programmēšanas pieeja parasti tiek izmantota kombinācijas vai optimizācijas problēmām. Viens jau minētās kombinācijas problēmas piemērs ir Fibonači secība. Vēl viens gadījums, ar kuru jūs varat saskarties intervijā, ir mugursomas problēma. Tā ir gan kombinācija, gan optimizācijas problēma.

Teiksim, ieplānotam kempinga braucienam jūs varat piepildīt mugursomu ar nepieciešamajām lietām, katrai precei ir sava svara izmaksas.

• Lāpa ir vienāda ar 1 kg,
• ūdens ir 2 kg,
• un telts ir vienāda ar 3 kg.

Turklāt katrai precei ir sava vērtība.  Lāpa ir vienāda ar 1, ūdens ir vienāds ar 2 un telts ir vienāds ar 3.

Lāpa(1) ; Ūdens(2) ; Telts(3)

JavaScript koda paraugs uzdevuma atrisināšanai vienā no daudzām iespējamajām versijām – savām vajadzībām varat šo kodu pielāgot un uzlabot ja nepieciešams:

function best_items(weight, items) {
    // Izveido tabulu, kurā glabāt labākās lietas katram svaram.
    var table = new Array(weight + 1);
    for (var i = 0; i <= weight; i++) {
      table[i] = [];
    }
 
    // Iterē pār visām lietām.
    for (var i = 0; i < items.length; i++) {
      var item = items[i];
 
      // Iterē pār visiem svariem.
      for (var j = weight; j >= 0; j--) {
        // Ja lietas svars ir mazāks vai vienāds ar atlikušo svaru,
        // pievieno lietu labāko lietu sarakstam.
        if (item.weight <= j) {
          table[j].push(item);
        }
      }
    }
 
    // Atgriež labāko lietu sarakstu norādītajam svaram.
    return table[weight];
  }
 
  // Pārbauda funkciju.
  var items = [
    { weight: 1, name: "Lāpa" },
    { weight: 2, name: "Ūdens" },
    { weight: 3, name: "Telts" }
  ];
  var weight = 8;
  var best_items = best_items(weight, items);
 
  // Izdrukā labāko lietu sarakstu.
  console.log("Labākās lietas:", best_items);
 
  // Aprēķina kopējo svaru.
  var total_weight = 0;
  for (var i = 0; i < best_items.length; i++) {
    total_weight += best_items[i].weight;
  }
 
  // Izdrukā kopējo svaru.
  console.log("Kopējais svars:", total_weight);

Koda izvade uzrādīs šādu rezultātu:

Labākās lietas: [Lāpa, Ūdens] Kopējais svars: 5

• Funkcija best_items() saņem divus argumentus: svara ierobežojumu un lietu sarakstu.
• Funkcija izveido tabulu, kurā katram svaram ir saraksts ar labāko lietu.
• Funkcija pēc tam iterē pār lietām un pievieno katru lietu tabulas atbilstošajam svaram, ja lietas svars ir mazāks vai vienāds ar atlikušo svaru.
• Funkcija pēc tam atgriež labāko lietu sarakstu norādītajam svaram.
• Funkcija tiek pārbaudīta, izmantojot lietu sarakstu, kas satur lāpu, ūdeni un telti, un svara ierobežojumu 8. Funkcija atgriež labāko lietu sarakstu, kas ir [Lāpa, Ūdens].

Īsāk sakot, mugursomas problēma iezīmē to priekšmetu sarakstu, kuru svars ir atšķirīgs un kuriem ir dažādas vērtības. Jūs varat pārvadāt tikai tik daudz priekšmetu savā mugursomā. Problēma prasa aprēķināt optimālo priekšmetu kombināciju, ko varat nēsāt, ja jūsu mugursoma var izturēt noteiktu svaru. Mērķis ir atrast vislabāko atdevi mugursomas svara ietilpībai. Lai aprēķinātu šīs problēmas risinājumu, ir jāatlasa visi vienumi, kas kopā veido noteiktu svaru un satur noteiktu vērtību. Pārnēsājamais svars mainīsies, šo problēmu var attiecināt uz resursu piešķiršanu, kur jums ir tik daudz CPU jaudas un jāizpilda X uzdevumi. Tāpat kā CPU jauda, kas paredzēta uzdevumu veikšanai. Dažreiz svars būs 7 kg, bet citreiz tas var būt 10 kg. Dinamiskā programmēšana ietver to aprēķinu saglabāšanu, kas izmantoti, lai nonāktu pie konkrēta risinājuma. Tātad, ja esat aprēķinājis optimālo atlasi 7 kg un tas ir palielināts līdz 10 kg, sākotnējie aprēķini nav jāveic atkārtoti. Tas var būt laika taupīšanas rādītājs. Aprēķinot dinamiskās programmēšanas risinājumus, vispirms ir jānosaka mērķa funkcija. Tāds ir optimālā rezultāta apraksts. Tālāk jums ir jāsadala problēma mazākos posmos. Viena pieeja, kas jau tika apspriesta, lai to panāktu, var būt rekursīvo funkciju izmantošana. Tās ir funkcijas, kas sevi izsauks atkārtoti, līdz tiks atrasts risinājums. Tie ir jāraksta tā, lai jūs varētu mainīt rezultātu, nemainot jau uzrakstīto metožu kodu.

Noslēgumā jāsaka, ka šajā rakstā ir parādīts, ka dinamiskā programmēšana ir pieeja, kuras mērķis ir optimizēt noteiktas problēmas risinājumus. Tajā tiek izmantoti iegaumēšanas principi un apakšproblēmu pārklāšanās, lai noteiktu, kad mērķa funkciju var sasniegt ātri, optimizējot nepieciešamās aprēķina darbības.