Computationele intelligentie
Algemeen 1
Ongeïnformeerd zoeken 2
Breadth-first search 2
Depth-first search 3
Iteratief verdiepen 3
Backtracking 4
Heuristisch zoeken 5
Best-first search 5
Heuristische depth-first search 5
A(*) 6
Zoeken met kosten 9
Cost-based search 9
Heuristische cost-based search 9
A* met kosten 9
Uitputtende depth-first search 11
Branch-and-bound 11
Lokaal zoeken 12
Hill-climbing 12
Random-restart hill climbing 14
Lokale beam search 14
Random-walk hill climbing 15
Simulated annealing 15
Tabu search 17
Evolutie 19
Permutation problems 20
Constraint satisfaction 22
Chronologische backtracking 23
Probleemreductie 23
Dynamische probleemreductie 26
Zoeken met een tegenstander 30
Minimax 30
𝛼-𝛽 pruning 30
Monte Carlo tree search 33
Uncertainty 36
Probability theory 36
Bayesian networks 39
Inference 42
Decision analysis 46
,Algemeen
Zoekprobleem Een tupel 𝑃 = (𝑇, 𝐵, 𝐷, 𝑂), waarvoor geldt:
- 𝑇 is de verzameling van toestanden van 𝑃 (toestandsruimte)
- 𝐵 ⊆ 𝑇 is de verzameling van begintoestanden van 𝑃
- 𝐷 ⊆ 𝑇 is de verzameling van doeltoestanden van 𝑃
- 𝑂 ⊆ 𝒫(𝑇 × 𝑇) is de verzameling operatoren van 𝑃
Zoekproblemen waar de doeltoestand al gegeven is zijn geïnteresseerd in de stappen die nodig
zijn om die doeltoestand te bereiken. Zoekproblemen waar geen doel gegeven is, gaat het
alleen om zo’n doeltoestand te vinden.
Voor een gegeven een zoekprobleem 𝑃 = (𝑇, 𝐵, 𝐷, 𝑂) geldt:
- Een pad 𝑡 is een eindige reeks toestanden die gevormd wordt door het herhaaldelijk
toepassen van de operatoren om een nieuwe toestand te krijgen
- Formeel: een pad 𝑡 ∈ 𝑇 is een eindige reeks toestanden 𝑡 = 𝑡1, ..., 𝑡𝑛 met 𝑛 ≥ 1,
zodanig dat voor elke 𝑘 = 1, ..., 𝑛 − 1 er een 𝑜 ∈ 𝑂 is met (𝑡𝑘, 𝑡𝑘+1) ∈ 𝑜
- De lengte van een pad 𝑡 ∈ 𝑇 met 𝑛 toestanden is gelijk aan 𝑛 − 1
- Een oplossing van 𝑃 is een pad waarvan de eerste toestand een begintoestand is en de
laatste toestand de gewenste doeltoestand
- Formeel: een pad 𝑡 = 𝑡1, ..., 𝑡𝑛 met 𝑡1 ∈ 𝐵 en 𝑡𝑛 = 𝐷
Zoekruimte Verzameling van alle toestanden waarvoor een pad bestaat dat begint vanuit één
van de toestanden uit de verzameling begintoestanden 𝐵
- De doeltoestand moet tenminste in de zoekruimte zitten om bereikbaar te zijn
Zoekgraaf Gerichte graaf 𝐺𝑃(𝑏) = (𝑉, 𝐴) voor een 𝑃 met begintoestand 𝑏 ∈ 𝐵, waarbij:
- Voor elke toestand 𝑡 ∈ 𝑉 geldt dat elke toestand die verkregen kan worden door een
operator op 𝑡 toe te passen, ook in 𝑉 voorkomt
- Formeel: elke toestand 𝑡' waarvoor er een 𝑜 ∈ 𝑂 bestaat met (𝑡, 𝑡') ∈ 𝑜, komt
ook voor in 𝑉
- Alle transformaties van een toestand naar een nieuwe (edges) komen voor in 𝐴
- Formeel: voor alle toestanden 𝑡, 𝑡' ∈ 𝑉 waarvoor een 𝑜 ∈ 𝑂 bestaat met
(𝑡, 𝑡') ∈ 𝑜 geldt dat 𝑡 → 𝑡' ∈ 𝐴
Zoekboom De boom met wortel 𝑏, bestaande uit alle paden in 𝐺𝑃(𝑏) vanuit 𝑏
Het zoeken van een oplossing voor 𝑃 vanuit 𝑏 ∈ 𝐵 is equivalent aan het zoeken naar een
kortste pad naar een doeltoestand 𝑑 in de zoekgraaf 𝐺𝑃(𝑏)
Soorten zoekalgoritmen
- Ongeïnformeerd zoeken: breadth-first search, depth-first search, backtracking
- Heuristisch zoeken: best-first search, A*
- Zoeken met kosten: cost-based search, heuristische cost-based search
- Lokaal zoeken: hill climbing, tabu search, simulated annealing
1
, - Zoeken met tegenstander: minimax, a-b pruning
- Constraint satisfaction: chronologische backtracking, forward checking, backjumping
Eigenschappen van zoekalgoritmen
- Volledigheid: een algoritme is volledig, als het altijd het pad naar de doeltoestand kan
vinden, gegeven dat het probleem ook daadwerkelijk zo’n pad bevat
- Optimaliteit: gevonden pad is van minimale lengte
- Rekentijd: hoeveel rekentijd het kost om het pad naar de doeltoestand te vinden
- Geheugenbeslag: hoeveelheid geheugen dat het algoritme gebruikt tijdens het zoeken
Ongeïnformeerd zoeken
Een algoritme voor ongeïnformeerd zoeken doorzoekt de zoekruimte van een probleem op een
systematische wijze zonder gebruik van extra kennis.
Overzicht van ongeïnformeerde algoritmes en hun eigenschappen met vertakkingsfactor
(hoeveel successors elke knoop heeft) 𝑏 en diepte 𝑑, ervan uitgaande dat het probleem
tenminste één doeltoestand heeft (zie slides voor exacte berekeningen):
Breadth- Depth-first Iteratief Backtracking
first verdiepen
Volledig? Ja Alleen voor eindige Ja Alleen voor eindige
zoekboom zoekboom
Optimaal? Ja Nee Ja Nee
Rekentijd 𝑂(𝑏 )
𝑑 𝑑
𝑂(𝑏 ) 𝑂(𝑏 )
𝑑 Iets minder dan
dynamische DFS
Geheugen 𝑂(𝑏 )
𝑑 𝑑
𝑂(𝑏 ) 𝑂(𝑏 · 𝑑) Minder dan
dynamische DFS
Breadth-first search
→ Doorzoekt een zoekboom laag voor laag
bfs wordt aangeroepen op een queue (FIFO) die in eerste instantie alleen de wortel bevat van
een expliciet gegeven zoekboom.
procedure bfs(L)
if empty(L) then return nil
else
t = dequeue(L);
if goal(t) then return t
else
L = enqueue(L,successors(t));
bfs(L)
endprocedure
Achtereenvolgens bevat de queue:
2
, 1. Q = [1]
2. Q = [4,3,2]
3. Q = [6,5,4,3]
4. Q = [8,7,6,5,4] ...
Dynamische variant
- Zoekboom is slechts impliciet gegeven
- Deel van zoekboom wordt dynamisch gegenereerd door de knopen in breadth-first
volgorde te expanderen door zijn successors te genereren
- Er kunnen paden met cycles ontstaan als een eerder voorgekomen knoop nog een keer
gegenereerd wordt
- Herhaalde toestanden kunnen voorkomen worden door bij het expanderen van knoop
nooit een toestand op te nemen die:
- Gelijk is aan de parent van de huidige knoop
- Ook al voorkomt op het pad van deze knoop naar de wortel
- Al eerder is gegenereerd
Depth-first search
→ Doorzoekt een zoekboom pad voor pad
dfs wordt aangeroepen op een stack (LIFO) die in eerste instantie alleen de wortel bevat van
een expliciet gegeven zoekboom.
procedure dfs(L)
if empty(L) then return nil
else
t = pop(L);
if goal(t) then return t
else
L = push(L,successors(t));
dfs(L)
endprocedure
Dynamische variant: successors van een knoop worden gegenereerd om knoop te expanderen.
Een dieptegrens specificeert een maximum diepte die moet worden doorzocht om oneindige
recursie te voorkomen.
Iteratief verdiepen
→ Doorzoekt een zoekboom door telkens een stap dieper te zoeken met DFS
iterative wordt aangeroepen met minimale dieptegrens en stapgrootte en de functie dfs
voert begrensde depth-first search (returnt toestand en boolean of de hele boom is doorlopen).
3
