Zaawansowane algorytmy i struktury danych/Wykład 12: Różnice pomiędzy wersjami

Wersja z 11:12, 3 sie 2006

Abstrakt

W ramach tego wykładu przedstawimy dwa algorytmu obrazujące wykorzystanie dwóch technik konstrukcji algorytmów geometrycznych. Do konstrukcji algorytmu sprawdzającego, czy w zbiorze odcinków istnieją dwa przecinające się użyjemy techniki zamiatania. Natomiast do konstrukcji algorytmu wyznaczającego najmniejszą odległość w zbiorze punktów użyjemy techniki dziel i zwyciężaj.

Przecinanie się zbioru odcinków

przecinanie_się_zbioru_odcinków Problem jaki nas będzie interesował, to problem przecinania się zbioru odcinków, w którym mamy za zadanie sprawdzić, czy w danym zbiorze odcinków $S$ istnieją dwa które się przecinają. Wykorzystamy tutaj algorytm sprawdzania, czy para odcinków się przecina zaprezentowany na poprzednim wykładzie (zobacz).

W celu uproszczenia prezentacji idei algorytmu poczynimy dwa upraszczające założenia. Po pierwsze załóżmy, że żaden z odcinków nie jest pionowy. Po drugie załóżmy, że żadne trzy odcinki nie przecinają się w jednym punkcie. Algorytm ten może być prosto zmieniony tak aby działał bez tych założeń.Ćwiczenie 1 do tego wykładu polega na pokazaniu tej modyfikacji. Jednak nie zawsze jest tak prosto. Bardzo często największym kłopotem w dowiedzeniu poprawności działania algorytmu geometrycznego jest poradzenie sobie ze wszystkimi szczególnymi i brzegowymi przypadkami.

Ponieważ założyliśmy, że w zbiorze nie ma odcinków pionowych, to każdy z odcinków może przecinać miotłę w co najwyżej jednym punkcie. Dlatego dla każdego położenia miotły możemy więc uporządkować odcinki przecinające ją zgodnie z kolejnością przecięć. Niech $s_{1}$ i $s_{2}$ będą dwoma odcinakami. Powiemy, że są one porównywalne w $a$ jeżeli miotła umieszczona w $x = a$ przecina je obydwa. Mówimy, że $s_{1}$ jest powyżej $s_{2}$ w $a$ , i oznaczamy $s_{1} >_{a} s_{2}$ , jeżeli $s_{1}$ i $s_{2}$ są porównywalne w $a$ oraz przecięcie $s_{1}$ z miotłą w $x = a$ jest wyżej niż przecięcie z $s_{2}$ z tą miotłą.

Ćwiczenie

Pokaż, używając technik z poprzedniego wykładu, jak sprawdzić, czy dwa odcinki $s_{1}$ i $s_{2}$ są porównywalne w $a$ ?

Wystarczy sprawdzić, czy odcinki te przekraczają dowolny odcinek współliniowy z prostą $x = a$ , np. odcinek $(a, 0) - (a, 1)$ .

Ćwiczenie

Pokaż używając technik z poprzedniego wykładu jak sprawdzić, czy dla dwóch porównywalnych nie przecinających się odcinków $s_{1}$ i $s_{2}$ zachodzi $s_{1} <_{a} s_{2}$ ?

Dla każdego $a$ porządek $<_{a}$ jest porządkiem całkowitym na odcinkach przecinających miotłę w $x = a$ . Jednak porządek ten może być różny dla różnych $a$ ponieważ:

dla różnych położeń miotły różne odcinki ją przecinają,
jeżeli odcinki się przecinają to ich kolejność po obydwu stronach przecięcia jest różna.

Co więcej ponieważ zakładamy, że żadne trzy odcinki nie przecinają się w tym samym punkcie, to dla każdej pary przecinających się odcinków $e$ i $f$ musi istnieć takie położenie miotły $a$ dla którego $e$ i $f$ będą kolejne w porządku $<_{a}$ . Tą własność właśnie wykorzystamy w algorytmie który za chwile skonstruujemy.

Algorytm

Będziemy przechowywać informację o porządku na odcinkach aktualnie przecinających miotłę w strukturze $T$ pozwalającej na wykonanie następujących operacji:

WSTAW $(T, s)$ - wstawia odcinek $s$ do porządku $T$ ,
USUŃ $(T, s)$ - usuwa odcinek $s$ z porządku $T$ ,
POPRZEDNI $(T, s)$ - zwraca odcinek przed $s$ w porządku $T$ ,
NASTĘPNY $(T, s)$ - zwraca odcinek po $s$ w porządku $T$ .

