Przeskocz do treści

Delta mi!

Parkietaże

Michał Adamaszek

o artykule ...

  • Publikacja w Delcie: luty 2019
  • Publikacja elektroniczna: 1 lutego 2019
  • Wersja do druku [application/pdf]: (331 KB)
obrazek

W autorskim tygodniku internetowym Trapez Jarosław Wróblewski proponuje serię zadań (nr 75-126) o parkietowaniu prostokątów. Na przykład: czy planszę 15 × 15 da się szczelnie pokryć klockami o wymiarach |8× 1;1 × 8;11 × 1 oraz 1 × 11 (oczywiście klocki nie mogą na siebie zachodzić).

W tego typu zadaniach odpowiedź zazwyczaj brzmi "nie", a typowa strategia polega na zgadnięciu numeracji lub kolorowania pól planszy i użyciu argumentu w stylu "każdy klocek pokrywa trzy pola zielone, ale liczba pól zielonych na całej planszy jest niepodzielna przez 3 ". Spróbujmy jednak ogólniej zastanowić się, jak systematycznie, od podstaw, można zaatakować problem: czy planszę o wymiarach n × m da się wyparkietować klockami ustalonych typów a1× b1,...,aℓ× bℓ.

Niech |(i, j) oznacza pole w |i-tym wierszu i  j-tej kolumnie. Każde pokrycie planszy możemy zakodować za pomocą zmiennych

 ⎧⎪⎪1 jeśli pewien klocek typu a ×b ma lewy gó rny róg na polu (i, j), xai,× jb= ⎨ ⎪⎪⎩0 wpp.
obrazek

Przykład parkietażu

Przykład parkietażu

Na przykład pokrycie planszy 4 ×2 z rysunku obok opisujemy następująco:

x1× 2 = x3×1 = x3×1= 1, 1,1 2,1 2,2

a wszystkie inne zmienne xa ×b i, j są równe zero.

Zapytajmy teraz, kiedy zestaw zmiennych xai×, jb opisuje poprawny parkietaż. Przede wszystkim musimy usunąć wszystkie zmienne

xa×bdla i > n +1 −a lub j > m i, j

ponieważ klocek o wymiarach a × b z lewym górnym rogiem na polu |(i, j) wystawałby poza planszę. Po drugie, wszystkie zmienne muszą przyjmować wartości 0 lub |1. W końcu, musimy zagwarantować, że każde pole planszy jest pokryte przez dokładnie jeden klocek. Ten warunek można zapisać następująco:

ℓ min i,n−ak+1 min j,m Q Q Q xaik ,× j bk= 1 k 1i max 1,i−ak+1 j max 1, j−bk+1 (1)

dla każdego i = 1,...,n, j = 1,...,m. Ten nieprzyjemny wzór oznacza po prostu, że spośród wszystkich legalnych położeń dostępnych klocków, które potencjalnie mogą zahaczać o pole (i, | j), dokładnie jedno jest faktycznie w użyciu. A zatem zerojedynkowe rozwiązania układu |nm równań liniowych (1) odpowiadają jednoznacznie parkietażom.

Dla zupełnej jasności rozważmy przykład. Zapiszmy w tym języku problem parkietowania planszy 3 | × 4 klockami typu 1× 3 i 2 × 1. Mamy |12 równań, z których każde wymienia legalne sposoby pokrycia jednego z pól:

 1× 3 2× 1 (1,1) x1,1 +x 1,1 = 1 (1,2) x1×1, 31 +x1×1,23+ x21×,21= 1 (1,3) x1× 3 +x1×3+ x2×1= 1 1,1×1 3 1,22× 1 1,3 (1,4) x1,1×2 3 +x 1,42× 1= 12×1 (2,1) x2,1 +x 1,1 + x2,1 = 1 (2,2) x1×2, 31 +x1×2,32 + x21×,21+ x22×,21= 1 (2,3) x1× 3 +x1×3+ x2×1+ x2×1= 1 2,1×1 3 2,2×2 1 12,3×1 2,3 (2,4) x2,1×2 3 +x 1,42× 1+ x2,4 = 1 (3,1) x3,1 +x 2,1 = 1 (3,2) x1×3, 31 +x1×3,32 + x22×,21= 1 (3,3) x1× 3 +x1×3+ x2×1= 1 3,1×1 3 3,2×2 1 2,3 (3,4) x3,2 +x 2,4 = 1 (2)

