Tips

Oblig 3 - 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ø med decreaseKey-operasjonen.

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]. (Todimensjonale arrayer anbefales ikke for denne oppgaven i Java eller C/C++, men går greit i Python med NumPy; spør om du vil vite hvorfor...).
• 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), og 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 tre muligheter:
  • Lettest: 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).
  • Bruk den innebygde. Både i Java, Python og C++ støtter denne ikke decreaseKey, så dette kan bli litt stygt. En må ikke fjerne og sette inn igjen, siden fjerning typisk bruker O(n)! Istedet må en bruke en wrapperklasse (NodeInPriQueue):
    • NodeInPriQueue inneholder kostnaden en node var satt inn med og en referanse til en node (det holder altså ikke å bare referere til kostnaden i noden, siden kostnaden må være konstant etter innsetting, men kostnaden i noden kan endre seg!). Den må også implementere riktige metoder, f.eks. arve fra og implementerer Comparable i Java.
    • Node må så inneholde en boolsk variabel for hvorvidt den allerede er tatt ut av køen eller ikke.
    • Når en setter inn en node, bare opprett en ny NodeInPriQueue-wrapper og sett denne inn.
    • Men, når en tar ut en wrapper, så sjekk om noden den refererer til allerede er tatt ut via en annen wrapper - i såfall har det skjedd en decreaseKey, og denne er en levning etter før decreaseKey og skal forkastes (og en går videre på neste element i køen med en gang).
      

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!

PS! Siden en vil få veldig liten tid på andre innlevering er det viktig at en leverer en OK førsteimplementasjon. Si derfor ifra om noe tar lang tid på denne oppgaven så har vi hjelp, evt. ferdig kode, å tilby.

Oblig 1

Spørsmål: Hva er egentlig forskjell på 1c) 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å.