AAIP – Hoofdstuk 4
Zoekalgoritmen & Optimalisatie
4.1 Waarom dit hoofdstuk belangrijk is
Zoekalgoritmen vormen de ruggengraat van klassieke AI.
Ze bepalen hoe een systeem:
- oplossingen vindt,
- routes plant,
- problemen oplost,
- en beslissingen maakt.
Zelfs moderne AI‑systemen gebruiken nog steeds zoek- en optimalisatieprincipes,
vooral in planning, reasoning, reinforcement learning en agent‑systemen.
4.2 Wat is een zoekprobleem?
Een zoekprobleem bestaat uit:
- Een starttoestand
- Een set mogelijke acties
- Een toestandsruimte (alle mogelijke situaties)
- Een doeltoestand
- Een kostenfunctie (optioneel)
Voorbeeld: een robot die van punt A naar B moet navigeren.
4.3 Ongeïnformeerde zoekalgoritmen
Deze algoritmen hebben geen kennis over het probleem behalve de structuur.
4.3.1 Breadth‑First Search (BFS)
- Zoekt eerst alle buren op hetzelfde niveau
- Vindt altijd de kortste oplossing
- Maar gebruikt veel geheugen
4.3.2 Depth‑First Search (DFS)
- Gaat zo diep mogelijk een pad in
- Weinig geheugen
- Kan verdwalen in diepe paden
4.3.3 Uniform Cost Search
- Zoekt de goedkoopste oplossing
- Gebruikt een prioriteitsqueue
4.4 Geïnformeerde zoekalgoritmen (heuristieken)
Deze algoritmen gebruiken extra kennis om sneller te zoeken.
4.4.1 Heuristieken
Een heuristiek is een schatting van de afstand tot het doel.
4.4.2 Greedy Best‑First Search
- Zoekt naar de toestand die het dichtst bij het doel lijkt
- Kan snel zijn, maar niet optimaal
4.4.3 A* (A‑star)
Het belangrijkste zoekalgoritme in AI.
- Combineert kosten tot nu toe + heuristiek
- Is optimaal als heuristiek “admissible” is
- Wordt gebruikt in navigatie, games, robots, planning
A* is de koning van zoekalgoritmen.
4.5 Optimalisatie in AI
Optimalisatie betekent: de beste oplossing vinden binnen beperkingen.
4.5.1 Hill Climbing
- Lokale optimalisatie
- Kan vastlopen in lokale maxima
4.5.2 Simulated Annealing
- Laat soms slechtere stappen toe
- Kan ontsnappen uit lokale maxima
4.5.3 Genetic Algorithms
- Gebaseerd op evolutie
- Mutatie, selectie, crossover
- Goed voor complexe optimalisatieproblemen
4.6 Toepassingen van zoekalgoritmen
- Routeplanning (Google Maps, GPS)
- Game‑AI (schaken, Go, videogames)
- Robotnavigatie
- Planning en scheduling
- Reinforcement learning
Zoekalgoritmen zijn overal — zelfs als je ze niet ziet.
4.7 Reflectie‑opdracht
Beantwoord de volgende vragen schriftelijk:
- Leg in je eigen woorden uit wat een heuristiek is.
- Waarom is A* zo belangrijk in AI?
- Noem een situatie waarin BFS beter is dan DFS.
- Welke optimalisatietechniek spreekt jou het meest aan en waarom?