Ternarno pretraživanje

Ternarno pretraživanje je po ideji nadogradnja binarnog pretraživanja. Ako još niste, ozbiljno vas potičemo da pogledate članak o Binarnom pretraživanju.

Uvjet

Osnovni preduvjet binarnog pretraživanja jest poredanost funkcije (niza) u kojem pretražujemo. Niz je mogao biti poredan bilo uzlazno, bilo silazno, a jednaki elementi bili su dopušteni.

U osnovi, ternarno pretraživanje koristimo kako bismo pronašli minimum ili maksimum funkcije (niza) koja ima točno jedan ekstrem i kojoj su sve uzastopne vrijednosti različite. Drugim riječima, funkcije na kojima je algoritam ternarnog pretraživanja iskoristiv su one koje prvo strogo padaju, a zatim strogo rastu ili strogo rastu, a zatim padaju.

{F112,size=full}

Ideja i dokaz

Za početak, zamislimo strogo rastući, a zatim strogo padajući niz (analogno vrijedi i za bilo koju odgovarajuću funkciju):

T = [ 1, 3, 4, 7, 10, 15, 14, 9, 6, 2, 0];

U nizu T odabrat ćemo dva indeksa koji se nalaze na prvoj i na drugoj trećini niza. U našem slučaju, to su: a = 11/3 = 3; i b = 2 * 11/3 = 7; (obratite pažnju da ne smijemo pisati b = 2/3*11 ☺).

Uspoređujemo T[a] (7) i T[b] (9). U ovom je slučaju T[a] < T[b] pa sa sigurnošću možemo zaključiti kako se najveća vrijednost u nizu ne nalazi u prvoj trećini niza. U slučaju da vrijedi T[a] > T[b], mogli bismo zaključiti da se najveća vrijednost ne nalazi u zadnjoj trećini niza.

Zašto to funkcionira?

Znamo da je T[0] < T[a] i znamo da je T[a] < T[b]. Kada bi se u prvoj trećini niza nalazio traženi, najveći element, on bi sigurno bio veći od T[a], pa bi niz prvo rastao, zatim padao do a, a zatim ponovo rastao do indeksa b. To se kosi s početnom pretpostavkom da je niz prvo strogo rastući, a zatim strogo padajući iz čega zaključujemo da se u prvoj trećini sigurno ne nalazi traženi broj i odbacujemo ju iz daljnjeg razmatranja. Kada bi vrijedilo da je T[a] > T[b], tada bismo analognim zaključivanjem mogli odbaciti zadnji dio niza koji počinje s T[b].

Zašto nužno različiti brojevi?

Što se događa ako u funkciji (nizu) imamo dvije iste vrijednosti? Ako je T[a] = T[b], nećemo moći ništa zaključiti o poziciji traženog ekstrema, što najbolje prikazuju sljedeća tri niza:
1 2 5 5 5 7 2
1 2 5 6 5 3 2
1 7 5 5 5 3 2
U sva tri niza za vrijednosti indeksa a i b odabrali bismo a=2 i b=4, a usporedbom T[2] I T[4] ni u jednom nizu ne možemo sa sigurnošću zaključiti o poziciji ekstrema. Naravno, drukčijim odabirom indeksa „pogodili“ bismo različite elemente, ali općenito vrijedi da ternarnim pretraživanjem ne možemo ništa zaključiti kada su promatrani elementi niza jednaki, zbog čega slijedi nužan uvjet različitih elemenata.

Kao i kod binarnog pretraživanja, prava „snaga“ algoritma ne proizlazi iz osnovne primjene u kojoj pretražujemo zadani niz, nego iz velikog broja zadataka u kojima možemo ternarnim pretraživanjem pronaći najbolje rješenje, bez obzira na funkciju o kojoj se u pozadini radi.

Složenost

Sada nam preostaju samo dvije trećine početnog niza, na kojima ponavljamo identičan postupak i vrlo brzo dolazimo do traženog rješenja. Složenost ovog algoritma također je logaritamska, kao i kod binarnog pretraživanja, s jedinom razlikom da je baza logaritma u ovom slučaju 3/2, što ne utječe značajno na brzinu izvršavanja.
(dok binarno pretraživanje niza od 1 000 000 elemenata zahtijeva maksimalno 20 koraka, ternarno će pretraživanje na nizu iste veličine zahtijevati 35 koraka)

Pseudokod

Pseudokod najjednostvnijeg pretraživanja u nizu:

int l = 0, u = n - 1; // lower i upper
while( l < u ) { 
  int a = l + ( u - l ) / 3;
  int b = l + 2 * ( u - l ) / 3;

  // u ovom primjeru trazimo minimum, tj.
  // niz prvo strogo pada pa strogo raste
  if ( T[a] < T[b] ) 
    u = b - 1; // sigurni smo i da T[b] nije rjesenje
  else
    l = a + 1; // T[a] sigurno nije rjesenje
}

U slučaju da ne tražimo minimum niza, nego proizvoljne funkcije cijele varijable, gotovo se ništa ne mijenja, osim što ne provjeravamo odnos T[a] i T[b], nego f(a) i f(b)

Realne funkcije

Ako je funkcija čiji minimum tražimo prima realni parametar, tada je najjednostavnije while petlju zamijeniti for petljom koja će se izvršiti unaprijed zadani broj iteracija (npr. 100 ili 200). Naravno, zbog kontinuiranosti skupa realnih brojeva, granice ćemo sada mijenjati tako da će postati l = a ili u = b.

Trik za pretvorbu u binarno pretraživanje

Ako ternarno pretraživanje radimo na skupu cijelih brojeva, moguće je iskoristiti jednostavan trik kako bismo problem ternarnog pretraživanja pretvorili u binarno pretraživanje.

Primjetite da, u slučaju funkcije koja prvo raste pa pada, kod traženja maksimuma, mi zapravo tražimo onu točku gdje je f(x-1) < f(x) i f(x+1) < f(x).
Ako bismo u binarnom pretraživanju predikat P(x) zamislili kao P(x) := f(x) > f(x+1), tada bismo binarnim pretraživanjem zapravo trebali pronaći prvi takav x za koji je P(x) = 1, a to je problem koji znamo lako riješiti! :)

Važno je ipak uočiti da ovaj "trik" nije moguće iskoristiti kod funkcija na kontinuiranom skupu.

Zadaci

  1. U ravnini su zadane dužina D i točka T. Pronađi točku T' na dužini D koja je najbliža točki T
  2. Center of Mass
© 2012. Ivo Sluganović Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License