zoekpaden

Zoekpaden is een term uit informatica en kunstmatige intelligentie die verwijst naar een opeenvolging van toestanden of stappen die leidt van een beginpunt naar een doel in een zoekruimte. Een zoekpad verschijnt vaak in grafen of toestandsruimten, waarin elke opeenvolgende toestand is verbonden door een overgangsactie met een kostenwaarde.

Formeel kan een pad worden gezien als een reeks toestanden s0, s1, ..., sk waarbij elk paar (si, si+1) via een overgangsactie met elkaar verbonden is. Het pad heeft een totale kostenwaarde die optelt over de overgangen. Een kortpad is een pad met minimale kosten, wat in veel probleeminstellingen overeenkomt met de optimale oplossing.

Zoekpaden ontstaan en worden gevonden met search-algoritmen zoals breadth-first search (BFS), depth-first search (DFS) en kosten-gebaseerde methoden zoals Dijkstra’s algoritme en A*, die heuristieken gebruiken om de zoekruimte efficiënter te doorzoeken. Afhankelijk van de probleeminstellingen kan een algoritme volledig en/of optimaal zijn. Het soort pad kan afhankelijk zijn van doelstelling: een enkel pad kan volstaan of men kan alle mogelijke paden willen verkennen.

Toepassingen van zoekpaden omvatten routeplanning en navigatie, robotnavigatie, puzzels en planning in AI, en algemene probleemoplossing waarbij een reeks acties tot een doel leidt. Belangrijke overwegingen zijn de omvang van de zoekruimte, geheugenverbruik en de keuze van heuristieken. Een gerichte heuristiek kan zo de uitvoering versnellen zonder de geldigheid van de oplossing in het geding te brengen.