Labb 5

Heuristik för rollbesättningsproblemet

Om du redovisar labben senast den 4 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 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 lösningen som PDF-dokument. Om det är flera som samarbetat om lösningen ska det framgå klart (se hederkodex). Det går bra att lämna in en inskannad handskriven lösning.

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/adk20/labb5/testfall/

Problemet heter kth.adk.castingheuristic Links to an external site. 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 använder en verifikator för den producerade lösningen, så att man upptäcker om en otillåten lösning produceras av heuristiken. En av kursens assistenter har skrivit en verifikator som finns kompilerad för KTH:s datorsystem på /afs/nada.kth.se/info/adk20/labb5/verifyLab5

Verifikatorn förväntar sig att få först en instans av rollbesättningsproblemet och sedan en föreslagen lösning på instansen (som får innehålla superskådisar). Kör verifikatorn med t.ex.

cat instance.txt cast.txt | /afs/nada.kth.se/info/adk20/labb5/verifyLab5

där instance.txt innehåller en instans av rollbesättningsproblemet och cast.txt lösningen för samma instans.

Redovisning

Länk till bokningslistor för labbredovisning 4 december 2020.