Søgning og optimering

Søgning og optimering (S&O)

Motivation:
En stor del af de problemer der skal løses maskinelt i industrien kan formulereres som optimerings- og søgeproblemer over et meget stort rum af muligeløsninger. Eksempler går fra software til løsning af logistiske problemer,såsom transport af varer, over web-caching, til software der kan slå Kasparov i skak.Mange af disse optimerings- og søgningsproblemer, men ikke alle, vil være vanskelige, i den forstand at der ikke er kendte effektive algoritmer, der løser dem ipraksis. For disse problemer findes en række teknikker til at finde tilfredsstillende ikke optimale løsninger.

Målbeskrivelse:
Målet med kurset er at sætte deltagerne i stand til

at kunne identificere et let problem,så de problemer der hurtigt kan løses optimalt ikke bliver løst approximativt med heuristiske teknikker.

omvendt, at kunne identificere et svært problem, så man ikke bruger kraft på forgæves at finde en effektiv algoritme der løser problemet optimalt, men anvender heuristiske teknikker, for at finde en tilfredsstillende approximativ løsning.
at vide hvilke teknikker, der er til rådighed og have en fornemmelse for hvilke teknikker der passer til hvilke problemer.

Indhold:
Søgeproblemer med effektive løsninger:

Max-flow algoritmer, lineær programmering ....

Identifikation af vanskelige problemer:

Kompleksitetsklasserne P og NP, NP-hårdhed, NP-fuldstændighed.

Håndtering af vanskelige søgeproblemer:

- Begrænsning af udtømmende søgning - f.eks. Branch and bound, Davis-Putman procedure og ()-game tree search.

- Local search - f.eks. taboo search, simulated annealing og genetiske algoritmer.

Approksimationsmetoder - f.eks. randomiseret afrunding og andre randomiserede teknikkker.

Evaluering
Mundtlig eksamen, som bedømmes efter 13-skalen. Ekstern censur.

Bemanding
Sven Skyum og Peter Bro Miltersen

Belastning
2 point / 10 ECTS