Fara í innihald

Deili- og drottnunarreiknirit

Úr Wikipediu, frjálsa alfræðiritinu

Í tölvunarfræði eru deili- og drottnunarreiknirit mikilvæg tegund reiknirita. Þau brjóta viðfangsefnið aftur og aftur niður í tvö eða fleiri einfaldari vandamál af sömu eða svipaðri gerð uns þau verða nægilega einföld til að leysast með beinum hætti. Lausnir hinna minni vandamála eru síðan sameinuð til þess að fá lausn á hinu upprunalega vandamáli.

Deili- og drottnunarreiknirit eru auðveldlega útfærð sem ítrunarföll. Þannig eru hlutalausnirnar geymdar á kallhlaðanum.

Einnig er hægt að útfæra slík reiknirit án þess að nota ítrun, en þá eru hlutalausnirnar geymdar í gagnagrind á borð við hlaða, biðröð eða FIFO. Með þessari aðferð er hægt að velja með mun auðveldari hætti hvaða minni vandamál reikniritið skuli fást við næst, sem er mjög mikilvægur eiginleiki í sumum lausnum, svo sem breidd fyrst ítrun og greina og afmarka aðferðinni við bestun falla.

Eitt afbrigði af deili- og drottnunarreikniritum eru minnkunar- og drottnunarreiknirit, þar sem að lokaniðurstaðan er aðeins háð einni milliniðurstöðu. Það getur verið gott að höndla slík verkefni sérstaklega, þar sem þau eru yfirleitt leysanleg með lausnum af hluta hinna minni verkefna. Auk þess er oft auðveldara að greina þau en önnur deili- og drottnunarvandamál.

Reiknirit til þess að finna stærsta gildið í lista af tölum:

Reiknirit StærstaTala  
  Ílag: Listi af tölum L, sem er ekki tómur.
  Úttak: Stærsta talan í listanum L.
  Athugasemd:   Deili- og drottnunaraðferð.
  ef L.stærð == 1 þá
     skila L.haus
  stærst1 ←  StærstaTala(L.haus...L.miðja)
  stærst2 ←  StærstaTala(L.miðja....L.hali)
  ef stærst1 >  stærst22, þá
    stærststærst1
  else
     stærststærst2
  skila stærst
Reiknirit StærstaTala 
  Ílag: Listi af tölum L, sem er ekki tómur.
  Úttak: Stærsta talan í listanum L.
  Athugasemd:  Minnka og drottna.
 ef L.stærð == 1 þá
     skila L.haus
  síðasta = L.stærð - 1;
  stærst ←  StærstaTala(L.haus...L.síðasta)
  ef stærst <  L.hali þá
    stærstL.hali
  skila stærst

Fyrirmynd greinarinnar var „Divide and conquer algorithm“ á ensku útgáfu Wikipedia. Sótt 9. maí 2006.