Path finding i virkeligheden

Det at kunne finde korteste veje i netværker har mange anvendelser, som for eksempel ruteplanlægning (google maps) eller telekommunikation. I dette foredrag giver vi en kort introduktion til hvilke slags problemer indenfor dette område der er interessante og lidt teoretisk baggrund til hvordan disse problemer løses, for eksempel ved hjælp af Dijkstra’s algoritme.

Derefter vil vi præsentere nogle forbedringer i algoritmerne til at håndtere større mængder af data (eller større netværk), som falder inden for rammerne af A*-søgning. Vi vil også kort nævne to elementer, der besværliggør anvendelsen i virkeligheden: betingelser og flere optimeringskriterier. Disse elementer indgår for eksempel i planlægning af flyruter, ruteplanlægning for automatiserede køretøjer og arbejdsplanlægning i transportsektoren.