Topic 6

Question 1

Heuristische functies:

Answer 1

Met heuristische functies proberen we de kwaliteit van de vorige methoden te verbeteren.

_
- Hiervoor moeten we domeinspecifieke kennis (kennis omtrent het probleem) kunnen gebruiken.

• We moeten ervoor zorgen dat het algoritme overal toepasbaar blijft zodat we het niet telkens hoeven te herimplementeren
  _
• Een heuristische functie probeert een getal te plakken op een toestand. Dat getal moet inschatten hoever de toestand ligt van het doel dat moet bereikt worden.

f(T) notatie: De functie f probeert op elke toestand T een getal te plakken dat inschat hoe ver de toestand van het doel verwijderd is (of hoe goed de toestand dus is)

-

Question 2

Geef 3 voorbeelden van heuristische functies:

Answer 2

1) Afstand in vogelvlucht
- Vanuit elke node, de afstand in vogelvlucht nemen, in plaats van de effectieve route te berekenen.

Let op: Kan een zeer slechte inschatting zijn. Soms is de afstand in vogelvlucht klein maar is de effectieve route veel hoger.
De afstand in vogelvlucht is hier dus een zeer slechte inschatting.

2) f1 (T) & f2 (T)
Functie f1 telt het aantal juist geplaatste vakjes.

Functie f2 telt het aantal verkeerd geplaatste vakjes.
- Meestal zijn heuristiek die een afstand van het doel uitdrukken de meest bruikbare heuristieken
-> Inschatting hoe ver de toestand van de doeltoestand verwijderd is.
Hoe kleiner f2 hoe dichter bij de oplossing en hoe groter hoe verder.

Let op: Als er 8 vakjes zijn en f1 (T) = 3 , dan f2(T) = 5!
-> Als er drie juist zijn dan er 5 verkeerd, 3 zou dan een onderschatting zijn omtrent hoever we van het doel verwijderd zijn, namelijk 5!

3) Manhattan Distance
f(3) = De som van (de horizontale + verticale afstand dat elk vakje ver is van de doeltoestand)