Na przykład równanie dla pola (2,4) czytamy następująco: pole to można przykryć klockiem 1 ×3 z pola (2,2) lub klockiem 2 ×1 z jednego z pól |(1,4) lub (2,4).

Jak łatwo sprawdzić, prostokąta 3× 4 klockami |1× 3 i 2× 1 pokryć się nie da. Możemy tego faktu dowieść algebraicznie, mianowicie mnożąc równania (2) kolejno przez następujące współczynniki:

− 1,1,0,− 1,1,−1,0,1,−1,1,0,−1 (3)

i dodając wszystko stronami. Wtedy otrzymamy

0 =− 1,

co dowodzi, że układ (2) nie ma rozwiązań rzeczywistych (a więc tym bardziej zerojedynkowych!).

Uogólnijmy ostatnie rozumowanie. Układ równań liniowych nie ma rozwiązań w liczbach rzeczywistych jedynie wówczas, gdy pewna kombinacja liniowa danych równań daje "oczywistą sprzeczność" postaci "zero z lewej, coś niezerowego z prawej strony". Nie udowodnimy tego faktu, a jedynie odwołamy się do intuicji i życiowego doświadczenia Czytelników w tym zakresie.

Co to znaczy w szczególnym przypadku układu (1)? Oznaczmy przez |yi j współczynnik, przez jaki w naszym dowodzie nierozwiązywalności przemnożymy równanie dla pola (i, j). Możemy nawet myśleć o tych współczynnikach jako wpisanych w pola planszy: yi j umieszczamy na polu |(i, j). Na przykład współczynniki (3) dla przykładu (2) pojawią się na planszy |3× 4 w następującej kolejności:

|--|---|---|--| − 1| 1 |0 |−1| |--|---|---|--| |-1|−1-|0--|-1| −-1--1--0---−1-

Wtedy (proszę sprawdzić) "oczywista sprzeczność" dla układu (1) polega na tym, że:

  • każde dopuszczalne położenie klocka na planszy pokrywa pola o sumie |y i j równej zeru,
  • suma wszystkich yi j jest niezerowa.

Jest zupełnie Jasne (przez duże J, i to bez lektury całego naszego wywodu), że powyższe warunki dowodzą nieistnienia parkietażu! A zatem odkryliśmy od podstaw jeden z wariantów magicznej metody rozwiązywania tego typu zadań, wspomnianej na początku.

obrazek

Spójrzmy na to, co tutaj się stało, z jeszcze szerszej perspektywy. Układ równań taki jak (1) jest bardzo szczególnym przypadkiem problemu z zakresu programowania całkowitoliczbowego (ang. mixed-integer programming). Wiele trudnych problemów kombinatorycznych można zakodować w tej postaci, wprowadzając zmienne zerojedynkowe opisujące pewne zdarzenia (np. klocek leży na polu) i wyrażając wzajemne ograniczenia (np. klocki nie zachodzą na siebie) w postaci równań i nierówności liniowych, tak jak w (1). Jest to standardowa technika dla wielu tego typu problemów. Rozwiązywanie problemów całkowitoliczbowych, choć możliwe, jest bardzo czasochłonne (w istocie NP-trudne), dlatego możemy na początek zapytać, czy badany problem ma w ogóle rozwiązanie w liczbach rzeczywistych. Ten proces nazywa się relaksacją. Powstały problem liniowy można rozwiązać efektywnie, a jeżeli okaże się, że rozwiązania nie ma, to zawsze można podać certyfikat niespełnialności (ang. infeasibility certificate), analogiczny do naszej tabeli współczynników |yi j. Czytelnikom zainteresowanym tym Olbrzymim (przez duże O) działem optymalizacji proponuję wpisanie wymienionych tu haseł w wyszukiwarce. Reasumując:

dowód nieistnienia parkietażu przez kolorowanie/numerowanie i inne sprytne niezmienniki

to nic innego, jak

certyfikat niespełnialności dla liniowej relaksacji całkowitoliczbowego modelu parkietowania.

Pod tym adresem można znaleźć kod źródłowy wraz z komentarzami, pozwalający własnoręcznie eksperymentować z parkietażami przy użyciu ogólnodostępnych pakietów do modelowania i programowania liniowego/całkowitoliczbowego. Można tam znaleźć rozwiązanie zadania o planszy 15× 15 ze wstępu.