Wyszukiwanie maksimum lokalnego cz II. - O szybkim turyście i chciwym bacy

Treść tego zadania jest bardzo głupia :) Chciałem ją zmodyfikować, ale stwierdziłem, że tak będzie śmieszniej :) Miłej lektury.

Mamy dany graf w którym wyróżniono dwa wierzchołki - A oraz B. Z każdą krawędzią i są związane dwie liczby rzeczywiste: a_i oraz b_i. Koszt przejechania tej krawędzi w czasie t wynosi a_it + b_i.
Turysta chce przejść z punktu A do B. Turysta jest bardzo sprytny i w dowolnym czasie t potrafi znaleźć najtańszą drogę z punktu A do B. Jest też bardzo bardzo szybki (struś pędziwiatr to przy nim żółw) i całą trasę potrafi przebiec w czasie zerowym!

Pytanie: W jakim czasie T z przedziału [0, 1] baca powinien wypuścić turystę ze swojej chatki, aby zmaksymalizować swój zysk?

Co ma z tym wspólnego maksimum lokalne? Dla każdej ścieżki w grafie jej koszt jest funkcją liniową zależną od T.
Zatem baca jeśli wypuści turystę w czasie T zarobi min(T) dudków, gdzie min(T) jest dane wzorem:
Spójrzmy na wykres tej funkcji.
Funkcja ma tylko jedno maksimum lokalne. Możemy zatem użyć wyszukiwania ternarnego (wystarczy tylko uogólnić algorytm na przedział rzeczywisty - co pozostawiam jako proste ćwiczenie ;) )

Metoda włączeń i wyłączeń cz II.

Przedstawię dwa proste zadania, które można rozwiązać za pomocą metody włączeń i wyłączeń.

Mamy danych 10 prostopadłościanów ortogonalnych (to znaczy takich, których krawędzie są równoległe do osi układów współrzędnych). Prostopadłościany te mogą na siebie nachodzić. Pytamy o sumę objętości tych prostopadłościanów.
Prostopadłościan ortogonalny może być zapisany za pomocą pary punktów: lewego, dolnego, "bliższego" (nam) oraz prawego, górnego, "dalszego". Powiedzmy, że pewien prostopadłościan jest określony za pomocą pary: (a₁, a₂, a₃) oraz (b₁, b₂, b₃). Jego objętość można wyrazić wzorem: (b₁-a₁)(b₂-a₂)(b₃-a₃).
Bardzo łatwo także wyznaczyć przecięcie dwóch prostopadłościanów, które także jest prostopadłościanem. Jeśli pierwszy z prostopadłościanów to (a₁, a₂, a₃) oraz (b₁, b₂, b₃), a drugi: (c₁, c₂, c₃) oraz (d₁, d₂, d₃) to prostopadłościan, który jest ich przecięciem to: (max{a₁, c₁}, max{a₂, c₂}, max{a₃, c₃}) oraz (min{b₁,d₁}, min{b₂,d₂}, min{b₃,d₃}).
Tak jak nauczyliśmy się w poprzedniej części - możemy teraz obliczyć sumę objętości prostopadłościanów na podstawię ich przecięć.

Drugie zadanie jest następujące. Mamy dany zbiór S = {1, 2, 3, ..., 10⁹}. Pytamy ile jest liczb w tym zbiorze, które są podzielne przez 9, 11 lub 15?
Oznaczmy przez D_k zbiór tych wszystkich liczb należących do S, które są podzielne przez k. Nie trudno zauważyć, że |D_k| = 10⁹ / k. Przy czym dzielenie tutaj rozumiemy jako dzielenie całkowitoliczbowe.
Tak samo łatwo można policzyć przecięcie dwóch zbiorów. Wystarczy tylko zauważyć, że:
Gdzie lcm(k, l) oznacza najmniejszą wspólną wielokrotność liczb k oraz l.
Zgodnie z opisaną w poprzedniej części metodą włączeń i wyłączeń możemy obliczyć sumę zdefiniowanych wzorów.

Dobrym ćwiczeniem będzie dla każdego implementacja powyższych algorytmów. Nie powinno to nikomu sprawić większych problemów, ale warto się oswoić z tą techniką.

Metoda włączeń i wyłączeń cz I.

Zdarza się, że prosto jest policzyć liczbę elementów przecięcia kilku zbiorów, natomiast trudno liczbę elementów sumy tychże zbiorów. Przedstawimy metodę, dzięki której problem wyznaczenia sumy zbiorów sprowadzimy do wyznaczenia ich przecięć.

