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:

Detaljer:

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