• kth.se
  • Studentwebben
  • Intranät
  • kth.se
  • Studentwebben
  • Intranät
Logga in
DD2350 HT20 (51571)
Teoriuppgifter till labb 5
Hoppa över till innehåll
Översikt
  • Logga in
  • Översikt
  • Kalender
  • Inkorg
  • Historik
  • Hjälp
Stäng
  • Min översikt
  • DD2350 HT20 (51571)
  • Uppgifter
  • Teoriuppgifter till labb 5
  • Startsida
  • Kursöversikt
  • Uppgifter
  • Course Evaluation

Teoriuppgifter till labb 5

  • Inlämningsdatum 26 nov 2020 av 13.15
  • Poäng 1

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 26 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 vid redovisningen ladda upp en egen skriftlig lösning med namn på som PDF-dokument. Det går bra att lämna in en inskannad handskriven lösning.

Läsanvisningar för teoriuppgifterna:

  • labblydelsen
  • föreläsning 29 (heuristiker) 
  • sida KTorig: 661-670/KTnie: 749-758

 

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? 
1606392900 11/26/2020 01:15pm
Inkludera en beskrivning
Ytterligare kommentarer:
Maxresultat för gradering till > poäng
Inkludera en bedömningstitel

Matris

Hitta matris
Inkludera en titel
Hitta en matris
Titel
Du har redan bedömt studenter med den här matrisen. Större ändringar kan påverka resultaten för deras uppgifter.
 
 
 
 
 
 
 
     
Det går inte att ändra en matris efter att du börjat använda den.  
Titel
Kriterier Bedömningar Poäng
Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
tröskel: 5 poäng
Redigera beskrivning av kriterium Ta bort kriterium rad
5 till >0 poäng Full poäng blank
0 till >0 poäng Inga poäng blank_2
Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
poäng
  / 5 poäng
--
Ytterligare kommentarer
Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
tröskel: 5 poäng
Redigera beskrivning av kriterium Ta bort kriterium rad
5 till >0 poäng Full poäng blank
0 till >0 poäng Inga poäng blank_2
Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
poäng
  / 5 poäng
--
Ytterligare kommentarer
Poängsumma: 5 av 5
Föregående
Nästa
Labb 5 Betygshöjande extralabb