8 września 2008

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 Smin oraz Smax.

Nasze rozwiązanie będzie znajdowało się gdzieś w środku (Smin, Smax). Policzmy średnią Sśr = (Smin + Smax) / 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 (Smin, Sśr) lub (Sśr, Smax). 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.

Brak komentarzy: