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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 43: Linia 43:
 
* {{kotwica|NASTĘPNY|NASTĘPNY}}<math>(T,s)</math> - zwraca odcinek po <math>s</math>  w porządku <math>T</math>.
 
* {{kotwica|NASTĘPNY|NASTĘPNY}}<math>(T,s)</math> - zwraca odcinek po <math>s</math>  w porządku <math>T</math>.
  
Jeżeli zaimplementujemy tę strukturę z użyciem zrównoważonych drzew wyszukiwania, to operacje te będziemy mogli zrealizować w czasie <math>O(\log n)</math>, gdzie <math>n</math> to całkowita liczba odcinków. Poniższy algorytm zwraca TRUE wtedy i tylko wtedy, gdy zbiór <math>S</math> przekazany jako argument zawiera parę przecinających się odcinków.
+
Jeżeli zaimplementujemy tę strukturę z użyciem zrównoważonych drzew wyszukiwania, to operacje te będziemy mogli zrealizować w czasie <math>O(\log n)</math>, gdzie <math>n</math> to całkowita liczba odcinków. Poniższy algorytm zwraca <math>TRUE</math> wtedy i tylko wtedy, gdy zbiór <math>S</math> przekazany jako argument zawiera parę przecinających się odcinków.
  
 
{{algorytm|sprawdza, w zbiorze <math>S</math> istnieją dwa przecinające się odcinki|ZBIÓR-ODCINKÓW-SIĘ-PRZECINA|3=
 
{{algorytm|sprawdza, w zbiorze <math>S</math> istnieją dwa przecinające się odcinki|ZBIÓR-ODCINKÓW-SIĘ-PRZECINA|3=
Linia 49: Linia 49:
 
   1  <math>T = 0</math>
 
   1  <math>T = 0</math>
 
   2  niech <math>P</math> będzie posortowanym zbiorem końców odcinków z <math>S</math> od lewej do prawej
 
   2  niech <math>P</math> będzie posortowanym zbiorem końców odcinków z <math>S</math> od lewej do prawej
   3  '''for''' każdego <math>p \in P</math> '''do'''
+
   3  '''foreach''' <math>p \in P</math> '''do'''
 
   4  '''begin'''
 
   4  '''begin'''
 
   5    '''if''' <math>p</math> to lewy koniec odcinka <math>s</math> '''then'''
 
   5    '''if''' <math>p</math> to lewy koniec odcinka <math>s</math> '''then'''
Linia 56: Linia 56:
 
   8      <math>s_p = </math>[[#POPRZEDNI|POPRZEDNI]]<math>(T,s)</math>
 
   8      <math>s_p = </math>[[#POPRZEDNI|POPRZEDNI]]<math>(T,s)</math>
 
   9      <math>s_n = </math>[[#NASTĘPNY|NASTĘPNY]]<math>(T,s)</math>
 
   9      <math>s_n = </math>[[#NASTĘPNY|NASTĘPNY]]<math>(T,s)</math>
   10    '''if''' <math>s_p \neq NIL \mbox{ i } </math> [[../Wykład 10#przecinanie_się_odcinków|ODCINKI-SIĘ-PRZECINAJĄ]]<math>(s,s_p)</math> '''then''' '''return''' TRUE
+
   10    '''if''' <math>s_p \neq NIL \mbox{ \bf i } </math> [[../Wykład 10#przecinanie_się_odcinków|ODCINKI-SIĘ-PRZECINAJĄ]]<math>(s,s_p)</math> '''then''' '''return''' <math>TRUE</math>
   11    '''if''' <math>s_n \neq NIL \mbox{ i } </math> [[../Wykład 10#przecinanie_się_odcinków|ODCINKI-SIĘ-PRZECINAJĄ]]<math>(s,s_n)</math> '''then''' '''return''' TRUE
+
   11    '''if''' <math>s_n \neq NIL \mbox{ \bf i } </math> [[../Wykład 10#przecinanie_się_odcinków|ODCINKI-SIĘ-PRZECINAJĄ]]<math>(s,s_n)</math> '''then''' '''return''' <math>TRUE</math>
 
   12  '''end'''
 
   12  '''end'''
 
   13  '''if''' <math>p</math> to prawy koniec odcinka <math>s</math> '''then'''
 
   13  '''if''' <math>p</math> to prawy koniec odcinka <math>s</math> '''then'''
Linia 63: Linia 63:
 
   15      <math>s_p = </math>[[#POPRZEDNI|POPRZEDNI]]<math>(T,s)</math>
 
   15      <math>s_p = </math>[[#POPRZEDNI|POPRZEDNI]]<math>(T,s)</math>
 
   16      <math>s_n = </math>[[#NASTĘPNY|NASTĘPNY]]<math>(T,s)</math>
 
   16      <math>s_n = </math>[[#NASTĘPNY|NASTĘPNY]]<math>(T,s)</math>
   17    '''if''' <math>s_p \neq NIL \s_n \neq NIL \mbox{ i } </math> [[../Wykład 10#przecinanie_się_odcinków|ODCINKI-SIĘ-PRZECINAJĄ]]<math>(s_p,s_n)</math> '''then''' '''return''' TRUE
+
   17    '''if''' <math>s_p \neq NIL \mbox{ \bf i } s_n \neq NIL \mbox{ \bf i } </math> [[../Wykład 10#przecinanie_się_odcinków|ODCINKI-SIĘ-PRZECINAJĄ]]<math>(s_p,s_n)</math> '''then''' '''return''' <math>TRUE</math>
 
   18    [[#USUŃ|USUŃ]]<math>(T,s)</math>
 
   18    [[#USUŃ|USUŃ]]<math>(T,s)</math>
 
   19  '''end'''
 
   19  '''end'''
 
   20  '''end'''
 
   20  '''end'''
   21  '''return''' FALSE
+
   21  '''return''' <math>FALSE</math>
 
}}
 
}}
  
Linia 74: Linia 74:
 
<flash>file=Zasd_ilustr_k.swf|width=600|height=300</flash>
 
<flash>file=Zasd_ilustr_k.swf|width=600|height=300</flash>
  
{{twierdzenie|poprawność_odcinków||3=
+
{{twierdzenie|1|poprawność_odcinków|3=
Algorytm [[#ZBIÓR-ODCINKÓW-SIĘ-PRZECINA|ZBIÓR-ODCINKÓW-SIĘ-PRZECINA]] zwraca TRUE wtedy i tylko wtedy, gdy w <math>S</math> istnieje para przecinających się odcinków.
+
Algorytm [[#ZBIÓR-ODCINKÓW-SIĘ-PRZECINA|ZBIÓR-ODCINKÓW-SIĘ-PRZECINA]] zwraca <math>TRUE</math> wtedy i tylko wtedy, gdy w <math>S</math> istnieje para przecinających się odcinków.
 
}}
 
}}
  
 
{{dowod|||3=
 
{{dowod|||3=
Algorytm [[#ZBIÓR-ODCINKÓW-SIĘ-PRZECINA|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 <math>S</math> istnieje para przecinających się odcinków, to algorytm zwróci TRUE.
+
Algorytm [[#ZBIÓR-ODCINKÓW-SIĘ-PRZECINA|ZBIÓR-ODCINKÓW-SIĘ-PRZECINA]] zwraca <math>TRUE</math> w wypadku, gdy znalazł parę przecinających się odcinków. W celu pokazania jego poprawności wystarczy więc pokazać, że jeżeli w <math>S</math> istnieje para przecinających się odcinków, to algorytm zwróci <math>TRUE</math>.
  
 
Załóżmy, że w <math>S</math> jest co najmniej jedno przecięcie. Niech <math>p</math> będzie tym najbardziej na lewo spośród nich. Niech <math>a</math> i <math>b</math> będą odcinkami przecinającymi się w <math>p</math>. Ponieważ po lewej stronie <math>p</math> nie ma żadnych przecięć, to porządek przechowywany w <math>T</math> jest poprawny do momentu przekroczenia <math>p</math>. Jak zauważyliśmy poprzednio, istnieje takie położenie <math>x</math> miotły, dla którego <math>a</math> i <math>b</math> są kolejne w porządku <math><_{x}</math>. Co więcej, istnieje takie <math>x</math>, że miotła w <math>x</math> jest na lewo od <math>p</math>. Takie <math>x</math> istnieje, ponieważ założyliśmy, że trzy odcinki nie przecinają się w jednym punkcie. W takim razie widzimy, że w <math>x</math> porządek w <math>T</math> poprawnie reprezentuje porządek <math><_{x}</math>. Odcinki <math>a</math> i <math>b</math> mogły się stać kolejne w <math>T</math>:
 
Załóżmy, że w <math>S</math> jest co najmniej jedno przecięcie. Niech <math>p</math> będzie tym najbardziej na lewo spośród nich. Niech <math>a</math> i <math>b</math> będą odcinkami przecinającymi się w <math>p</math>. Ponieważ po lewej stronie <math>p</math> nie ma żadnych przecięć, to porządek przechowywany w <math>T</math> jest poprawny do momentu przekroczenia <math>p</math>. Jak zauważyliśmy poprzednio, istnieje takie położenie <math>x</math> miotły, dla którego <math>a</math> i <math>b</math> są kolejne w porządku <math><_{x}</math>. Co więcej, istnieje takie <math>x</math>, że miotła w <math>x</math> jest na lewo od <math>p</math>. Takie <math>x</math> istnieje, ponieważ założyliśmy, że trzy odcinki nie przecinają się w jednym punkcie. W takim razie widzimy, że w <math>x</math> porządek w <math>T</math> poprawnie reprezentuje porządek <math><_{x}</math>. Odcinki <math>a</math> i <math>b</math> mogły się stać kolejne w <math>T</math>:
Linia 88: Linia 88:
 
Algorytm ten działa w czasie <math>O(n \log n)</math> gdyż na jego czas działania składa się:
 
Algorytm ten działa w czasie <math>O(n \log n)</math> gdyż na jego czas działania składa się:
 
* wykonanie linii 2 w czasie <math>O(n \log n)</math>,
 
* wykonanie linii 2 w czasie <math>O(n \log n)</math>,
* wykonanie dla każdego końca odcinka pętli '''for''' w liniach 4-20 w całkowitym czasie <math>O(n\log n)</math> - w każdym wykonaniu pętli wywoływana jest stała liczba operacji na strukturze <math>T</math>.
+
* wykonanie pętli '''foreach''' w liniach 4-20 w całkowitym czasie <math>O(n\log n)</math> - w każdym obrocie pętli wywoływana jest stała liczba operacji na strukturze <math>T</math>.
  
 
{{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óra 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:
  
 
{{wzor2|1=
 
{{wzor2|1=
Linia 138: Linia 138:
 
którego rozwiązaniem jest <math>T(n) = O(n\log n)</math>. Zauważmy, że czas potrzebny na posortowanie po raz pierwszy tablic <math>X</math> i <math>Y</math> także wynosi <math>O(n\log n)</math>. Całkowity czas potrzebny na znalezienie najmniejszej odległości między parą punktów w <math>n</math>-elementowym zbiorze wynosi więc <math>O(n \log n)</math>.
 
którego rozwiązaniem jest <math>T(n) = O(n\log n)</math>. Zauważmy, że czas potrzebny na posortowanie po raz pierwszy tablic <math>X</math> i <math>Y</math> także wynosi <math>O(n\log n)</math>. Całkowity czas potrzebny na znalezienie najmniejszej odległości między parą punktów w <math>n</math>-elementowym zbiorze wynosi więc <math>O(n \log n)</math>.
  
{{twierdzenie|poprawność_odległości||3=
+
{{twierdzenie|2|poprawność_odległości|3=
 
Algorytm [[#NAJMNIEJ-ODLEGŁA-PARA|NAJMNIEJ-ODLEGŁA-PARA]] wyznacza najmniejszą odległość między parą punktów w <math>Q</math>.
 
Algorytm [[#NAJMNIEJ-ODLEGŁA-PARA|NAJMNIEJ-ODLEGŁA-PARA]] wyznacza najmniejszą odległość między parą punktów w <math>Q</math>.
 
}}
 
}}

Wersja z 14:24, 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:

Dwa punkty w zbiorze mogą mieć tę samą współrzędną. 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

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 . 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 kwadracie 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