Deili- og drottnunarreiknirit

Í 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.

Útfærsla

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.

Afbrigði

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ærst ← stærst1
  else
     stærst ← stæ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ærst ← L.hali
  skila stærst

Tengt efni

• Þrepasönnun
• Deilið og drottnið (stjórnmálafræðileg hugmyndafræði)
• Akra-Bazzi aðferðin
• Meistarasetningin

Heimildir

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