Dziel I Zwyciezaj

Definicja

Dziel i zwyciężaj (ang. divide and conquer) jest strategią konstruowania algorytmów i jedną z najefektywniejszych metod algorytmicznych w informatyce. Problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tak długo, aż stanie się on wystarczająco prosty do bezpośredniego rozwiązania. Następnie rozwiązania otrzymane dla mniejszych podproblemów scala się uzyskując rozwiązanie całego zadania.

Twierdzenie o rekurencji uniwersalnej

Opisuje czas działania algorytmu, który dzieli problem na mniejsze podporoblemy.
Więcej możesz się dowiedzieć TUTAJ

Algorytm Karatsuby

Algorytm Karatsuby - algorytm szybkiego mnożenia dużych liczb całkowitych. Jego złożoność obliczeniowa wynosi Θ(n^log₂3). Mimo, że praktycznie nieużywany, jest niezłym przykładem algorytmu dziel i zwyciężaj.

Sposób działania

Do pomnożenia dwóch n-cyfrowych liczb x i y przy podstawie B, gdzie n=2m (jeśli n jest nieparzyste, albo x ma różną liczbę cyfr niż y, można to naprawić dodając zera po lewej stronie tych liczb), rozpisujemy je jako:

x = x₁ B^m + x₂
y = y₁ B^m + y₂

gdzie x₂ i y₂ są mniejsze niż B^m. Wynik mnożenia wynosi wtedy:

xy = (x₁B^m + x₂)(y₁B^m + y₂)

= x₁y₁B^2m + (x₁y₂ + x₂y₁)B^m + x₂y₂

Standardową metodą byłoby pomnożenie czterech czynników osobno i dodanie ich po odpowiednim przesunięciu. Daje to algorytm działający w czasie O(n²). Karatsuba zauważył że możemy ten sam wynik uzyskać wykonując tylko trzy mnożenia:

X = x₁y₁
Y = x₂y₂
Z = (x₁ + x₂)(y₁ + y₂) - X - Y

Dostajemy wtedy

Z = (x₁y₁ + x₁y₂ + x₂y₁ + x₂y₂) - x₁y₁ - x₂y₂

= x₁y₂ + x₂y₁

A zatem xy = X B^2m + Y + Z B^m tym samym kosztem kilku dodawań i odejmowań zmniejszyliśmy liczbę mnożeń z czterech do trzech.

Każde z tych mnożeń m-cyfrowych liczb możemy wykonać rekurencyjnie.

Implementacja

pomnóż(a,b)
{
    rozdziel a na a1 i a2
    rozdziel b na b1 i b2
 
    u=pomnóż(a1, b1);
    p=pomnóż(a1+a2, b1+b2);
    z=pomnóż(a2, b2);
 
    wynik = u * 10^2m + (p-u-z) * 10^m + z;
    return wynik;
}

W: "Punkty"

Mamy n punktów na płaszczyźnie. Należy znaleźć Taką parę, by odcinek łączący te punkty był najkrótszy.

Rozwiązanie

Potrzeba:
posortowaną względem współrzędnej x tablicę punktów tab[]
pustą tablicę punktów tab2[]
p, q - numery pierwszego i ostatniego rozpatrywanego punktu w tab[]
dl, dp - najkrótsze odcinki odpowiednio w prawej i lewej części płaszczyzny (po podziale przez pionową prostą l), należące do przedziału <p,q>
d - najkrótszy w ogóle do danego momentu odcinek dla przedziału <p,q>
s - dzieli przedział <p,q> na połowy

najblizsza para (p,q)
{
       if (q=p) return INFINITY; // UWAGA limity zadania przewidują nieskończoność rzędu 4*10^18, co uwzględniają testy (udowodniłem doświadczalnie)
       if (q-p=1) return odlleglosc(tab[p],tab[q]);
 
       znajdź pionową prostą l taką, że po jej lewej i prawej stronie jest po połowie punktów
       s = (p+q)/2;
       dl = najblizsza para(p,s);
       dp = najblizsza para(s+1,q);
       d = min(dl,dp); //wyznaczona długość najkrótszego odcinka na prawo lub na lewo od prostej l
 
       przepisz wszystkie punkty znajdujące się w odległości d od prostej l do nowej tablicy tab2[]
       posortuj znalezione punkty względem zmiennej y
 
       for  i=1 to rozmiar tab2
               for j=1; to min(7, rozmiar tab2 - 1)
                   if (odległość (tab2[i], tab2[i+j]) < d) d = odległość(tab2[i],tab2[i+j]);
 
       return d;
}

Zgodnie z zasadą dziel i zwyciężaj, dzielimy płaszczyznę na dwie części, aż osiągniemy zbiór zawierający dwa lub jeden punkt. Wtedy przypadku obliczenie najmniejszej odległości nie jest już problemem.
Pozostaje jedynie kwestia odcinków łączących osobne części płaszczyzny - czy nie znajdziemy wśród nich krótszego, niż najlepszy do tej pory? Warto zauważyć, że jeśli faktycznie mielibyśmy taki odcinek znaleźć, to łączyłby on punkty odległe od linii podziału o nie więcej niż d. W ich przypadku wystarczy rozpatrzyć grupy po 7 kolejnych punktów (patrząc "z góry na dół" - dlatego sortujemy względem y).