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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 92: Linia 92:
 
{{kotwica|najmniej_odlegla_para|}}
 
{{kotwica|najmniej_odlegla_para|}}
 
== Najmniej odległa para punktów ==
 
== Najmniej odległa para punktów ==
Będziemy się teraz zajmować problemem znalezienia najmniej odległej pary punktów w zbiorze <math>Q</math>, gdzie <math>|Q|\ge 2</math>. Interesować nas tutaj będzie odległość euklidesowa, którą dla punktów <math>p = (x_p, y_p)</math>, <math>q = (x_q, y_q)</math> oznaczamy przez <math>|p-q|</math>, oraz definiujemy:
+
Będziemy się teraz zajmować problemem znalezienia najmniej odległej pary punktów w zbiorze <math>Q</math>, gdzie <math>|Q|\ge 2</math>. Interesować nas tutaj będzie odległość euklidesowa, którą dla punktów <math>p = (x_p, y_p)</math>, <math>q = (x_q, y_q)</math> oznaczamy przez <math>|p-q|</math>, oraz definiujemy jako:
  
 
{{wzor2|1=
 
{{wzor2|1=
Linia 98: Linia 98:
 
}}
 
}}
  
Dwa punkty w zbiorze <math>Q</math> mogą mieć tę samą współrzędną. W takim przypadku odległość między nimi wynosi <math>0</math>. 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 <math>\left(\begin{matrix}|Q|\\2\end{matrix}\right)</math> parami punktów, możemy ten problem rozwiązać w czasie <math>O(n^2)</math>. Pokażemy teraz, jak wykorzystując technikę [[../Wykład 11#dziel_i_zwyciężaj|dziel i zwyciężaj]]  problem ten można rozwiązać w czasie <math>O(n \log n)</math>.
+
Dwa punkty w zbiorze <math>Q</math> mogą mieć te same współrzędne. W takim przypadku odległość między nimi wynosi <math>0</math>. 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 <math>\left(\begin{matrix}|Q|\\2\end{matrix}\right)</math> parami punktów, możemy ten problem rozwiązać w czasie <math>O(n^2)</math>. Pokażemy teraz, jak wykorzystując technikę [[../Wykład 11#dziel_i_zwyciężaj|dziel i zwyciężaj]]  problem ten można rozwiązać w czasie <math>O(n \log n)</math>.
  
 
=== Algorytm ===
 
=== Algorytm ===
Linia 130: Linia 130:
 
<math>
 
<math>
 
T(n)=\begin{cases}
 
T(n)=\begin{cases}
2 T(\farc{n}{2}) + O(n) & \mbox{jeżeli } n>2,\\
+
2 T(\frac{n}{2}) + O(n) & \mbox{jeżeli } n>2,\\
 
O(1) & \mbox{jeżeli } n \le 2.
 
O(1) & \mbox{jeżeli } n \le 2.
 
\end{cases}
 
\end{cases}
Linia 145: Linia 145:
 
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>, 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.
 
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>, 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 (zobacz rysunek poniżej).
+
Rozważmy teraz prostokąt rozmiaru <math>2d \times d</math> ułożony centralnie na linii <math>l</math>. W prostokącie 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>
 
<flash>file=Zasd_ilustr_g_stat.swf|width=400|height=200</flash>

Wersja z 14:29, 28 wrz 2006

Abstrakt

W ramach tego wykładu przedstawimy dwa algorytmy 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

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 istnieją dwa odcinki, 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 uporządkować odcinki przecinające ją zgodnie z kolejnością przecięć. Niech i będą dwoma odcinakami. Powiemy, że są one porównywalne w jeżeli miotła umieszczona w przecina je obydwa. Mówimy, że jest powyżej w , i oznaczamy , jeżeli i są porównywalne w oraz przecięcie z miotłą w jest wyżej niż przecięcie z z tą miotłą.

Ćwiczenie

Pokaż jak sprawdzić, używając technik z poprzedniego wykładu, czy dwa odcinki i są porównywalne w ?


Ćwiczenie

Pokaż jak sprawdzić, używając technik z poprzedniego wykładu, czy dla dwóch porównywalnych nie przecinających się odcinków i zachodzi ?

Dla każdego porządek jest porządkiem całkowitym na odcinkach przecinających miotłę w . Jednak porządek ten może być różny dla różnych 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 i musi istnieć takie położenie miotły , dla którego i będą kolejne w porządku . Tę własność właśnie wykorzystamy w algorytmie, który za chwilę skonstruujemy.

Algorytm

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

  • WSTAW - wstawia odcinek do porządku ,
  • USUŃ - usuwa odcinek z porządku ,
  • POPRZEDNI - zwraca odcinek przed w porządku ,
  • NASTĘPNY - zwraca odcinek po w porządku .

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

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


 ZBIÓR-ODCINKÓW-SIĘ-PRZECINA
 1  
 2  niech  będzie posortowanym zbiorem końców odcinków z  od lewej do prawej
 3  foreach  do
 4  begin
 5    if  to lewy koniec odcinka  then
 6    begin
 7      WSTAW
 8      POPRZEDNI
 9      NASTĘPNY
 10     if Parser nie mógł rozpoznać (błąd składni): {\displaystyle s_p \neq NIL \mbox{ \bf i } }
 ODCINKI-SIĘ-PRZECINAJĄ then return 
 11     if Parser nie mógł rozpoznać (błąd składni): {\displaystyle s_n \neq NIL \mbox{ \bf i } }
 ODCINKI-SIĘ-PRZECINAJĄ then return 
 12   end
 13   if  to prawy koniec odcinka  then
 14   begin
 15      POPRZEDNI
 16      NASTĘPNY
 17     if Parser nie mógł rozpoznać (błąd składni): {\displaystyle s_p \neq NIL \mbox{ \bf i } s_n \neq NIL \mbox{ \bf i } }
 ODCINKI-SIĘ-PRZECINAJĄ then return 
 18     USUŃ
 19   end
 20  end
 21  return 

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

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

Twierdzenie 1

Algorytm ZBIÓR-ODCINKÓW-SIĘ-PRZECINA zwraca wtedy i tylko wtedy, gdy w istnieje para przecinających się odcinków.

Dowód

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

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

  • po wstawieniu jednego z nich do , taka sytuacja będzie wykryta w liniach 8-11,
  • po usunięciu odcinka między nimi, taką sytuację wykryjemy w liniach 15-17. End of proof.gif

Algorytm ten działa w czasie gdyż na jego czas działania składa się:

  • wykonanie linii 2 w czasie ,
  • wykonanie pętli foreach w liniach 4-20 w całkowitym czasie - w każdym obrocie pętli wywoływana jest stała liczba operacji na strukturze .

Najmniej odległa para punktów

Będziemy się teraz zajmować problemem znalezienia najmniej odległej pary punktów w zbiorze , gdzie . Interesować nas tutaj będzie odległość euklidesowa, którą dla punktów , oznaczamy przez , oraz definiujemy jako:

Dwa punkty w zbiorze mogą mieć te same współrzędne. W takim przypadku odległość między nimi wynosi . 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 parami punktów, możemy ten problem rozwiązać w czasie . Pokażemy teraz, jak wykorzystując technikę dziel i zwyciężaj problem ten można rozwiązać w czasie .

Algorytm

W celu uniknięcia wielokrotnego sortowania punktów w wywołaniach rekurencyjnych, wykorzystamy dwie tablice i , które zawierały będą wszystkie punkty z posortowane odpowiednio po 'owej współrzędnej i 'owej współrzędnej. Jeżeli podzielimy zbiór na dwie części: i , to odpowiednie tablice i , zawierające posortowane elementy z i można wyznaczyć w czasie . Musimy po prostu, przeglądając tablicę oraz , kopiować elementy w napotkanej kolejności do mniejszych tablic.

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


 NAJMNIEJ-ODLEGŁA-PARA
 1  if  then return 
 2  if  then return 
 3  korzystając z tablicy  znajdź pionową prostą  taką, że po jej lewej i
    prawej stronie jest  punktów
 4  niech   i  to będą punkty odpowiednio po lewej i prawej stronie 
 5  wyznacz tablice  oraz 
 6  NAJMNIEJ-ODLEGŁA-PARA
 7  NAJMNIEJ-ODLEGŁA-PARA
 8  
 9  niech  będzie tablicą  po usunięciu z niej punktów odległych od  o więcej niż 
 10 for  to  do
 11   for  to  do
 12     if  then 
 13 return 

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

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

którego rozwiązaniem jest . Zauważmy, że czas potrzebny na posortowanie po raz pierwszy tablic i także wynosi . Całkowity czas potrzebny na znalezienie najmniejszej odległości między parą punktów w -elementowym zbiorze wynosi więc .

Twierdzenie 2

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

Dowód

Jeżeli najmniej odległa para punktów znajduje się w zbiorze bądź , 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 i . Oznaczmy, tak jak w algorytmie, przez najmniejszą z odległości i . Widzimy teraz, że aby odległość między i mogła być mniejsza niż , punkty te nie mogą być bardziej odległe od niż o . W związku z tym usunięcie bardziej odległych punktów z w linii 9 algorytmu nie zmieni wyniku.

Rozważmy teraz prostokąt rozmiaru ułożony centralnie na linii . W prostokącie tym może znajdować się co najwyżej punktów z i , gdyż odległość między nimi jest co najmniej . 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 End of proof.gif