Topic 5 (Blind search) Flashcards
Beschrijf de evaluatiecriteria die gebruikt worden om algoritmen te vergelijken met elkaar.
Completeness
Vindt het algoritme altijd een pad?
Speed: Hoogste aantal paden dat zouden moeten gecreëerd worden.
Maximaal aantal paden die door het algoritme moet berekend worden.
Memory: Hoogste aantal paden dat zouden moeten bijgehouden worden?
Maximaal aantal paden dat in het geheugen moet opgeslagen worden.
Welke waarden zijn belangrijk bij de evaluatie:
Drie waarden zijn daarbij belangrijk:
- d, de diepte van de boom
- b, de (gemiddelde) branching factor van de boom
- m, de diepte van de minst diepe oplossing.
Criteria voor depth first search:
Completeness:
Compleet onder volgende voorwaarden:
- Spelboom bevat geen oneindige takken. Boom/netwerk moet eindig zijn (finite net)
- Er mogen geen lussen voorkomen
Speed:
Uitgaan van het slechtste geval: de goal-node zit helemaal rechts.
Alle nodes moeten bezocht worden door de diepte eerst voordat de oplossing gevonden kan worden.
-> b^(d+1)-1/b-1
-> O(b^d)
Memory
Maximaal aantal nodes/paden tellen dat in het geheugen moeten opgeslagen worden
Wordt bereikt als de nodes/paden in de meest linker tak gegenereerd worden.
Van de laatste node wordt max b nodes gegenereerd van alle andere nodes (b-1)
- > Wanneer een node bezocht wordt wordt die verwijderd uit de queue.
- > ((b-1)*d)+1
- >
- 1 want voor de laatste niveau tellen we eentje te weinig
- > O(b*d)
—-> Vindt niet altijd het kortste pad
Criteria voor breadth first search:
Completeness:
Altijd & zonder voorwaarden compleet
- Ook bij oneindige takken/infinite nets: kan niet vast komen zitten in oneindige takken
- Ook zonder loop checking
Speed:
Max aantal nodes die bezocht moeten worden tot oplossing gevonden is.
-> Aantal nodes tot diepte m (minst diepe oplossing)
O(b^m)
—-> Vindt altijd het kortste pad
Memory:
Max aantal nodes dat opgeslagen moet worden tot diepst mogelijke oplossing gevonden wordt.
-> Alle ancestors werden reeds bezocht dus worden van de QUEUE verwijderd en daarvan worden kinderen gegenereerd
-> Max aantal kinderen bereik je in de laatste niveau ‘m’
->O(b^m)
Non-deterministic search
Leg uit:
Bij non-deterministic search gaan we nieuwe paden niet van voor of van achter maar gewoon willekeurig in de QUEUE invoeren.
-> Add the new paths in random places in the QUEUE
Iterative deepening
DFS & BFS hebben voor- en nadelen
Met iterative deepening proberen we de voordelen te combineren.
We voeren diepte eerst uit tot een bepaalde diepte. Indien de oplossing niet gevonden wordt tot op een bepaalde niveau gaan we telkens een niveau dieper.
We starten dus bij niveau 1, passen diepte-eerst toe. Indien we geen oplossing gevonden hebben, starten we opnieuw diepte-eerst, maar nu tot op niveau 2. We gaan zo verder tot we een oplossing gevonden hebben, of tot de volledige boom doorzocht werd (en er dus geen oplossing is).
Depth = 1
WHILE(goal is not reached)
- perform Depth limited search
- Depth += 1
DLS:
Queue create
->rehect
->add
Criteria: Iterative deepening search
Compleet:
Ja
Vindt het kortste pad (gelijk aan breadth first)
Memory:
Iterative deepening is Depth first tot op diepte m dus net als Breadth first is de complexitieit O(b*m)
Speed:
Algoritme bestaat uit het meerdere keren uitvoeren van diepte eerst tot op een bepaalde diepte.
We gaan ervan uit dat telkens alle knopen moeten bekeken worden, tot op niveau m.
Centrale vraag:
Hoeveel werk hebben we teveel gedaan door de eerste kleinere bomen te doorzoeken i.p.v. onmiddelijk te zoeken tot op niveau m.
(onmiddelijk zoeken tot niveau m is niet mogelijk -> getal m is niet gekend bij een willekeurige boom)
Aangezien tot op het niveau m-1 er O(b^m-1) werkt verricht is, en aangezien O(b^m-1) significant, om niet te zeggen veel kleiner is dan O(b^m), valt de schade nogal mee. Iterative deepening vergt meer werktdan breedte-eerst op zich, maar aangezien het geheugengebruik beter is, is dit een zeer goede trade-off.
-> Iterative deepening is eigenlijk het enige praktisch bruikbare blind search algoritme
dat we gezien hebben.
