Labb 4

NP-fullständighetsreduktioner - Rollbesättning

Om du redovisar labben senast den 18 november får du en bonuspoäng på tentan. Labbteoriuppgifterna nedan kan redovisas för en bonuspoäng till tentan, och detta görs på övningen den 10 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.

Ansvarig för castingen på ett filmbolag behöver koppla ihop rätt skådespelare med rätt roller. Samma person kan spela flera roller, men samma roll kan endast innehas av en person. Manus anger vilka roller som är med i samma scener. Inga monologer får förekomma. Varje skådespelare får bara ha en roll i varje scen.

Dessutom är divorna p1 och p2 garanterade att få (minst) en roll var. Detta medför extraarbete eftersom de båda inte tål varandra och rollerna ska besättas så att de aldrig spelar mot varandra. Rollbesättningsproblemet är att avgöra ifall alla roller kan besättas med de skådespelare som finns till hands. Ingående parametrar är alltså: 
Roller r1, r2,... , rn 
Skådespelare p1, p2,... ,pk 
Villkor typ 1 (till varje roll): rt kan besättas av p1, p2, p6 
Villkor typ 2 (till varje scen): i su medverkar r1, r3, r5, r6 och r7

Indataformat

Alla tal i indataformatet är positiva heltal n, 1<=n.

I exemplen nedan hittar du ett '#'-tecken följt av en förklaring. Tecknet och det som följer efter det fram till radslut är inte en del av indataformatet. Mellanslaget innan '#'-tecknet är valfritt och påverkar inte korrekthetsbedömningen.

I indataformatet används en kompaktform för att uttrycka en mängd tal som kan vara fristående eller intervall. Mellan tal, intervall och mellan tal och intervall är det mellanslag. Intervall markeras med två tal som skills åt med bindestreck. Här är några exempel på kompaktformen:
1 2 3 4 5 6 7 8 9 10 # Alla heltal från och med 1 till och med 10.
1-10 # Alla heltal från och med 1 till och med 10.
1-5 6 7 8-10 # Alla heltal från och med 1 till och med 10, men raden ovanför uttrycker det kortare och bättre.
1-7 9 10 # Alla heltal från och med 1 till och med 10 utom 8
1-7 9-10 # Alla heltal från och med 1 till och med 10 utom 8
1-42 73 # Alla helta från och med 1 till och med 42 och dessutom 73.

Ovanstående kompaktform kommer att kallas "kompaktformen" när vi går igenom indataspecen. 

Rad ett består av tre positive heltal separerade med mellanslag: n_rollkravsrader, n_skådespelare och n_roller. n_rollkravsrader beskriver hur många av följande rader som beskriver vilka krav som ställs på rollerna. Återstående två tal anger antal skådespelare och antal roller. Ett exempel på hur rad ett kan se ut:
4 10 7 # Följande 4 rader beskriver vilka 10 skådespelare som kan spela de 7 rollerna.
3 4 42 # Följande 3 rader beskriver vilka 4 skådespelare som kan spela de 42 rollerna.

Raderna två till n_rollkravsrader+1 består av en lista med roller på kompaktform följt av ett ':'-tecken och en lista med skådespelare på kompaktform. Observera att roller och skådespelare är ett-indexerade i exemplen som följer:
1-10 : 1-3 4-7 # Rollerna från och med 1 till och med 10 kan spelas av skådespelarna 1,2,3,4,5,6 och 7.
11 14 16 : 1-8 # Rollerna 11,14 och 16 kan spelas av skådespelarna 1,2,3,4,5,6,7 och 8.

Rad n_rollkravsrader+2 består av de två talen n_scenkravsrader och n_scener. Det första talet beskriver hur många rader indata som återstår efter denna rad och det andra talet beskriver antalet scener.
1 10 # Nästa rad beskriver hur de 10 scenerna ser ut
3 3 # Nu följer 3 rader som beskriver 3 olika scener

Slutligen kommer raderna från och med n_rollkravsrader+3 till och med n_rollkravsrader+n_scenkravsrader+2. De beskriver vilka roller som spelar i vilken scen. Scener och roller är ett-indexerade i exemplen som följer:
1-10 : 1-3 4-7 # I scenerna från och med 1 till och med 10 förekommer rollerna 1,2,3,4,5,6 och 7.
11 14 16 : 1-8 # I scenerna 11,14 och 16 förekommer rollerna 1,2,3,4,5,6,7 och 8.

Sätt ihop alla delar så är indataformatet för castingproblemet klart.

1 10 10
1-10 : 1-10
5 5
1: 1 4 9
2: 2 3 5 7
3: 1 2 3 4 5 6
4: 7 8 9 10
5: 1-10

3 7 8
1-4 : 1-4
5 : 5
6-8 : 6-7
3 4
1 : 1-3 5-6
2-3 : 2 4 6 8
4 : 1 3 5 7

Förklaring av nej-instansen

1 10 10 # 10 roller och 10 skådespelare
1-10 : 1-10 # Alla är utbytbara
5 5 # En rad per scen.
1: 1 4 9 # Konflikter uppstår.
2: 2 3 5 7 # Konflikter uppstår.
3: 1 2 3 4 5 6 # Konflikter uppstår.
4: 7 8 9 10 # Ännu fler konflikter uppstår.
5: 1-10 # I slutstriden tvingas divorna spela i samma scen och därför är castingen omöjlig.

