2 AI: Graphsearch

You understand what a graph is and how it represents knowledge (Graph = Knowledge Representation)

Een grafiek is een datastructuur met nodes (toestanden/objecten) en edges (transities). Het wordt gebruikt om kennis en toestanden van een systeem te modelleren.
You can explain the difference between dense and sparse graphs (Dense vs Sparse)

You can describe how graph search represents planning (Graph Search = Planning)

Een grafiek laat toe om een pad te zoeken van een start-node naar een doel-node via een reeks acties of transities = planning in AI.

You understand what a graph is and how it represents knowledge (Graph = Knowledge Representation)

Een grafiek is een datastructuur met nodes (toestanden/objecten) en edges (transities). Het wordt gebruikt om kennis en toestanden van een systeem te modelleren.
You can explain the difference between dense and sparse graphs (Dense vs Sparse)

You can describe how graph search represents planning (Graph Search = Planning)

Een grafiek laat toe om een pad te zoeken van een start-node naar een doel-node via een reeks acties of transities = planning in AI.

You understand the difference between adjacency list and matrix (Graph Implementation)

Een adjacency list is geheugen-efficiënt voor sparse graphs. Een adjacency matrix is sneller voor dense graphs en maakt snelle connectiviteitschecks mogelijk.

You know different types of graph search (Graph Search Types)

Ongeïnformeerde zoekmethodes:
 – Depth-First Search (DFS) = gaat zo diep mogelijk, gebruikt een stack.
 – Breadth-First Search (BFS) = bekijkt eerst alle naburen, gebruikt een queue.
Ingevoerde zoekmethodes:
 – Dijkstra = gebruikt kosten op edges om het goedkoopste pad te zoeken.
 – A*: gebruikt heuristieken om sneller het doel te vinden.

You can describe how DFS works and its connection to recursion (DFS = Recursive)

DFS zoekt diep in een pad, en backtrackt wanneer het vastzit. Het is gemakkelijk recursief te implementeren.

You understand how BFS works and why it's not recursive (BFS = Queue)

BFS gebruikt een wachtrij en zoekt eerst op breedte. Moeilijk recursief te maken omdat het queue-gebaseerd is.

You know how Dijkstra’s algorithm works and its greedy nature (Dijkstra = Cost-Based Greedy)

Dijkstra berekent het goedkoopste pad naar elke node. Het kiest altijd de goedkoopste nog onbekende node – greedy gedrag.

You understand the role of heuristics in A and how it improves Dijkstra (A = Dijkstra + Heuristic)

A* combineert de huidige kost met een geschatte afstand (heuristiek) naar het doel. Dit maakt het sneller dan Dijkstra, zolang de heuristiek goed is.

You understand constraint satisfaction problems and their use of backtracking (CSP = Graph + Backtracking)

CSP’s zoeken naar oplossingen die voldoen aan beperkingen (bv. sudoku, kleurproblemen). Gebruiken vaak backtracking door de graph.

You can identify real-world applications of CSPs (CSP Examples)

Voorbeelden; sudoku, cryptarithmetic, regio-kleuring, puzzels, mazes. Hierbij wordt gezocht naar geldige configuraties volgens regels.