h3. Soluţie:

Aceasta este o problemă celebră, sau aşa se pare după numărul de concursuri în care a fost folosită, şi este o generalizare a unei probleme din 'articolul precedent':probleme-de-acoperire-1.

Aceasta este o problemă celebră, sau aşa se pare după numărul de concursuri în care a fost folosită, şi este o generalizare a unei probleme din articolul precedent.

Prima idee ar fi să încercăm o abordare $greedy$ şi să punem piese pe tablă într-o ordine oarecare cât timp mai este loc. Dar putem găsi uşor contraexemple pentru acest tip de abordare. Limitele sunt mult prea mari pentru ca o rezolvare bazată pe $programare dinamică$ combinată cu $backtracking$ să meargă. O idee ce am utilizat-o în articolul anterior ne va fi folositoare şi aici. Colorăm tabla noastră în mod asemănător unei table de şah şi numerotăm pătrăţelele tablei.

Prima idee ar fi să încercăm o abordare $greedy$ în care încercăm într-o ordine oarecare să punem piese pe tablă cât timp mai este loc, dar putem găsi uşor contraexemple pentru acest tip de abordare. Limitele sunt mult prea mari pentru ca o rezolvare bazată pe $programare dinamică$ combinată cu $backtracking$ să meargă. O idee ce am utilizat-o în numărul anterior ne va fi folositoare aici. Colorăm tabla noastră în mod asemănător unei table de şah şi numerotăm pătrăţelele tablei.

p=. !probleme-de-acoperire-2?P282.jpg!

Acum vedem că un domino amplasat pe tablă trebuie să ocupe o celulă colorată alb şi una negru, celule care sunt adiacente. Dacă realizăm un graf în care nodurile sunt celulele, iar între două noduri există muchie dacă ele sunt adiacente vertical sau orizontal pe tablă, facem observaţia că graful este bipartit. O acoperire cu dominouri corespunde în acest graf unei mulţimi de muchii pentru care nu există două muchii cu acelaşi capăt (o muchie corespunde amplasării posibile a unui domino, iar restricţia menţionată face ca să nu existe dominouri care se suprapun). Deci pentru a găsi o soluţie maximală pentru problema iniţială, trebuie să găsim o mulţime de muchii neadiacente de cardinal maxim. În acest mod am transformat cerinţa într-o problemă clasică de teoria grafurilor cunoscută sub numele de $cuplaj maxim într-un graf bipartit$. Vedem în imaginea următoare cum a fost transformată tabla într-un graf şi cum soluţia prezentată în exemplu corespunde unui $cuplaj maxim$ în graful asociat tablei.

Acum vedem că un domino poate fi amplasat pe tablă şi el trebuie să ocupe o celulă colorată alb şi una negru, celule care sunt adiacente. Dacă realizăm un graf în care nodurile sunt celulele iar între două noduri există muchie dacă ele sunt adiacente vertical sau orizontal pe tablă, facem observaţia că graful este bipartit. O acoperire cu dominouri corespunde în acest graf unei mulţimi de muchii pentru care nu există două muchii cu acelaşi capăt (o muchie corespunde amplasării posibile a unui domino, iar restricţia menţionată face ca să nu existe dominouri care se suprapun). Deci pentru a găsi o soluţie maximală pentru problema iniţială, trebuie să găsim o mulţime de muchii de cardinal maxim. În acest mod am transformat cerinţa într-o problemă clasică de teoria grafurilor cunoscută sub numele de '$cuplaj maxim într-un graf bipartit$':usaco-ian-2005-divizia-gold#cover. Vedem în imaginea următoare cum a fost transformată tabla într-un graf şi cum soluţia prezentată în exemplu corespunde unui $cuplaj maxim$ în graful asociat tablei.

p=. !probleme-de-acoperire-2?P283.jpg!