Till KTH:s startsida Till KTH:s startsida

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. Varje roll måste förekomma i minst en scen.

Dessutom är divorna p1 och p2 garanterade att få (minst) en roll var (och de rollerna ska självklart delta i åtminstone en scen 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 r1r2,... , rn 
Skådespelare p1p2,... ,pk 
Villkor typ 1 (till varje roll): rt kan besättas av p1p2p6 
Villkor typ 2 (till varje scen): i su medverkar r1r3r5r6 och r7

Indataformat
De tre första raderna består av talen ns och k (antal roller, antal scener och antal skådespelare, n≥1, s≥1, k≥2), ett tal per rad. 

De följande n raderna representerar villkoren av typ 1 och börjar med ett tal som anger antalet efterföljande tal på raden, följt av de möjliga skådespelarnas nummer (mellan 1 och k, kursiverade i exemplen nedan). 
De sista s raderna är villkor av typ 2 och börjar ett tal som anger antalet efterföljande tal på raden, följt av tal som representerar de olika rollerna som är med i respektive scen. Varje roll förekommer högst en gång på varje sådan rad, så antalet roller på en rad ligger mellan 2 och n.

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

Exempel på godkända indata

nej-instans:
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
       ja-instans:
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
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 kth.adk.npreduction1) och Hamiltonsk cykel (problem-id kth.adk.npreduction2). 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, \(1 \leq V \leq 300\)
Rad två: tal E (antal kanter, \(0\le E\le 25000\)
Rad tre: mål m (max antal färger, \(1\le m\le 2^{30}\)
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, \(1\le V\le 200\)
Rad två: tal E (antal kanter \(0\le E\le 5000\)
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 10 januari 2017 kl 14-17 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å momentet TEN1 (dvs 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+1k+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 kth.adk.castingheuristic på 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 annealing, tabusökning eller annan sofistikerad 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 4000 och antalet skådespelare aldrig större än 400.

Viggo Kann skapade sidan 19 augusti 2016

Lärare Viggo Kann ändrade rättigheterna 19 augusti 2016

Kan därmed läsas av lärare och ändras av lärare.

Lärare Viggo Kann ändrade rättigheterna 31 oktober 2016

Kan därmed läsas av alla och ändras av lärare.
kommenterade 4 november 2016

När kommer problem-id för Graffärgning och Hamiltonsk cykel?

kommenterade 7 november 2016

^

Dessutom, vad betyder "Inga monologer får förekomma."?

En användare har tagit bort sin kommentar
kommenterade 7 november 2016

Teorifråga 5:

Antalet skådespelare som behövs borde rimligtvis vara relaterat till vilken probleminstans det är frågan om. Tänker jag fel eller är frågan felställd?

kommenterade 7 november 2016

"Inga monologer får förekomma" betyder gissningsvis att en uppsättning inte får innehålla någon scen med endast en skådespelare.

kommenterade 7 november 2016

@Mikael Min tanke också, men har den ingen riktig funktion så borde den istället förekomma som indatakrav (annars tillförd den bara meningslös "komplexitet"). Därav tänkte jag att det kanske var något annat.

Tack för svar ;)

Lärare kommenterade 7 november 2016

Som Mikael beskrev betyder "Inga monologer" att varje scen måste ha minst två roller.

Teorifråga 5 är korrekt ställd.

Jag vet inte när Kattisproblemen kommer upp men förhoppningsvis inom ett dygn. Problemen är klara och behöver bara läggas upp av en Kattisadministratör.

kommenterade 8 november 2016

Tiden rinner iväg och det går inte att testa mot kattis. Känner mig stressad.

Lärare kommenterade 8 november 2016

Robin, inom några dagar ska Kattisuppgifterna vara uppe. Det är fortfarande 10 dagar kvar till bonusdatumet för labben, så ta det lugnt!

kommenterade 8 november 2016

I graffärgningsproblemet påverkar inte eventuella dubbelkanter färgningen på något sätt, eller?

Tack på förhand :)

En användare har tagit bort sin kommentar
kommenterade 10 november 2016

Någon som behöver labbpartner på denna? Skicka mig ett pm så kan vi labba :)

kommenterade 12 november 2016

Att (kontinuerligt) hålla på och smyga in ändringar i labblydelsen så här nära inpå deadline är inte OK. Det är riktigt otrevligt och bestraffar oss som är ute i god tid.

Dessutom gäller enligt kursens labbassistenter inte alls "Du får redovisa din reduktion om du kan bevisa att den är korrekt, oavsett om Kattis har godkänt den eller inte". Jag var inte ensam om att slösa många timmar av måndagen pga detta. Oseriöst.

En användare har tagit bort sin kommentar
Lärare kommenterade 13 november 2016

Hej Johan! Labbuppgiften har inte ändrats. I tisdags gjordes ett förtydligande av  labblydelsen, nämligen att varje roll i uppsättningen måste förekomma i minst en scen, vilket jag hoppas ingen tycker är konstigt. Igår förmiddags la jag in länkar till dom utlovade Kattisproblemen i labblydelsen. Jag är ledsen att Kattisproblemen las upp bara en vecka före bonusdatumet för labben. Vi ville vara säkra på att den nyskrivna specialdomaren och dom nya testfallen skulle fungera, och det tog några dagar längre än planerat.

Meningen om att man kan få redovisa utan att Kattis godkänt lösningen syftar på fallet då lösningen inte har accepterats av Kattis på grund av att reduktionen gett en så komplicerad probleminstans att Kattis inte hunnit kontrollera den inom rimlig tid. Kattis är ju tvungen att lösa ett NP-fullständigt problem för att kontrollera svaret!

kommenterade 13 november 2016

Hej Viggo! Tack för snabbt svar (målet var dock att belysa missförhållanden snarare än diskussion).

Labbuppgiften har ändrats. Huruvida det senaste kravet är konstigt eller inte påverkar inte det faktum att vi behöver skriva om hela vår tidigare lösning (som var skräddarsydd efter tidigare kravspec, något som ofta behövs i adk:n för att klara tidskravet). Detta kombinerat med den korta tidsfristen och att vi inte alls fick redovisa vår reduktion i fredags har mördat min planering och jag tycker lite självkritik vore på sin plats.

kommenterade 13 november 2016

Så man får alltså redovisa trots att Kattis godkänner vissa testfall för att sedan få time limit exceeded (i vårt fall korrekta lösningar fram till testfall 33/36 då vi får resultatet "time limit exceeded") så länge man kan bevisa att reduktionen är korrekt?

Lärare kommenterade 14 november 2016

David, du beskriver just det fallet då reduktionen skapar en instans som Kattis inte klarar av att lösa inom den uppsatta tidsgränsen. Då är det tillåtet att redovisa och vid redovisningen bevisa att reduktionen är korrekt (inklusive att den är polynomisk!). Men att Kattis får time limit exceeded tyder på att reduktionen är onödigt komplicerad, så det kan ändå vara en bra idé att försöka förenkla den.

Marcus Dicander redigerade 30 november 2016

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. Varje roll måste förekomma i minst en scen.

Dessutom är divorna p1 och p2 garanterade att få (minst) en roll var (och de rollerna ska självklart delta i åtminstone en scen 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

IndataformatDe tre första raderna består av talen n, s och k (antal roller, antal scener och antal skådespelare, n≥1, s≥1, k≥2), ett tal per rad. 

De följande n raderna representerar villkoren av typ 1 och börjar med ett tal som anger antalet efterföljande tal på raden, följt av de möjliga skådespelarnas nummer (mellan 1 och k, kursiverade i exemplen nedan). De sista s raderna är villkor av typ 2 och börjar ett tal som anger antalet efterföljande tal på raden, följt av tal som representerar de olika rollerna som är med i respektive scen. Varje roll förekommer högst en gång på varje sådan rad, så antalet roller på en rad ligger mellan 2 och n.

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

Exempel på godkända indata

nej-instans: 55 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        ja-instans: 654 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 UppgiftI 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 kth.adk.npreduction1) och Hamiltonsk cykel (problem-id kth.adk.npreduction2). 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ärgningIndata: 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, tex:\displaystyle 1 \leq V \leq 300) Rad två: tal E (antal kanter, tex:\displaystyle 0\le E\le 25000) Rad tre: mål m (max antal färger, tex:\displaystyle 1\le m\le 2^{30}) En rad för varje kant (E stycken) med kantens ändpunkter (hörnen numreras från 1 till V)

