Eerstejaars practicum. Opdracht 2:

1. Depth-First Search

   start state : ((120)(453)(786)) goal state: ((123)(456)(708))

   1. Doorloop het zoekprobleem met het depth-first zoekalgoritme in single step mode en houdt de queue bij.
      Zodra het algoritme de oplossing heeft gevonden, noteer je de lengte van het pad, de queue van dat moment en het totale aantal doorzochte knopen. Geef ook aan wat het maximaal aantal knopen was dat de queue heeft bevat.
   2. Doorloop hetzelfde probleem in user prediction mode. Hoe kiest het algoritme welke knoop moet worden ge-evalueerd?
   
   
   

2. Breadth-First-Search

   
   

   start state : ((120)(453)(786)) goal state: ((123)(456)(708))

   1. Doorloop de zoekboom met het breadth-first algoritme, in single step mode. Houdt de queue bij.
      Zodra het algoritme de oplossing heeft gevonden, noteer je de lengte van het pad, de queue van dat moment en het totale aantal doorzochte knopen. Geef ook aan wat het maximaal aantal knopen was dat de queue heeft bevat.
   2. Vergelijk de maximale grootte van de queue voor dfs en bfs. Wat valt je op? Was dit te verwachten?
   3. Doorloop hetzelfde probleem in user prediction mode. Hoe kiest het algoritme welke knoop moet worden ge-evalueerd?
   
   
   

3. Greedy-Search

   
   

   Stel het zoekalgoritme op greedy search, zet de start state op ((120)(453)(786)) en de goal state op ((123)(456)(708)).
   Kies als heuristiek city blok.

   1. Doorloop het algoritme eerst in single step mode.
   2. Doorloop het algoritme nu in user prediction mode. Hoe selecteert greedy search de node om te expanderen en waaraan zie je dit in de applet?)
   
   
   

4. A* Search

   
   

   Beantwoord hier dezelfde vragen als bij Greedy Search.
   
   

5. Paardensprong

   
   
   

   Voor de volgende twee opdrachten gebruiken we het volgende applet.
   Stel, je hebt een schaakbord van 3 bij 3 zoals op de afbeelding. Je paard staat op vakje (3,3) en je wilt hem met paardensprongen naar vakje (1,1) krijgen (een paardensprong bestaat uit een beweging van 1 vakje horizontaal en 2 vakjes verticaal of een beweging van 1 vakje verticaal en 2 vakjes horizontaal.)

   1. Teken het schaakbord in de applet. Vergeet niet de begin- en eindknoop te definieren en gebruik de edges om te zorgen dat alle paardensprongen mogelijk zijn. Gebruik nu solve om de oplossing voor de puzzel te vinden.
      Lever de tekstuele representatie (je vind deze onder edit/view/edit text) in.
      Het is helaas niet mogelijk om onder windows de tekst uit je java window te knippen en plakken.. dus mag je het overtypen of tijdens het practicum je applet even laten keuren door een studentassistent
      
   2. Teken nu de volledige zoekboom in het applet, tot een afdoende diepte. Label de states met de coordinaten van het paard.
      Lever de tekstuele representatie van je zoekboom in.
   3. Door nu op het tabblad solve te klikken, is het mogelijk de zoekboom te doorzoeken. Probeer zowel breadth first search als depth first search. Wat zou er kunnen gebeuren als het ook toegestaan was om in states te zoeken waar je net vandaan kwam? Zijn beide algoritmen dan nog steeds geschikt?
   4. Waarom is A* niet zo geschikt in dit geval?
   5. Stel, je hebt een 20x20 veld met als startpositie (1,1) en als doel positie (20,20). Zou je nu wel A* kunnen gebruiken? Zo ja, geef de heuristiek. Zo nee, leg uit waarom niet.
   
   

6. Routeplanner

   Creeer voor deze opdracht een new graph en vervang de tekstuele representatie met de tekst van dit bestand
   Als het goed is staat de tekst nu in het invoerveld. Je moet nu de boom kunnen zien.
   
   De grafiek lijkt op de boom in het boek over het route probleem in Roemenie. Het is de bedoeling om enige zoekstrategieen uit te proberen om te bekijken welke strategieen in dit geval het meest efficient zijn. Als eerste het depth-first-search algoritme. Door op het tabblad solve te klikken is het mogelijk om een algoritme uit te proberen. Dit kun je instellen in Search Algorithms. Onder Search Options kun je instellen of de node heuristics en edge costs weergegeven worden. Beredeneer zelf wat deze getallen inhouden.
   
   
   1. Is DFS een geschikt algoritme voor dit probleem?
   2. Wat is het probleem met dit algoritme?
   3. Probeer nu breadth-first-search. Loop met het autosearch commando alle stappen af. Nu stopt het programma na 50 stappen. Druk op OK om verder te zoeken. Je kunt deze parameter onder search options groter maken (bijv. 500) om langer door te laten zoeken.
      Lijkt BFS een efficient algoritme voor dit probleem? Waarom wel/niet?
   4. Betere algoritmes voor dit probleem zijn de informed search methods. Geef zelf aan wat er zou gebeuren als je een greedy search zou toepassen op dit probleem (deze staat niet in het menu, beredeneer het zelf).
   5. Geef het pad als je greedy search zou gebruiken als 0 de beginnode zou zijn. Is dit de beste oplossing?
   6. De waarde onder de nodes geven de directe afstand (in een rechte lijn), en geven dus de waarde van een heuristiek. Kies nu A* als zoekmethode. Beschrijf uitvoerig wat er gebeurt. Lees hiervoor eerst de tekst uit het boek.