Er det noen som har mulighet til å forklare litt utdypende om hvorfor det er en kobling mellom DAG-SP og dynamisk programmering?

Blackboard-spørsmål fra 2018

Algoritmene i pensum baserer seg i all hovedsak på rekursiv dekomponering, der instanser brytes ned i andre instanser av samme problem. Om vi lar disse instansene representeres ved noder, og dekomponeringen som kanter til en instans fra dens delinstanser (mer uformelt, delproblemer), så får vi en rettet delinstansgraf, oftest kalt en delproblemgraf. (For litt mer om dette, se s. 370 i boka.)

For at vi skal kunne finne en løsning, må denne grafen være velfundert – altså, om vi løser problemet rekursivt må vi ikke ende opp med uendelig rekursjon. Når vi har et endelig antall delinstanser, så tilsvarer det bare at grafen vår må være asyklisk, altså en DAG, som representerer avhengigheter som må respektres: Dersom vi har en kant \((u,v)\), må vi løse instansen som tilhører \(u\) før vi løser den for \(v\). Det vil si, vi må løse instansene i topologisk sortert rekkefølge.

Om du for eksempel vil sortere en sekvens basert på splitt-og-hersk-tankegangen, så vil du for en instans (sekvens) \(s\) få kanter \((\ell,s)\) og \((r,s)\), der \(\ell\) og \(r\) er venstre og høyre halvdel av \(s\), og \(\ell\) og \(s\) dekomponeres på samme måte, som gir deg et tre. Løvnodene må løses (sorteres) først, og så konstruerer du løsninger oppover i treet, ved å bygge på løsningene i barnenodene.

Vi kan generelt løse slike problemer rekursivt, ved å starte i noden som representerer den opprinnelige instansen, dekomponere den i delinstanser, løse delinstansene rekursivt, og så konstruere løsningen. Og nor det ikke er noe overlapp, så er det ikke noe problem. Men dersom vi kommer innom noen noder (delinstanser) mer enn én gang, så vil vi fort besøke noder lenger vekk mange ganger, og vi ender med eksponentiell kjøretid. Løsningen på det er å lagre løsningen knyttet til hver delinstans – f.eks. kan vi tenke oss at noden \(u\) har et felt \(d\) som inneholder løsningen. Det vil si, når vi har løst \(u\), så finner vi løsningen i \(u{.}d\), og om vi har kanter \((u_i,v)\) til node \(v\), så baserer vi oss på \(u_i{.}d\), for alle forgjengere \(u_i\). Når vi lagrer delløsninger slik, omtaler vi det gjerne som dynamisk programmering (selv om det egentlig er en litt uformell betegnelse).

For eksempel, i stavkuttingseksemplet (delkapittel 14.1) vil en node kunne representeres ved stavlengden \(n\), og vi har kanter \((n-i,n)\) for \(i=1\dots n\). Formelen for å finne svaret \(q\) for én node er gitt av linje 7 i pseudokoden for Memoized-Cut-Rod-Aux på side 368 (uten at den snakker om graf-formalismen):

\[n{.}q = \max_{1\leq i < n}\ (n-i){.}q + p[i]\]

Her har vi latt kantene være implisitte, men om vi lar enhver kant \((n-i,n)\) få vekt \(w(n-i,n)=i\), og døper om \(q\) til \(d\), så kan vi skrive opp den følgende varianten:

\[v{.}d = \max_{(u,v)\in E}\ u{.}d + w(u,v)\,.\]

Med andre ord, ved å sette opp delinstansene og avhengighetene mellom dem som en graf, har vi plutselig endt opp med en dekomponering for lengste vei i en graf. Om vi i stedet hadde brukt \(w(n-i,n)=-i\), så hadde vi endt opp med Dag-Shortest-Path.

På samme måte er f.eks. rutenettet vi setter opp for LCS-problemet også en graf, der hver celle er enn node, og vi har kanter til cellen over, til venstre og over til venstre, med kantvekter \(0\), \(0\) og \(1\). Igjen skal vi bare finne lengste vei. Ekvivalent, om vi bytter \(1\) med \(-1\) så har vi igjen Dag-Shortest-Path, bare på en annen graf.

Generelt er altså løsninger på problemer ved hjelp av DP bare varianter av Dag-Shortest-Path på ulike grafer. Det er ikke alltid vi skal ta minimum av summen av \(u{.}d\) og \(w(u,v)\) – så det er ikke alltid det er nøyaktig likt Dag-Shortest-Path, men strukturen er stort sett svært lik, og vi har at \(v{.}d\) er en funksjon av verdiene \(u{.}d\) og \(w(u,v)\) for alle inn-naboer \(u\).

Så på den måten er Dag-Shortest-Path et eksempel på DP, og DP er i all hovedsak ekvivalent med Dag-Shortest-Path.

En ting det er verdt å merke seg er at sånn som vi ofte implementerer Dag-Shortest-Path, tross den rekursive dekomponeringen beskrevet over, er ikke at vi henter inn verdiene fra forgjengere (pulling), men at vi sender verdiene til etterkommere (reaching). Det er en praktisk detalj, siden vi ofte har lettere tilgang til ut-kanter enn inn-kanter. Idet vi besøker node \(v\) vil vi uansett ha vurdert ethvert par \((u{.}d, w(u,v))\) for forgjengere \(u\) (ved hjelp av Dag-Shortest-Path, som bare er en fleksibel implementasjon av minimums-operasjonen), så resultatet blir det samme. Vi har fortsatt

\[v{.}d = \min_{(u,v)\in E}\ u{.}d + w(u,v)\,.\]