Hamiltonsk cykelIndata: 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, tex:\displaystyle 1\le V\le 200) Rad två: tal E (antal kanter tex:\displaystyle 0\le E\le 5000) En rad för varje kant (E stycken) med kantens starthörn och sluthörn (hörnen numreras från 1 till V)

Teoriuppgifter
* Skriv på valfritt sätt ned en lösning till ja-instansen av rollbesättningsproblemet som finns som indataexempel.
* Visa att rollbesättningsproblemet ligger i NP.
* 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?
* 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!
* 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å?
* 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 10 januari 2017 kl 14-17 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å momentet TEN1 (dvs 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 (KOMMER SENARE) ikth.adk.castingheuristic på 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 4000 och antalet skådespelare aldrig större än 400.

En användare har tagit bort sin kommentar
kommenterade 9 december 2016

Om man satsar på B finns det något övrig krav (för extrauppgiften), eller räcker det med Kattispoängen och att man kan förklara hur man tänkt? 

Lärare kommenterade 9 december 2016

Rebecca, det är kraven som står ovan som gäller, till exempel att uppgiften ska göras individuellt, att en rapport på en sida ska lämnas in etc.

kommenterade 31 december 2016

Vad skiljer en sofistikerad lokalsökningsheuristik från en icke-sofistikerad sådan? 

Lärare kommenterade 31 december 2016

Kristian, två exempel på sofistikerade lokalsökningsheuristiker är simulated annealing och tabusökning. Det är också tillåtet att använda andra heuristiker som bygger på lokalsökning men som inte bara gör enkel lokalsökning med fast djup. Du får i så fall själv vid redovisningen och i den korta rapporten tala om i vilken mening som den lösning du valt är sofistikerad.

En användare har tagit bort sin kommentar