Dla dwóch zbiorów sytuacja wygląda prosto. Dodajemy ilość elementów zbioru pierwszego do ilości elementów zbioru drugiego i odejmujemy ilość elementów przecięcia obu zbiorów.
Dla trzech zbiorów sprawa się nieco komplikuje, ale wciąż wzór wygląda przystępnie. Najpierw sumujemy liczbę elementów poszczególnych zbiorów. Następnie odejmujemy liczbę elementów w przecięciach każdych dwóch zbiorów. Na końcu dodajemy liczbę elementów znajdujących się we wszystkich zbiorach.
Dla czterech zbiorów wzór robi się już nieczytelny. Bardzo niemiły jest też wzór dla dowolnego n:
Gdzie P₊(n) oznacza zbiór potęgowy zbioru {1, 2, ..., n} bez zbioru pustego.

Nie przejmuj się jeśli tego wzoru nie rozumiesz. Przedstawię teraz o wiele prostszą definicję metody włączeń i wyłączeń, którą łatwiej zapamiętać i łatwiej zastosować.

Aby znaleźć liczbę elementów sumy zbiorów A₁, A₂, ..., A_n znajdź liczby elementów wszystkich możliwych przecięć zbiorów spośród {A₁, A₂, ..., A_n}, dodaj do siebie wyniki uzyskane dla przecięć nieparzystej liczby zbiorów, a następnie odejmij wyniki uzyskane dla przecięć parzystej liczby zbiorów.

