Alle stof die behandeld wordt bij het vak Computationele Intelligentie (CI), duidelijk en gestructureerd samengevat. Gebaseerd op de hoorcolleges en slides daarvan.
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 𝐺𝑃(𝑏)
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
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:
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Suniht. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.78. You're not tied to anything after your purchase.
