Matematisk statistik CTH/GU
Om Markovkedjor och kombinatorisk optimering
Man skulle kunna tro att optimering av en funktion definierad på en
ändlig mängd är något ganska ointressant. Men i många sammanhang är
denna mängd mycket stor; t.ex. kan den utgöras av alla permutationer
av k element av något slag, och antalet sådana är ju k!
som växer mycket snabbt i $k$. Det blir då nödvändigt att använda effektiva
metoder för att söka upp ett optimum. Ganska välkänt är
"handelsresandens problem"; det gäller att hitta en route för
handelsresanden sådan att han kommer, men endast en gång, till var och
en i en uppsättning städer och tillbaka till sin basort, detta med
minsta resväg.
En graf består av ett antal noder och förbindelselinjer mellan vissa
av dessa. Låt nu noderna representera Europas länder, och låt oss dra
linjer mellan par av noder om länderna dessa står för gränsar till
varandra. Om nu länderna (noderna) skall färgläggas enligt vissa krav,
hur görs det på bästa sätt? Det finns många varianter på detta problem
(i engelskspråkig litteratur kallat "Graph colouring problem"): vi
kan låta det vara förbjudet att använda samma färg för angränsande
länder, eller låta vissa färgkombinationer vara mindre önskvärda (enligt
något kriterium) för länder intill varandra.
Det har visat sig att stokastisk sökning efter optimala eller bra
lösningar på vissa kombinatoriska optimeringsproblem med hjälp av
Markovkedjor är effektiv; det används verkligen i praktiken.
Särskild uppmärksammad är s.k. "Simulated Annealing", och en god bok
om dess teori och tillämpningar är Simulated Annealing and
Boltzmann Machines från 1989 av E. Aarts och J. Korst. Någon
etablerad svensk term finns inte; simulerad aducering föreslås,
med den behåller vi den engelska termens bildspråk från
metallurgin.
Syftet med detta examensarbete är bl.a.\ att
- göra att litteraturstudium rörande simulerad aducering i allmänhet
och dess användning för färgsättning av grafer i synnerhet,
- skriva program för tillämpning på några färgsättningsproblem, och
- utröna hur smidigt
de datorer som används i vardagslag förmår
lösa dessa problem.
Förkunskapskrav är kursen Markovteori. Arbetet är tänkt att utföras av två
personer.
Kontaktperson
Torgny Lindvall, tel: 772 3574, epost: lindvall@math.chalmers.se
Last modified: Thu Feb 18 12:05:36 MET 1999