Jeżeli zaimplementujemy tą strukturę z użyciem zrównoważonych drzew przeszukiwania, to operacje te będziemy mogli zrealizować w czasie $O (\log n)$ , gdzie $n$ to całkowita liczba odcinków. Poniższy algorytm zwraca TRUE wtedy i tylko wtedy gdy zbiór $S$ przekazany my jako argument zawiera parę przecinających się odcinków.

Algorytm sprawdza, w zbiorze $S$ istnieją dwa przecinające się odcinki

 ZBIÓR-ODCINKÓW-SIĘ-PRZECINA $(S)$ 
 1   $T = 0$ 
 2  niech  $P$  będzie posortowanym zbiorem końcy odcinków z  $S$  od lewej do prawej
 3  for każdego  $p \in P$  do
 4  begin
 5    if  $p$  to lewy koniec odcinka  $s$  then
 6    begin
 7      WSTAW $(T, s)$ 
 8       $s_{p} =$ POPRZEDNI $(T, s)$ 
 9       $s_{n} =$ NASTĘPNY $(T, s)$ 
 10     if  $s_{p} \neq N I L i$  ODCINKI-SIĘ-PRZECINAJĄ $(s, s_{p})$  then return TRUE
 11     if  $s_{n} \neq N I L i$  ODCINKI-SIĘ-PRZECINAJĄ $(s, s_{n})$  then return TRUE
 12   end
 13   if  $p$  to prawy koniec odcinka  $s$  then
 14   begin
 15       $s_{p} =$ POPRZEDNI $(T, s)$ 
 16       $s_{n} =$ NASTĘPNY $(T, s)$ 
 17     if Parser nie mógł rozpoznać (nieznana funkcja „\s”): {\displaystyle s_p \neq NIL \s_n \neq NIL \mbox{ i } }
 ODCINKI-SIĘ-PRZECINAJĄ $(s_{p}, s_{n})$  then return TRUE
 18     USUŃ $(T, s)$ 
 19   end
 20  end
 21  return FALSE

Następująca animacja przedstawia działania tego algorytmu.

<flash>file=Zasd_Ilustr_k_04.swf|width=600|height=300</flash>

Twierdzenie poprawność_odcinków

Algorytm ZBIÓR-ODCINKÓW-SIĘ-PRZECINA zwraca TRUE wtedy i tylko wtedy gdy w

S

istnieje para przecinających się odcinków.

Dowód

Algorytm ZBIÓR-ODCINKÓW-SIĘ-PRZECINA zwraca TRUE w wypadku, gdy znalazł parę przecinających się odcinków. W celu pokazania jego poprawności wystarczy więc pokazać, że jeżeli w

S

istnieje para przecinających się odcinków to algorytm zwróci TRUE.

Załóżmy, że w $S$ jest co najmniej jedno przecięcie. Niech $p$ będzie tym najbardziej na lewo spośród nich. Niech $a$ i $b$ będą odcinkami przecinającymi się w $p$ . Ponieważ po lewej stronie $p$ nie ma żadnych przecięć, to porządek przechowywany w $T$ jest poprawny do momentu przekroczenia $p$ . Jak zauważyliśmy poprzednio istnieje takie położenie $x$ miotły, dla którego $a$ i $b$ są kolejne w porządku $<_{x}$ . Co więcej istnieje takie $x$ , że miotła w $x$ jest na lewo od $p$ . Takie $x$ istnieje ponieważ założyliśmy, że trzy odcinki nie przecinają się w jednym punkcie. W takim bądź razie widzimy, że w $x$ porządek w $T$ poprawnie reprezentuje porządek $<_{x}$ . Odcinki $a$ i $b$ mogły się stać kolejne w $T$ :

po wstawieniu jednego z nich do $T$ i taka sytuacja będzie wykryta w liniach 8-11,
po usunięciu odcinka między nimi, taką sytuację wykryjemy w liniach 15-17.

Algorytm ten działa w czasie $O (n \log n)$ gdyż na jego czas działania składa się:

wykonanie linii 2 w czasie $O (n \log n)$ ,
wykonanie dla każdego końca odcinka pętli for w liniach 4-20 w całkowitym czasie $O (n \log n)$ - w każdym wykonaniu pętli wywoływanych jest stała liczba operacji na strukturze $T$ .

Najmniej odległa para punktów

Będziemy się teraz zajmować problemem znalezienia najmniej odległej pary punktów w zbiorze $Q$ , gdzie $| Q | \geq 2$ . Interesować nas tutaj będzie odległość Euklidesowa, która dla punktów $p = (x_{p}, y_{p})$ , $q = (x_{q}, y_{q})$ oznaczamy przez $| p - q |$ , oraz definiujemy:

