Tips

Oblig 2 - A*-søk

Vi skriver her litt om datastrukturene som bør inngå i denne oppgaven. Siden en skal bevege seg i en dynamisk generert graf må datastrukturene bli litt mer kompliserte. En "konstruerer" så å si grafen mens en beveger seg i den. En trenger typisk minst en oppslagsstruktur (hashmap, splaytre el.l.) og en prioritetskø.

Skisse:

• Objektene som inngår er typisk et Board (som representerer et spillebrettkonfigurasjon; dette er typisk nøkkelen i oppslag i datastrukturer) og en annen klasse Node (som er en node i tilstandsgrafen vår, og inneholder et Board, foreldrepeker osv.).
• For hvert steg i algoritmen så står en i en Node u. Da må en se på hvilket Board som ligger lagret i denne noden, og så generere de <= 4 andre brettene en kan gå til.
• For hvert av disse brettene kan det hende at en har utforsket de før. Derfor må en slå opp, med en Board-instans som nøkkel, i en HashMap el.l. som inneholder alle hittil besøkte noder. Dersom en altså kommer inn igjen i en allerede utforsket del av tilstandsgrafen så vil disse tilstandene ligge i en HashMap og kan hentes inn igjen med den informasjonen som blei lagret på de da.
• Dessuten trenger en en prioritetskø for algoritmen.

Detaljer:

• Board - Denne vil typisk inneholde en array av lengde N*N til å lagre feltene i (gjerne av datatypen "byte", siden dette er minneintensivt, og N*N <= 100). I tillegg bør en lagre den rad og kolonne som 0 ligger i sånn at en slipper å søke etter denne. Oppslag i en endimensjonal array typisk gjøres med data[row*n + col]. 
• Node - Denne må inneholde en Board-instans, kostnader og heuristikker for noden, en foreldrepeker (hvilket Node-objekt kom en fra), muligens hvilken retning foreldren ligger i (ikke strengt nødvendig men gjør utskrift lettere), eventuelt også en eller annen informasjon som sier noe om prioritetskøstatus (avhenger av køen).
• Å lagre grafen - Tidligere har en altså brukt arrayer for dette (f.eks. en parent-array der node-indeksen fungerer som oppslagsnøkkel); nå må dette generaliseres siden grafen er mye større enn den biten vi utforsker. Node-objektene representerer noder i grafen mens Board-objektene tilsvarer "node-indekser".
  • Java: Bruk HashMap<Board, Node>. Board må da implementere hashCode og equals (se Java API-dokumentasjonen for equals). equals sjekker rett og slett at arrayene er identiske, mens hashCode må returnere en hash -- et greit valg er "data[0] + 29(data[1] + 29 * (data[2] + ...)))" (kodet som en for-løkke selvfølgelig).
  • Python: Bruk en vanlig dict. Her må __hash__ og __eq__ implementeres, på samme måte som i Java.
  • C++: Bruk en std::map<Board, Node>. Her må Board::operator< implementeres for å sammenligne brett; bare sammenlign først etter første element, så etter andre osv.
• Prioritetskø - Det er et problem at to Noder med samme Board kan legges inn i køen. Det er to muligheter:
  
  • Lettest: Bruk den innebygde, men sjekk alle Nodene du tar ut av køen, om du har sett på dette brettet før. Det er greit at to Noder med like brett ligger i køen, så lenge vi kun ser på det beste, altså det som blir tatt ut av køen først.
  • Implementer decreaseKey(), sånn at du bare sparer på Noden med minst verdi.
    • Bruk et tredjepartsbibliotek (og henvis til det og legg ved en link for nedlasting). Se under!
    • Lag din egen (typisk binomial heap). En vil typisk lagre nødvendig informasjon i Node (eller en klasse denne arver fra) for å kunne gjøre decreaseKey på O(log n) (for binomial heap lagrer du indeksen noden har i heapen i noden). Eller du kan lage en ny klasse der du bruker metoder i innebygde prioritetskøen.

Tredjeparts prioritetskøer

Et søk etter "java fibonacciheap" (som er asymptotisk raskest) gir f.eks. denne som virker veldig enkel å bruke: http://lucene.apache.org/nutch/apidocs-0.8.x/org/apache/nutch/util/FibonacciHeap.html (jeg har faktisk ikke testet den, men Apache-relaterte Java-prosjekter pleier å ha OK kvalitet).

Biblioteket den ligger i er på 60 megabyte, så jeg har hentet ut akkurat filen du trenger og lagt den her. Du trenger bare nevne at du bruker "Nutch sin fibonacci-heap" i besvarelsen dersom du bruker denne.

Om du bruker denne så bør du ikke bruke "contains"-metoden, men heller ha en boolsk variabel i Node-klassen som angir hvorvidt staten er tatt ut av køen eller ikke.

Andre tips? Send inn!

Oblig 1

Spørsmål: Hva er egentlig forskjell på 1b) og 1d) (top-down vs. bottom-up)?

Svar:

top-down:
Løs et problem, og ta underproblemene som de kommer. Eksempel med å legge sammen de N første kvadrattallene:

int sumSquare(int N){
    if (N==1) return 1;
    return N*N+sumSquare(N-1);
}

(I tillegg spørres det i obligen etter memoisering sammen med top-down, så en må da også ha en cache for å se om en gitt N er spurt om før.)

bottom-up:
Lag en formel, og regn ut alle elementene fra bunnen av. Samme eksempel som før:

int [] squares = new int[N];
squares[1] = 1; // 1^2 == 1
for (int i=2;i<N;i++){
    squares[i]=i*i+squares[i-1];
}

I grunn er det samme ting du må gjøre i obligen, bare litt mer komplisert enn å regne ut sum av kvadrater. Det trenger ikke være noe forskjell i formler du bruker, det er bare rekkefølgen du løser underproblemene på som vi ser på.