Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. Alicja i Bogdan na działce | Politechnika Gdańska

Zagadka 1

Alicja i Bogdan mają działkę kwadratową o boku 100 m, którą odziedziczyli po dziadku. Działka jest podzielona na identyczne grządki-poletka o wymiarze 6,25 m × 6,25 m. Chcą ją zazielenić, sadząc trawę na jak najmniejszej liczbie grządek. Wiedzą przy tym, że jeśli grządka przylega do dwóch obsianych (bezpośrednio lub narożnikowo), to po roku na niej również zaczyna rosnąć trawa. Jaka jest najmniejsza początkowa liczba grządek, na których mogą posiać trawę, tak by zaczęła ona rosnąć na całej działce?

Rozwiązanie
Zadanie jest silnie związane z problemem tzw. dominowania w grafach kratowych. Na rysunku 1 podajemy jedno z możliwych rozwiązań. Współczynnik zazielenienia wynosi tutaj 23,4 proc.
Uwaga 1. W tym rozwiązaniu każde poletko nieobsiane trawą sąsiaduje z dwoma obsianymi trawą położonymi w odległości co najwyżej 6,25 m (czyli przylega bezpośrednio do jednego, a z drugim sąsiaduje przez krawędź, styka się wierzchołkiem lub jest w odległości 6,25 m od niego), a zatem nasz problem będzie można sprowadzić do znalezienia najmniejszego zbioru (1,2)-dominującego w kracie kwadratowej 16 × 16, co w tym przypadku sprowadza się do znalezienia zwykłego zbioru dominującego.
Uwaga 2. Jednakże gdyby okazało się, że trawa przenosi się na wszystkie grządki odległe o nie więcej niż 1 m, to grządki można by zmniejszyć do rozmiaru 1 m × 1 m. Wówczas problem sprowadzi się do znalezienia zbioru dominującego w kracie 100 × 100. Ponieważ taki zbiór liczy 2076 węzłów, współczynnik koniecznego zazielenienia zmniejszy się do 20,8 proc.

Zagadka 2

Po posianiu trawy warto postawić strachy na wróble. Jeśli na poletku stoi jeden strach na wróble, to jego zasięg obejmuje tylko to poletko, na którym stoi. Jeśli dwa strachy na wróble, to ich zasięg jest większy, obejmuje także pola sąsiadujące z danym przez krawędź. W jaki sposób ustawić jak najmniejszą liczbę strachów, aby ptaki nie zjadły wysianego ziarna trawy?

Rozwiązanie
Zadanie jest silnie związane z problemem tzw. dominowania rzymskiego w grafach kratowych. Na rysunku 2 podajemy jedno z możliwych rozwiązań optymalnych.
Uwaga 3. Problemowi dominowania rzymskiego poświęcony był esej Grafy w Imperium Rzymskim, „Pismo PG” nr 3/2021, s. 30–31.

Zagadka 3

Bogdan zabrał się za malowanie płotu odgradzającego działkę od gminnej drogi. Płot składa się z pionowych desek jednakowej szerokości, ściśle przylegających do siebie. Deski mają rozmaite wysokości – po prostu taki płot postawił dziadek Alicji i nikt nie pomyślał, aby go wyrównać. Ponadto w płocie są otwory: na skrzynkę pocztową, na wejście dla kota itd. No trudno: równy, nierówny, ale pomalować trzeba. W tym celu Bogdan nabył spory pędzel – taki, że jego szerokość akurat odpowiadała szerokości deski w płocie. Pędzel można prowadzić zarówno poziomo, jak i pionowo. Aby uzyskać dobry efekt, pędzel podczas prowadzenia musi przylegać całą szerokością do powierzchni płotu. Poszczególne partie płotu mogą być pomalowane więcej niż raz. Bogdan chciałby jak najszybciej wykonać to zadanie, wykonując jak najmniejszą liczbę pociągnięć pędzla.

Rozwiązanie
Nasz problem zamodelujemy za pomocą grafu dwudzielnego G(V₁,V₂), w którym wierzchołki di pierwszej partycji V₁ będą odpowiadały poszczególnym deskom w płocie, zaś wierzchołki p_j z drugiej partycji V₂ – poziomym pociągnięciom pędzla. Pomiędzy d_i i p_j będzie krawędź jedynie wtedy, gdy na przecięciu i-tej deski i j-tego poziomu będzie obszar do pomalowania (por. rys. 3a). Obecnie nasz problem sprowadza się do znalezienia najmniejszego pokrycia wierzchołkowego
w grafie dwudzielnym, tj. takiego zbioru wierzchołków, że każda krawędź ma przynajmniej jeden koniec w tym zbiorze. Wówczas każdy taki wierzchołek dyktuje odpowiedni ruch pędzla (w pionie lub poziomie). Najmniejsze pokrycie wierzchołkowe można wyznaczyć efektywnie (wielomianowo), znajdując najpierw maksymalne skojarzenie w grafie G(V₁,V₂), czyli najliczniejszy zbiór izolowanych krawędzi (rys. 3b). W tym celu najwygodniej posłużyć się metodą ścieżki powiększającej (patrz też algorytm węgierski). W efekcie otrzymamy kolekcję maksymalnych skojarzeń, którą następnie przekształcimy w pokrycie wierzchołkowe. W naszym przykładzie już samo maksymalne skojarzenie wyznacza pokrycie wierzchołkowe.

Zagadka 4

Obecnie chcemy pokazać, że algorytm zachłanny użyty do rozwiązania zagadki 3 (tj. zawsze wybieraj linię zawierającą najwięcej niepomalowanych jeszcze kratek) nie gwarantuje wyniku optymalnego.

Rozwiązanie
Kontrprzykład pokazano na rys. 4. Zgodnie z algorytmem zachłannym Bogdan musiałby rozpocząć malowanie płotu od deski d₃, po czym musiałby przejechać po płocie jeszcze 3 razy. Łatwo zauważyć, że rozwiązanie optymalne zawiera 3 warstwy poziome.

Marek Kubale
kubale@eti.pg.edu.pl    

Joanna Raczek
joanna.raczek@pg.edu.pl