| p - q | = \sqrt{(x_{p} - x_{q})^{2} + (y_{p} - y_{q})^{2}} .

Dwa punkty w zbiorze $Q$ mogą mieć tą samą współrzędną, w takim przypadku odległość między nimi wynosi $0$ . Informacja o najbliższej parze punktów może być przydatna w wypadku, gdy chcemy wykrywać kolizję między obiektami np. w systemach kontroli ruchu. Wyznaczając wszystkie odległości między $(\begin{matrix} | Q | \\ 2 \end{matrix})$ parami punktów możemy ten problem rozwiązać w czasie $O (n^{2})$ . Pokażemy teraz jak wykorzystując technikę dziel i zwyciężaj problem ten można rozwiązać w czasie $O (n \log n)$ .

W celu uniknięcia wielokrotnego sortowania punktów w wywołaniach rekurencyjnych. Wykorzystamy dwie tablice $X$ i $Y$ , które zawierały będą wszystkie punkty z $Q$ posortowane odpowiednio po $x$ 'owej współrzędnej i $y$ 'owej współrzędnej. Jeżeli podzielimy zbiór $Q$ na dwie części $Q_{L}$ i $Q_{R}$ , to odpowiednie tablice $X_{L}, Y_{L}$ i $X_{R}, Y_{R}$ zawierające posortowane elementy z $Q_{L}$ i $Q_{R}$ można wyznaczyć w czasie $O (| Q |)$ . Musimy po prostu przeglądając tablicę $X$ oraz $Y$ kopiować elementy w napotkanej kolejności do mniejszych tablic.