Dowód poprawności tej metody znajduje się na Wikipedii (http://pl.wikipedia.org/wiki/Zasada_w%C5%82%C4%85cze%C5%84_i_wy%C5%82%C4%85cze%C5%84).

Wadą tej metody jest oczywiście złożoność. Gdy mamy N zbiorów policzymy tą metodą liczebność 2^N-1 zbiorów. Niestety, niekiedy jest to najszybszy sposób.

W części drugiej przedstawię kilka przykładów zadań, które wymagają użycia tej metody.

Wyszukiwanie binarne po wynikach cz III.

W poprzedniej części pokazaliśmy, że czasami łatwiej jest powiedzieć czy dana wartość spełnia warunki zadania, niż znaleźć najmniejszą z nich. W tej części przedstawię metodę, którą można rozwiązać wszystkie przedstawione w tej serii zadania. Przyjrzyjmy się najpierw jakie warunki musi spełniać zadanie, aby można było skorzystać z wyszukiwania binarnego po wynikach.

Aby móc skorzystać z opisanej poniżej metody, zadanie musi spełniać następujące warunki:

• Szukamy element e który:
• Spełnia warunki zadania
• Jest najmniejszym {największym} takim elementem
• Dla każdych elementów d oraz d' takich, że d < d' {d > d'} to jeśli d spełnia warunki zadania, to d' także

Drugi warunek może wydawać się dla niektórych skomplikowany. Dlatego rozpatrzymy go na przykładach:

Zadanie o krowach (d > d'). Jeśli potrafimy tak rozdzielić krowy, aby każda z nich była oddalona o conajmniej d jednostek od siebie, to potrafimy to też zrobić aby odległość między każdą z nich była większa o d' (wystarczy wybrać te same obory).

Zadanie o złodzieju (d > d'). Jeśli potrafimy tak wybrać przedmioty aby odpowiedni iloczyn był niemniejszy niż d, to potrafimy też tak je wybrać aby był niemniejszy od d' (wystarczy wybrać te same przedmioty).

Zadanie o zabytkach (d < d'). Jeśli potrafimy znaleźć po d dniach cykl w grafie, to potrafimy też znaleźć cykl po d' dniach (wystarczy "znaleźć" ten sam cykl).

Zatem drugi warunek mówi nam rzecz następującą. Podzielmy wszystkie elementy na dwa zbiory. W pierwszy zbiorze znajdą się wszystkie te liczby, które spełniają warunek zadania, a w drugim te które tego warunku nie spełniają. Każdy element w tym pierwszym zbiorze jest większy {mniejszy} niż każdy element w tym drugim. Prezentuje nam to poniższy rysunek:
Metoda wyszukiwania binarnego po wyniku przypomina zabawę w zgadywankę. Ja pomyślę o jakiejś liczbie. Ty będziesz zgadywał jaka to liczba, a ja będę mówił czy moja liczba jest większa czy mniejsza lub równa.

Pierwszym krokiem będzie znalezienie 2 elementów. Pierwszy z nich ma spełniać warunki zadania, a drugi nie. Oznaczmy je jako S_min oraz S_max.

Nasze rozwiązanie będzie znajdowało się gdzieś w środku (S_min, S_max). Policzmy średnią S_śr = (S_min + S_max) / 2. W zależności od tego czy S_śr spełnia czy nie spełnia warunków zadania, może zmniejszyć obszar naszych poszukiwań do (S_min, S_śr) lub (S_śr, S_max). Cały akapit powtarzamy dopóki nie będziemy pewni poprawnej odpowiedzi.

Istnieje wiele niepoprawnych algorytmów do zadań, które tu omówiliśmy. W następnej notce zaprezentuję kontrprzykłady do niektórych z nich.

Wyszukiwanie binarne po wynikach cz II.

Przypomnijmy, że wszystkie zadania z części pierwszej to zadania optymalizacyjne. Szukamy największej (najmniejszej) wartości, która spełnia pewne określone warunki. W drugiej części zamiast szukać takiej wartości, sprawdzimy czy konkretna wartość k spełnia dane warunki.

Zadanie o krowach. Napiszmy algorytm, który zwróci prawdę jeśli da się tak ustawić krowy, aby każde dwie z nich były oddalone od siebie o co najmniej k jednostek. Zadanie to daje się rozwiązać zachłannie. Dla pierwszej krowy wybieramy oborę położoną najbardziej na lewo. Następnie usuwamy wszystkie obory, które znajdują się mniej niż k jednostek od tej. Powtarzamy to do momentu, w którym zabraknie nam krów lub miejsc w oborach. Jeśli braknie nam krów to znaczy, że da się tak ułożyć w oborach, aby każde dwie były oddalone od siebie o co najmniej k. Jeśli braknie nam obór, to oznacza że się nie da.

Zadanie o złodzieju. Sprawdzamy czy da się wybrać tak i przedmiotów, aby określony w zadaniu iloraz był większy bądź równy k. Dokonując kolejnych modyfikacji ilorazu, dostajemy następujący wzór (jako I rozumiemy w tym wzorze zbiór wybranych przez złodzieja przedmiotów):Wzór ten można łatwo sprawdzić. Wybieramy i przedmiotów, których wartość cena - k * waga jest najmniejsza wśród wszystkich przedmiotów. Jeśli suma tych wartości i przedmiotów jest większa lub równa od zera to znaczy że da się wybrać i przedmiotów aby iloczyn sumy cen do sumy wag był większy bądź równy niż k. Jeśli jest mniejsza od zera to nie da się.

Zadanie o zabytkach. Sprawdzamy czy po k dniach będzie można wybrać jakiś zabytek, a następnie autostradami przejechać przez kilka innych zabytków i wrócić do pierwszego. To zadanie z tych trzech jest chyba najprostsze. Bierzemy zabytki jako wierzchołki, k pierwszych autostrad jako krawędzie skierowane i sprawdzamy czy tak utworzony graf jest grafem cyklicznym.

Mamy trzy procedury, które w czasie liniowym (czyli bardzo szybko) mówią nam, czy k spełnia określone w zadaniach warunki. W następnej części napiszę, jak na podstawie tych funkcji napisać procedurę, która znajdzie najmniejsze (największe) takie k, które spełnia warunki zadania.

Wyszukiwanie binarne po wynikach cz I.

W części pierwszej przedstawię trzy zadania. Wszystkie zadanie można rozwiązać za pomocą metody zwanej wyszukiwaniem binarnym po wyniku. Oto i one:

Zadanie o krowach. Farmer John wybudował nową oborę dla krów z N boksami. Boksy są ulokowane w linii prostej na pozycjach x₁, x₂, ..., x_N. John ma C (C <= N) krów. Przy czym nie lubią one przebywać blisko ze sobą. Dlatego John chce tak umieścić krowy w boksach, aby odległość między dwoma najbliższymi krowami była możliwie jak największa.

Zadanie o złodzieju. Mamy dane n przedmiotów. Każdy przedmiot ma określoną cenę oraz określoną wagę. Złodziej chce ukraść i przedmiotów. Przy czym chce wybrać tak przedmioty, aby stosunek sumy cen wszystkich ukradzionych przedmiotów do sumy ich wag była jak największa. Należy podać wartość iloczynu z dokładnością dwóch cyfr po przecinku.

Zadanie o zabytkach. Mamy w mieście n zabytków. Chcemy je połączyć m jednokierunkowymi drogami. W każdym dniu będzie budowana jedna droga. Kolejność budowy dróg jest ustalona. Pytamy o najmniejsze takie k, że po k dniach będzie istnieć ścieżka zaczynająca się i kończąca przy tym samym zabytku.

Proponuję, aby Czytelnik spróbował samodzielnie rozwiązać każde z powyższych zadań. W tym miejscu nie ważna jest złożoność Twoich rozwiązań, ale docelowo będziemy chcieli, aby rozwiązania działały w czasie liniowo-logarytmicznym.

W II części wyjaśni się co te na pozór różne zadania mają ze sobą wspólnego.