Labb 4: NP-fullständighetsreduktioner - Rollbesättning

För ADK gäller: Om du redovisar labben senast den 7 maj får du en bonuspoäng på tentan. På övningen den 22 april har du dessutom möjlighet att redogöra för lösningen på teoriuppgifterna nedan. Korrekt lösning av dessa ger en bonuspoäng på tentan. Sen redovisning ger ingen bonus för labb eller teoriuppgifter.
Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom.

För SUALKO gäller: Labben är frivillig men kan ge bonuspoäng. Rätt löst labb ger en poäng och teoriuppgifterna en poäng som vanligt.

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 p₁ och p₂ garanterade vid varje castingtillfälle. 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 r₁, r₂,... , r_n
Skådespelare p₁, p₂,... ,p_k
Villkor typ 1 (till varje roll): r_t kan besättas av p₁, p₂, p₆
Villkor typ 2 (till varje scen): i s_u medverkar r₁, r₃, r₅, r₆ och r₇

Indataformat

Fråga: Kan rollerna besättas med högst k st skådespelare så att p₁ och p₂ deltar men inte är med i samma scener som varandra?

Exempel på godkända indata

5 5 3
3 1 2 3
2 2 3
2 1 3
1 2
3 1 2 3
2 1 2
2 1 2
3 1 3 4
2 3 5
3 2 3 5

6 5 4
3 1 3 4
2 2 3
2 1 3
1 2
4 1 2 3 4
2 1 4
3 1 2 6
3 2 3 5
3 2 4 6
3 2 3 6
2 1 6 

Uppgift

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?

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 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/adk10/labb4/testfall/

Problemet heter 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 580. För betyg A krävs 475 eller bättre. Betygen ges under förutsättning att eleverna blir godkända på efterföljande teoritenta.