DD2350HT191
    Labb 5
    Hoppa över till innehåll
    Översikt
    • Logga in
    • Översikt
    • Kalender
    • Inkorg
    • Hjälp
    Stäng
    • Min översikt
    • DD2350HT191
    • Uppgifter
    • Labb 5
    • Startsida

    Labb 5

    • Inlämningsdatum 6 dec 2019 av 17:00
    • Poäng 1

    Heuristik för rollbesättningsproblemet

    Om du redovisar labben senast den 6 december får du en labbleveranspoäng, som kan ge högre betyg på labbmomentet. Till labben hör teoriuppgifter som kan redovisas för en teoripoäng till tentan, och detta görs på övningen den 28 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.

    Målen för labb 5 är att du ska

    • öva på att attackera ett problem som inte kan lösas optimalt,
    • implementera en heuristik för ett NP-svårt problem,

    Du ska välja att implementera valfri heuristik som löser konstruktionsproblemet: Vilka skådespelare ska ha vilka roller för att lösa rollbesättningsinstansen med så få skådespelare som möjligt? Indataformatet för rollbesättningsproblemet är detsamma som i labb 4. Divorna är 1 och 2.

    Utdataformat: 
    Rad ett: antal skådespelare som fått roller 
    En rad för varje skådespelare (som fått roller) med skådespelarens nummer, antalet roller skådespelaren tilldelats samt numren på dessa roller

    Problemet ska lösas enligt villkoren som specificerats för rollbesättningsproblemet, dvs divorna måste vara med men får inte mötas, ingen roll får spelas av flera personer, och ingen skådespelare får spela mot sig själv i någon scen. Bättre heuristik (dvs färre skådespelare) ger bättre betyg. Endast lösbara instanser kommer att ges som indata, men för att heuristiken i polynomisk tid säkert ska kunna hitta en lösning så är det tillåtet att använda högst n-1 särskilda superskådisar med nummer k+1, k+2, ... Varje superskådis kan spela vilken roll som helst, men kan bara spela en enda roll.

    Några testfall att testa ditt program med finns på /afs/nada.kth.se/info/adk19/labb5/testfall/

    Problemet heter kth.adk.castingheuristic på Kattis. Kattis summerar antalet använda skådespelare i testfallen och returnerar summan. För godkänt krävs ett resultat bättre än 600.

    I Kattis testfall är antalet roller aldrig större än 600, antalet scener aldrig större än 4000 och antalet skådespelare aldrig större än 400.

    Notera att det finns en betygshöjande extralabb där kraven är strängare. För att få redovisa extralabben krävs betyg C på labbkursen, dvs att alla labbar är godkända och att minst 4 labbleveranspoäng uppnåtts. Extralabben ska göras individuellt.

    Tips

    Det kan underlätta om man skriver en egen verifikator för den producerade lösningen, så att man upptäcker om en otillåten lösning produceras av heuristiken.

     

    1575648000 12/06/2019 05:00pm
    Ytterligare kommentarer:
    Maxresultat för gradering till > poäng

    Matris

     
     
     
     
     
     
     
         
    Det går inte att ändra en matris efter att du börjat använda den.  
    Hitta en matris
    Hitta matris
    Titel
    Du har redan bedömt studenter med den här matrisen. Större ändringar kan påverka resultaten för deras uppgifter.
    Titel
    Kriterier Bedömningar Poäng
    Redigera beskrivning av kriterium Ta bort kriterium rad
    Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
    tröskel: 5 poäng
    Redigera ranking Radera ranking
    5 till >0 poäng
    Full poäng
    blank
    Redigera ranking Radera ranking
    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