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 1 december (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 vid redovisningen ha med en lösning. Om det är flera som samarbetat om lösningen ska du se till att det framgår klart (se hederskodex). Överarbeta inte lösningen - den behöver inte se snygg ut. Det går bra att lämna in en (inskannad) handskriven lösning. Om du redovisar i övningssal ska du ta med en utskrift av lösningen; om du redovisar i Zoom ska du ladda upp en PDF med lösningen.

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 (simulerad härdning) 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?