Korteste vej problemet

Foredraget handler om hvordan man, ved hjælp af dynamisk programmering og baglænsoptrævling, kan finde den korteste vej mellem f.eks. to byer, når afstanden mellem alle mellemliggende byer er kendt. Først vil vi, som motivation, se på et eksempel, hvor vi ønsker at bestemme den korteste vej fra Ålborg til Tønder. Dette eksempel vil vi følge gennem hele foredraget, for bedre at kunne få et overblik over den, nogle gange, tunge notation.

Vi vil formulere det generelle beslutningsproblem (som også kan anvendes i andre sammenhænge) og angive en løsningsmetode til korteste vej-problemet, nemlig baglænsoptrævling.

Vi vil gøre antagelser, som gør problemerne mindre komplekse, og dermed nemmere at løse, da foredraget er en introduktion til problemstillinger af denne slags.