Förklaring av ja-instansen
3 7 8 # 3 rader beskriver hur 7 skådespelare kan spela 8 roller
1-4 : 1-4 # Divorna och två icke-divor kan spela de första fyra rollerna
5 : 5 # Roll 5 kan bara spelas av skådespelare 5
6-8 : 6-7 # Roll 6-8 kan bara spelas av skådespelare 6 och 7
3 4 # 3 rader beskriver 4 scener
1 : 1-3 5-6 # Rollerna kan spelas av skådespelare 1,3,4,5 och 6.
2-3 : 2 4 6 8 # Rollerna kan spelas av skådespelare 3,2,6 och 7.
4 : 1 3 5 7 # Rollerna kan spelas av skådespelare 1,4,5 och 7.

Uppgift
I den här laborationen ska du visa att rollbesättningsproblemet är NP-svårt genom att reducera ett känt NP-fullständigt problem, som finns inlagt i Kattis. Din reducerade instans kommer att granskas och lösas av Kattis. Du får välja mellan att reducera problemen Graffärgning (problem-id: oldkattis:adkreduction1) och Hamiltonsk cykel oldkattis:adkreduction2). Indataformat för dessa problem beskrivs nedan. Din uppgift är alltså att implementera en reduktion, inte att lösa problemet.

Kattis testar om din reduktion är korrekt, men du måste naturligtvis kunna bevisa att den är det vid redovisningen. Kattis svar är egentligen avsedda att vägleda dig i arbetet med beviset och påpeka om du glömt något viktigt specialfall. Vid redovisningen kommer handledaren också att fråga varför problemet ligger i NP och vad komplexiteten är för din reduktion.

Vid rättningen utnyttjas en lösare för instanser av ett (annat) NP-fullständigt problem inom rimliga storleksgränser. Av tekniska skäl har Kattis en maximal tillåten storlek på instanserna. Du får bara meddelanden om den ifall du skickar in en för stor instans. Du får redovisa din reduktion om du kan bevisa att den är korrekt, oavsett om Kattis har godkänt den eller inte.

Graffärgning
Indata: En oriktad graf och ett antal färger m. Isolerade hörn och dubbelkanter kan förekomma, inte öglor.

Fråga: Kan hörnen i grafen färgas med högst m färger så att inga grannar har samma färg?

Indataformat: 
Rad ett: tal V (antal hörn, V≥1) 
Rad två: tal E (antal kanter, E≥0) 
Rad tre: mål m (maxantal färger, m≥1) 
En rad för varje kant (E stycken) med kantens ändpunkter (hörnen numreras från 1 till V)

Hamiltonsk cykel
Indata: En riktad graf.

Fråga: Finns det en tur längs kanter i grafen som börjar och slutar på samma ställe och som passerar varje hörn exakt en gång?

Indataformat: 
Rad ett: tal V (antal hörn, V≥1) 
Rad två: tal E (antal kanter E≥0) 
En rad för varje kant (E stycken) med kantens starthörn och sluthörn (hörnen numreras från 1 till V)

Teoriuppgifter

1. Skriv på valfritt sätt ned en lösning till ja-instansen av rollbesättningsproblemet som finns som indataexempel.
2. Visa att rollbesättningsproblemet ligger i NP.
3. Förändra nej-instansen i exemplet på indata till en ja-instans. Hur många skådespelare behöver du lägga till i just detta fall?
4. Vilken är den minsta möjliga produktion som uppfyller indatakraven för rollbesättningsproblemet och som går att sätta upp? Skriv upp indata för denna produktion!
5. Tänk dig en instans där rollerna är indelade i två grupper, ungefär som i matchningsproblemet, där rollerna aldrig förekommer i samma scener som roller ur samma grupp. Hur många skådespelare behövs då?
6. Anta att film a innehåller en scen med rollerna 4, 7 och 12 medan film b har tre scener med rollerna 4 och 7, 7 och 12 samt 4 och 12. Om alla övriga villkor är identiska mellan filmerna - kommer svaren då att bli likadana? Varför/varför inte?

Extrauppgift

Frivillig extrauppgift som redovisas på ett särskilt redovisningstillfälle den 8 januari 2015 kl 13-16 och då kan ge betyg A eller B på lärandemålet om hantering av problem med hög komplexitet (och då behöver man inte examineras på det lärandemålet på muntan). Uppgiften görs individuellt. För att få redovisa extrauppgiften måste du vara godkänd på teoritentan.

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 tidigare. 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å /info/adk16/labb4/testfall/

Skriv en kort rapport (omkring en sida) där du dels beskriver vilka heuristiker din lösning använder och dels reflekterar över hur du arbetat med uppgiften och hur du möjligen kunnat arbeta annorlunda. Skriv namn på rapporten och lämna den till labbassistenten vid redovisningen.

Problemet heter oldkattis:adkcasting i Kattis. Kattis summerar antalet använda skådespelare i testfallen och returnerar summan. För betyg B krävs ett resultat bättre än 560. För betyg A krävs 460 eller bättre. För betyg A krävs också att algoritmen använder simulated annealling, tabusökning eller annan sofitistikerad lokalsökningsheuristik. Bara den som är godkänd på teoritentan får redovisa extralabben.

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