Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. Alicja i Bogdan zostają deweloperami | Politechnika Gdańska

Zagadka 1

Alicja otrzymała ważną informację od Dziadka, który powiedział jej, że pod ich kwadratową działką biegnie żyła złota, ale nie pamiętał dokładnie, gdzie ona przebiega. Alicja poprosiła Bogdana, by spróbował dokopać się do złota. Zakładając, że domniemana żyła ma przebieg prostoliniowy (przynajmniej pod działką), jak Bogdan powinien przekopywać działkę, by jak najszybciej dotrzeć do złota?

Rozwiązanie
Zauważmy, że schemat, według którego Bogdan będzie przeprowadzał prace, nie musi być spójny. Taki schemat rzecz jasna winien składać się z prostych odcinków, gdyż wprowadzenie łuków niepotrzebnie zwiększyłoby długość drogi koparki. W tym przypadku szukamy najkrótszego lasu spinającego wszystkie narożniki. Rozwiązanie optymalne przedstawiamy na rys. 1. Długość tego rozwiązania wynosi √2 +3/√6.
Uwaga 1.
Ogólnie problem, który przedstawiamy, to tzw. drzewo Steinera na płaszczyźnie (tutaj las). W przypadku 3 bądź 4 punktów jest on wielomianowy, lecz gdy liczba punktów jest dowolna, to problem staje się NP-trudny.

Zagadka 2

Bogdan dokopał się do złota! Nasza para postanowiła wybudować wieżowiec z halą garażową w podziemiach. Parking ma być w pełni monitorowany. Zastanawiają się, ile kamer o polu widzenia 360° muszą zakupić, by mieć gwarancję, że z ich pomocą można będzie obserwować całą powierzchnię garażu.

Rozwiązanie
Przyjmijmy, dla ustalenia uwagi, że kształt parkingu jest ortogonalny, np. taki jak na rys. 2. Dzielimy powierzchnię na trapezy (im mniej, tym lepiej). Następnie w każdym trapezie dorysowujemy przekątne i kolorujemy wierzchołki tak utworzonego grafu 4 kolorami. W końcu wybieramy ten kolor, który został użyty najmniej razy. W narożnikach garażu odpowiadających tym wierzchołkom umieszczamy kamery. Można udowodnić, że liczba użytych kamer nie przekracza [n/4], gdzie n jest liczbą ścian w garażu.

Uwaga 2
Problem tutaj rozważany nosi nazwę problemu galerii sztuki i jest NP-trudny w wielu swoich uogólnieniach. Jeżeli rozważany wielokąt jest dowolny, tj. niekoniecznie wypukły i niekoniecznie ortogonalny, to liczba potrzebnych kamer nie przekracza nigdy [n/3]. Na rys. 3 podajemy przykład garażu/galerii, dla której potrzeba dokładnie n/3 strażników.

Marek Kubale
kubale@eti.pg.edu.pl