Algorytm znajduje najmniejszą odległość między parą punktów w $Q$

 NAJMNIEJ-ODLEGŁA-PARA $(Q, X, Y)$ 
 1  if  $| Q | = 2$  then return  $\infty$ 
 2  if  $| Q | = 2$  then return  $| Q [1] - Q [2] |$ 
 3  korzystając z tablicy  $X$  znajdź pionową prostą  $l$  taką, że po jej lewej i 
    prawej stronie jest  $⌊ \frac{| Q |}{2} ⌋$  punktów
 4  niech  $Q_{L}$   i  $Q_{P}$  to będą punkty odpowiednio po lewej i prawej stronie  $l$ 
 5  wyznacz tablice  $X_{L}, X_{P}$  oraz  $Y_{L}, Y_{P}$ 
 6  Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_L = NAJMNIEJ-ODLEGŁA-PARA(Q_L, X_L, Y_L)}

 7  Parser nie mógł rozpoznać (błąd składni): {\displaystyle d_R = NAJMNIEJ-ODLEGŁA-PARA(Q_R, X_R, Y_R)}

 8   $d = \min (d_{L}, d_{R})$ 
 9  niech  $Y^{'}$  będzie tablicą  $Y$  po usunięciu z niej punktów odległych od  $l$  o więcej niż  $d$ 
 10 for  $i = 1$  to  $| Y^{'} |$  do
 11   for  $j = 1$  to  $\min (7, | Y^{'} | - i)$  do
 12     if  $| P [i] - P [i + j] | < d$  then  $d = | P [i] - P [i + j] |$ 
 13 return  $d$

Działanie tej procedury przedstawione jest na poniższej animacji. <flash>file=Zasd_Ilustr_g_02.swf|width=600|height=300</flash>

Nie wliczając wywołań rekurencyjnych procedura ta działa w czasie liniowym. Zakładając, że $| Q | = n$ , otrzymujemy równanie rekurencyjne na czas działania w postaci

Parser nie mógł rozpoznać (nieznana funkcja „\farc”): {\displaystyle T(n)=\begin{cases} 2 T(\farc{n}{2}) + O(n) & \mbox{jeżeli } n>2,\\ O(1) & \mbox{jeżeli } n \le 2. \end{cases} }

Którego rozwiązaniem jest $T (n) = O (n \log n)$ . Zauważmy, że czas potrzebny na posortowanie po raz pierwszy tablic $X$ i $Y$ także wynosi $O (n \log n)$ . Całkowity czas potrzebny na znalezienie najmniejszej odległości między parą punktów w $n$ -elementowym zbiorze wynosi więc $O (n \log n)$ .

Twierdzenie poprawność_odległości

Algorytm NAJMNIEJ-ODLEGŁA-PARA wyznacza najmniejszą odległość między parą punktów w

Q

.

Dowód

Jeżeli najmniej odległa para punktów znajduje się w zbiorze

Q_{L}

bądź

Q_{P}

to zostanie ona znaleziona w wywołaniu rekurencyjnym. W takim razie musimy rozważyć tylko przypadek, w którym najmniej odległa para punktów to

p_{L} \in Q_{L}

i

p_{R} \in Q_{R}

. Oznaczmy, tak jak w algorytmie, przez

d

najmniejszą z odległości

d_{L}

i

d_{R}

. Widzimy teraz, że aby odległość między

p_{L}

i

p_{R}

mogła być mniejsza niż

d

, to punkty te nie mogą być bardziej odległe od

l

niż o

d

. W związku z tym usunięcie bardziej odległych punktów z

Y

w linii 9 algorytmu nie zmieni wyniku.

Rozważmy teraz prostokąt rozmiaru $2 d \times d$ ułożony centralnie na linii $l$ , w kwadracie tym może znajdować się co najwyżej $8$ punktów z $Q_{L}$ i $Q_{R}$ gdyż odległość między nimi jest co najmniej $d$ . Zauważmy, że punktów mieszczących się w tym prostokącie znajdujących się poniżej danego punktu jest co najwyżej 7 (zobacz rysunek poniżej).

<flash>file=Zasd_Ilustr_g_stat.swf

@@ Linia 106: / Linia 106: @@
   '''if''' <math>|Q|=2</math> '''then''' '''return''' <math>\infty</math>
   '''if''' <math>|Q|=2</math> '''then''' '''return''' <math>|Q[1] - Q[2]|</math>
-  korzystając z tablicy <math>X</math> znajdź pionową prostą <math>l</math> taką, że po jej lewej i prawej stronie jest <math>\lfloor \frac{|Q|}{2} \rfloor</math> punktów
+  korzystając z tablicy <math>X</math> znajdź pionową prostą <math>l</math> taką, że po jej lewej i
+     prawej stronie jest <math>\lfloor \frac{|Q|}{2} \rfloor</math> punktów
   niech <math>Q_L</math>  i <math>Q_P</math> to będą punkty odpowiednio po lewej i prawej stronie <math>l</math>
   wyznacz tablice <math>X_L,X_P</math> oraz <math>Y_L,Y_P</math>
@@ Linia 142: / Linia 143: @@
 Jeżeli najmniej odległa para punktów znajduje się w zbiorze <math>Q_L</math> bądź <math>Q_P</math> to zostanie ona znaleziona w wywołaniu rekurencyjnym. W takim razie musimy rozważyć tylko przypadek, w którym najmniej odległa para punktów to <math>p_L\in Q_L</math> i <math>p_R \in Q_R</math>. Oznaczmy, tak jak w algorytmie, przez <math>d</math> najmniejszą z odległości <math>d_L</math> i <math>d_R</math>. Widzimy teraz, że aby odległość między <math>p_L</math> i <math>p_R</math> mogła być mniejsza niż <math>d</math>, to punkty te nie mogą być bardziej odległe od <math>l</math> niż o <math>d</math>. W związku z tym usunięcie bardziej odległych punktów z <math>Y</math> w linii 9 algorytmu nie zmieni wyniku.
-Rozważmy teraz prostokąt rozmiaru <math>2d \times d</math> ułożony centralnie na linii <math>l</math>, w kwadracie tym może znajdować się co najwyżej <math>8</math> punktów z <math>Q_L</math> i <math>Q_R</math> gdyż odległość między nimi jest co najmniej <math>d</math>. Zauważmy, że punktów mieszczących się w tym prostokącie znajdujących się poniżej danego punktu jest co najwyżej 7. Gdyby było ich więcej to odległość między nimi musiałaby być mniejsza niż <math>d</math>. Dlatego też w linii 11 algorytmu możemy ograniczyć się do przejrzenia tylko 7 kolejnych punktów.
+Rozważmy teraz prostokąt rozmiaru <math>2d \times d</math> ułożony centralnie na linii <math>l</math>, w kwadracie tym może znajdować się co najwyżej <math>8</math> punktów z <math>Q_L</math> i <math>Q_R</math> gdyż odległość między nimi jest co najmniej <math>d</math>. Zauważmy, że punktów mieszczących się w tym prostokącie znajdujących się poniżej danego punktu jest co najwyżej 7 (zobacz rysunek poniżej).
+<flash>file=Zasd_Ilustr_g_stat.swf|width=400|height=200</flash>
+Gdyby było ich więcej to odległość między nimi musiałaby być mniejsza niż <math>d</math>. Dlatego też w linii 11 algorytmu możemy ograniczyć się do przejrzenia tylko 7 kolejnych punktów.
 }}

Zaawansowane algorytmy i struktury danych/Wykład 12: Różnice pomiędzy wersjami

Wersja z 11:12, 3 sie 2006

Spis treści

Abstrakt

Przecinanie się zbioru odcinków

Algorytm

Najmniej odległa para punktów

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia