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. 

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. En heuristik är bättre ju färre skådespelare den behöver. 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/kth.se/misc/info/kurser/DD2350/adk24/labb5/testfall/

Problemet heter kth.adk.castingheuristic Links to an external site. på Kattis. Kattis summerar antalet roller i alla testfall, subtraherar det totala antalet använda skådespelare i testfallen och returnerar differensen. För godkänt krävs resultatet 1152 eller högre.

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. Ett krav är att programmet måste ge ett bättre resultat än programmet du redovisade i labb 5. 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/kth.se/misc/info/kurser/DD2350/adk24/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/kth.se/misc/info/kurser/DD2350/adk24/labb5/verifyLab5

  där instance.txt innehåller en instans av rollbesättningsproblemet och cast.txt lösningen för samma instans.
• Det rekommenderas inte att använda en lokalsökningsheuristik, eftersom det då blir svårare att utföra den betygshöjande labben. Detta är viktigt eftersom en förbättring av heuristiken måste göras individuellt till den betygshöjande labben. Ifall heuristiken från labb 5 då är "för bra" krävs ytterligare ansträngning på den betygshöjande labben. För att uppnå ett godkänt resultat på labb 5 räcker det med att implementera en enklare heuristik.

Vid labbpassen och redovisningen

Labbpassen genomförs både i sal (se schemat) och på distans med hjälp av Zoom. Varje labbgrupp som vill delta i labbpasset i Zoom skapar ett eget Zoomrum att arbeta i under labbpasset. I kursen används (för både sal och Zoom) kösystemet Stay a while på queue.csc.kth.se för att hålla reda på hjälp- och redovisningskön vid hjälplabbpassen (tvåtimmarspassen, som huvudsakligen är till för hjälp men där redovisningar också tas emot). Skriv i rutan Location in länken till den Zoomsession som ni arbetar i (för Zoomlabb) och i kommentarsrutan vilken labb det gäller.

Länk till bokningslistor för labbredovisning 4 december publiceras här ett dygn före labbpassets start.  Den som vill ha hjälp eller redovisa andra labbar än labb 5 får skriva upp sig i Stay-a-while-kön.

För att bli helt klar med labbkursen behöver var och en skriva en labbkursreflektion.

Högrebetygslabben går inte att redovisa vid detta tillfälle utan ska redovisas antingen 9 december eller 7 januari.