Note de curs, probleme algoritmică, 13 ianuarie 2014

From Algopedia
Jump to navigationJump to search

În acest curs am discutat problemele:

Funny Game

Cerință

Doi teroriști joacă un joc: teroriștii zboară dintr-un aeroport în altul. Înainte să se îmbarce într-un avion, unul din ei montează o încărcătură explozivă în aeroport iar odată plecați, detonează aeroportul, astfel încât nu se mai pot întoarce. Cei doi teroriști aleg cu schimbul avionul cu care vor zbura. Teroristul care nu mai poate detona aeroportul în care îl duce partenerul său pierde jocul.

Cunoscându-se numărul inițial de aeroporturi, toate zborurile care conectează aeroporturile, aeroportul din care cei doi teroriști încep jocul și faptul că aeroporturile și zborurile formează o structură de arbore, să se determine care din cei doi teroriști câștigă într-un joc perfect (teroristul care începe jocul sau partenerul său).

În plus, dacă teroristul care începe jocul are o strategie sigură de câștig, trebuie să numim și aeroportul cu identificatorul minim pe care îl poate alege pentru a câștiga (primul pas al strategiei câștigătoare).

Rezolvare

Aceasta este o problemă clasică de teoria jocurilor. Pentru a o putea rezolva va trebui să identificăm:

  • toate stările jocului: lista situațiilor distincte în care jucătorul aflat la mutare trebuie să ia o decizie;
  • lista alegerilor pe care le are jucătorul aflat la mutare, pentru fiecare stare a jocului;
  • starea inițială a jocului (din care se începe jocul).

Se observă că, datorită structurii de arbore a rețelei de zboruri, teroriștii ajung într-un aeroport numai prin distrugerea tuturor aeroporturilor care formează drumul de la aeroportul inițial la cel curent. De aceea, stările jocului se caracterizează (disting) doar prin identificatorul aeroportului în care se află cei doi teroriști la un moment dat.

Lista alegerilor pe care le are jucătorul aflat la mutare într-o anumită stare coincide cu lista zborurilor care pleacă din aeroportul respectiv, cu excepția zborului cu care teroriștii au aterizat.

Starea inițială a jocului este dată de aeroportul din care cei doi teroriști pornesc la drum.

În acest moment putem calcula, pentru fiecare stare a jocului, dacă jucătorul aflat în starea respectivă are sau nu o strategie de câștig într-un joc perfect din partea adeversarului său (vom cataloga stările drept câștigătoare sau pierzătoare).

Știm din enunțul problemei că teroristul care nu poate detona aeroportul în care se află pierde jocul. Așadar, vom spune că toate stările care nu admit alegeri sunt pierzătoare.

În continuare, putem cataloga o stare pentru care deja am catalogat toate stările ei succesive după următoarele reguli:

  • dacă starea curentă are cel puțin o stare succesivă pierzătoare atunci ea este câștigătoare (dacă jucătorul curent îl poate forța pe adversarul său într-o stare pierzătoare, atunci el se află într-o stare câștigătoare);
  • dacă starea curentă are numai stări succesive câștigătoare atunci ea este pierzătoare (dacă jucătorul curent are de ales numai între stări câștigătoare pentru adversarul său, atunci el se află într-o stare pierzătoare).

Bicolored Horses

Cerință

N cai albi și negri sunt aliniați. Aceștia trebuie grupați, în ordine, și puși în K grajduri. Se știe că dacă în același grajd sunt plasați i cai albi și j cai negri atunci disconfortul creat va fi i * j.

Cunoscând, în ordine, culoarea fiecărui cal, să se identifice o modalitate optimă de grupare a acestora astfel încât disconfortul cumulat să fie minim și să se afișeze acest disconfort.

Rezolvare

Această problemă se rezolvă prin programare dinamică. Va trebui să identificăm o modalitate de descompunere a problemei date în subprobleme mai simple, ale căror soluții, puse cap la cap dau soluția problemei inițiale. Subprobleme se pot descompune la rândul lor în sub-subprobleme tot mai simple, până când rezolvarea lor devine trivială și descompunerea lor nu mai este necesară.

În cazul de față vom calcula următoarele funcții:

D(i, j) = disconfortul creat prin gruparea cailor i, i + 1, ..., j în același grajd (i <= j)
DG(C, G) = disconfortul global optim creat prin gruparea primilor C cai în G grajduri (C >= G)

Calcularea funcției D este trivială, pornind de la culorile cailor și aplicând formula disconfortului din enunț.

Funcția DG se calculează după formula:

DG(C, G) = D(1, C)                                             , dacă G == 1
         = min(i = G - 1 ... C - 1, DG(i, G - 1) + D(i + 1, C)), dacă G >= 2

Explicație:

  • Dacă grupăm caii într-un singur grajd, disconfortul global conincide cu disconfortul local.
  • Dacă grupăm caii în mai mult de un grajd (în G grajduri) atunci va exista un număr de cai (i cai) pe care îi vom grupa optim în primele G - 1 grajduri iar pe următorii cai (cu indici între i + 1 și C) îi vom pune separat în cel de-al G-lea grajd, pentru care se va atinge o grupare optimă în G grajduri. Deoarece nu putem cunoaște de la bun început numărul i de cai, vom efectua calculele pentru orice grupare posibilă și vom alege gruparea optimă (cu disconfortul global minim).

Bineînțeles, soluția problemei este dată de valoarea DG(N, K).

Mnemonics and Palindromes

Cerință

Dându-se un șir S de N caractere, acesta trebuie împărțit într-un număr nimim de subsecvențe cu proprietatea de palidrom, care prin concatenare să dea șirul inițial.

Rezolvare

O primă problemă care trebuie rezolvată este să determinăm pentru orice subsecvență a șirului dat dacă are sau nu proprietatea de palidrom. Acest lucru se poate realiza prin calcularea funcției:

estePalindrom(i, j) = subsecvența delimitată de indicii i și j are proprietatea de palindrom (1 <= i <= j <= N)
                    = true                                       , dacă j - i + 1 == 1
                    = S(i) == S(j)                               , dacă j - i + 1 == 2
                    = S(i) == S(j) && estePalindrom(i + 1, j - 1), dacă j - i + 1 > 2

Pentru a rezolvarea problema, va trebui să calculăm funcția:

palindroame(L) = numărul minim de subsecvențe palindromice în care poate fi
                 împărțit prefixul de lungime L al șirul inițial (0 <= L <= N)
               = 0                                                                    , dacă L == 0
               = min(i = 0 .. L - 1, dacă estePalindrom(i + 1, L), palindroame(i) + 1), dacă L >= 1

Explicație:

  • Prefixul de lungime 0 al șirului inițial poate fi împărțit în 0 subsecvențe. Acesta este un caz degenerat al problemei inițiale, însă pe baza lui putem calcula cazurile mai compleze ușor (prefixele de lungime strict pozitivă).
  • Pentru partiționarea optimă a prefixului de lungime arbitrară L există un subprefix al său de i de caractere care se poate partiționa optim și poate fi concatenat cu un subșir cu proprietatea de palindrom pentru a forma prefixul inițial. Deoarece nu putem cunoaște de la bun început lingimea i a subprefixului, vom efectua calculele pentru orice lungime posibilă și vom alege lungimea optimă (care formează o descompunere cu număr minim de subsecvențe).

Bineînțeles, soluția problemei este dată de valoarea palindroame(N).