Teoriuppgifter till labb 5

Dessa teoriuppgifter hör till labb 5 och kan redovisas för en teoripoäng till tentan. Redovisningen görs skriftligt och muntligt på övningen den 29 november (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom. Arbeta gärna i grupp med labbteoriuppgifterna, men var och en ska av administrativa skäl ta med en egen skriftlig lösning med namn på som lämnas in vid redovisningen. Skriv gärna för hand!

Teoriuppgifter

1. Vad skiljer en heuristik från en approximationsalgoritm?
2. Rollbesättningsproblemet i labb 5 är ett minimeringsproblem. Vad är målfunktionen för problemet?
3. I labb 5 har så kallade superskådisar införts i rollbesättningsproblemet. Varför behövde superskådisar införas i labb 5?
4. Om lokalsökning ska användas som heuristik för rollbesättningsproblemet behövs en metod för lokal modifiering av en lösning. Föreslå en lokal modifiering för rollbesättningsproblemet!
5. Vid lokalsökning gör man lokala modifieringar som inte försämrar målfunktionens värde upprepade gånger. Bevisa att detta tillvägagångssätt (med din lokala modifiering från uppgift 4) inte alltid leder till att den optimala lösningen hittas.
6. Varför fungerar inte ditt bevis i uppgift 5 om Simulated annealing används istället för upprepad lokal förbättring.
7. När bör man sluta göra upprepade lokala modifieringar vid lokalsökning? Det vill säga, hur länge ska man hålla på?
8. Vad finns det för fördelar med att införa slump i en heuristik?