Topic 7 Flashcards
Leg de werking van de uniform cost algoritme uit en wat de nadeel is van deze algoritme.
De uniform cost algoritme neemt telkens het kortste pad in de QUEUE genereert daar de kinderen van en sorteert vervolgens de volledige QUEUE (volgens geaccumuleerde kost)
Add the new paths to the QUEUE and sort the entire QUEUE (by accumulated cost)
Nadeel:
Vanaf dat er een pad naar het doel is in de QUEUE is er niet meer voldaan aan de WHILE loop, dit zorgt ervoor dat ons algoritme stopt met zoeken.
Het gevonden pad is niet noodzakelijk het korte en dus meest optimale pad.
Als de algoritme verder had gezocht zou het misschien wel een kortere pad gevonden hebben.
Hoe probeert men het probleem met de uniform cost algoritme aan te pakken?
Leg uit:
Het probleem is dat men te vroeg stopt met zoeken.
We zouden dus moeten verder zoeken, het gevaar is natuurlijk wel dat de rekentijd zal toenemen.
We proberen hier een evenwicht in te vinden door bepaalde takken van de boom te snoeien.
Met de branch-and-bound principle, kan men van zodra er een pad naar het doel gevonden is beginnen snoeien.
De kost van het tot nu toe gevonden pad is een bovengrens voor kortst mogelijke pad dat kan gevonden worden. We noemen die kost “kleinst_gevonden_kost”. Paden die we tegenkomen tijdens de analyse van de boom die langer worden dan het “kleinst_gevonden_kost”. moeten niet meer onderzocht worden, want die paden zullen toch nooit korter zijn dan het “kleinst_gevonden_kost”.
Dit zorgt er voor dat de branching factor gereduceerd wordt wat op het gebied van rekentijd een groot verschil kan maken.
Leg de werking van de optimal uniform cost algoritme uit en wat de probleem is aan deze algoritme.
Optimal uniform cost algorithm is uniform cost algorithm uitgebreid met de branch and bound principle.
We blijven verder zoeken, tot het pad naar het doel eerst komt te staan in de QUEUE in plaats van tot er een een pad naar het doel in de QUEUE gevonden wordt.
Het weggooien van paden gebeurt niet in optimal uniform cost.
WHILE (QUEUE is not empty AND first path does not reach goal)
Het probleem met deze algoritme is dat er geen rekening wordt gehouden met wat er nog komt.
Wat zijn de criteria-eigenschappen voor de optimal uniform cost?
Compleet, meestal.
Kan het optimale pad vinden als die bestaat.
Geheugen en snelheid, in het slechtste geval net zo slecht als breadth-first
-> Zelfs slechter want de sortering komt er bij
Leg de werking van de extended uniform cost algoritme uit:
Extended uniform cost algoritme is de optimal uniform cost algoritme maar we gaan de geaccumuleerde cost vervangen door de f waarde:
f(path) = cost(path) + h(endpoint_path)
-> Geaccumuleerde cost + functie h (de straight line distance als heuristiek)
Hoe lager de f-waarde, hoe meer kans dat een pad via die knoop tot het optimale pad tot het doel leidt.
Dit is echter een kans, geen zekerheid.
Add the new paths to the QUEUE and sort the entire QUEUE (by f = cost + h)
Wat zijn de criteria-eigenschappen voor de extended uniform cost?
Compleet en optimaal voor een goede heuristissche functie h
Snelheid en geheugen:
In het ergste geval geen verbetering tov ‘branch and bounded extended uniform cost of optimal uniform cost’
Voor goede heuristische functie kan het zoeken resulteren in het bezoekn van minder nodes.
Hoe kan de extended uniform cost verbeterd worden?
De extended uniform cost algortime kan verbeterd worden door de redundante paden weg te gooien.
Als er een pad is van S naar SA met kost 4 en een pad van S naar SDA met kost 9, dan is SDA een redundante pad en kan het genegeerd worden, want er is een kortere pad mogelijk en SDA zal dus nooit tot een optimaal pad kunnen leiden.
IF the QUEUE contains: a path P terminating in I, with cost cost_P a path Q containing I, with cost cost_Q cost_P cost_Q THEN delete P
Leg de werking van de A* algoritme uit.
De A* algoritme is de uniform cost algoritme met alle technieken die we gezien hebben:
Branch and bound extention:
WHILE (Queue !empty and first path !reach goald)
Estimate extention:
Add the new paths to the QUEUE and sort the entire QUEUE(by f = cost + h)
Redundant path deletion extention: IF the QUEUE contains: a path P terminating in I, with cost cost_P a path Q containing I, with cost cost_Q cost_P cost_Q THEN delete P
