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

F�r ADK g�ller: Om du redovisar labben senast den 23 april f�r du en bonuspo�ng p� tentan. P� �vningen den 16 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.

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 590. F�r betyg A kr�vs 480 eller b�ttre. Betygen ges under f�ruts�ttning att eleverna blir godk�nda p� efterf�ljande teoritenta.