Алгоритми/"Подели, па владај"

Прва међу главним алгоритамским техникама коју ћемо покрити је подели и владај (divide et impera). Део вештине прављења доброг алгоритма подели и владај је одређивање како задати проблем може да буде подељен на два или више сличних, али мањих потпроблема. Генерално речено, када правимо алгоритам подели и владај, предузимамо следеће кораке:

Методологија подели и владај За дати проблем идентификовати мали број значајно мањих потпроблема истог типа. Решити сваки потпроблем рекурзијом (најмања могућа величина потпроблема је базни случај). Обједините добијена парцијална решења у решење главног проблема.

Први алгоритам који ћемо приказати коришћењем ове методологије је сортирање спајањем.

Сортирање спајањем

Проблем који сортирање спајањем решава је опште сортирање задатог неуређеног вектора елемената. Овај алгоритам као резултат даје вектор сортираних елемената. Тачније, за неки вектор a са индексом 1 до n, у случају да важи услов да

за свако i, j такво да је 1 ≤ i < j ≤ n онда a[i] ≤ a[j]

може рећи да је a сортиран. Овде је приказан интерфејс:

// sort -- враћа копију сортираног низа a
function sort(array a): array

Следећи методологију подели и владај, како сортирање a да поделимо на мање потпроблеме? Пошто је a вектор од n елемената, можда можемо започети дељењем вектора на два, величине n/2 елемената. Ови мањи вектори ће такође бити несортирани и има смисла да сваки сортирамо засебно; тако ћемо њих сматрати „сличним“. Занемарујући за сада базни случај, на овај начин сводимо проблем на други: како ћемо објединити два задата сортирана вектора у један сортирани вектор који садржи све њихове елементе:

// merge -- дато a и b (претпоставља се да су сортирани) враћа спојени низ који 
// одржава редослед
function merge(array a, array b): array

До сада смо следећи методологију дошли до овде, али шта је са базним случајем? Базни случај је део алгоритма који се односи на то шта се дешава када проблем не може више да се подели на мање потпроблеме. Овде је базни случај када вектор садржи само један елемент. Доле је приказан алгоритам за сортирање вектора који садржи 0 или 1 елемент:

// base-sort -- дат је низ од једног елемента (или празан), враћа копију 
// сортираног низа
function base-sort(array a[1..n]): array
  assert (n <= 1)
  return a.copy()
end

Састављајући приказане делове кода, добијамо до чега нас је до сада довела методологија:

// sort -- враћа копију сортираног низа a
function sort(array a[1..n]): array
  if n <= 1: return a.copy()
  else:
    let sub_size := n / 2
    let first_half := sort(a[1,..,sub_size])
    let second_half := sort(a[sub_size + 1,..,n])
    
    return merge(first_half, second_half)
  fi
end

И осим неимплементираног кода за потпрограм merge, овај алгоритам сортирања је готов! Пре него што покажемо како овај алгоритам ради, приказаћемо како може да буде написан merge:

// merge -- дато a и b (претпоставља се да су сортирани) враћа спојени низ који 
// одржава редослед
function merge(array a[1..n], array b[1..m]): array
  let result := new array[n + m]
  let i, j := 1
  
  for k := 1 to n + m:
    if i >= n: result[k] := b[j]; j += 1
    else-if j >= m: result[k] := a[i]; i += 1
    else:
      if a[i] < b[j]:
        result[k] := a[i]; i += 1
      else:
        result[k] := b[j]; j += 1
      fi
    fi
  repeat
end

Анализа

Нека је $T(n)$ број корака који је потребан алгоритму за величину улаза $n$. Спајање троши линеарно време и ми вршимо рекурзију сваки пут на два потпроблема двапут мање величине од изворног, тако да

$T(n)=2\cdot T\left({\frac {n}{2}}\right)+O(n).$

Према Главној теореми види се да ова рекурзија има уравнотежено стабло, тако да је време извршења:

$T(n)=O(n\cdot \log n).$

До овога се може доћи и интуитивно, запитајући се колико пута треба n поделити са 2, пре него што дужина вектора за сортрање постане једнака 1? Наравно, зашто m пута? 2^m = n , што је еквивалентно log 2^m = log n, и даље m x log₂2 = log ₂ n, и пошто је log₂ 2 = 1, следи да је m = log₂n.

Пошто је m број половљења вектора пре него што се он подели на под-векторе који садрже 1 елемент, биће потребно m нивоа спајања неког под-вектора са суседом, где ће сумарна дужина под-вектора бити n на сваком нивоу. Требаће да се изврши тачно n/2 поређења за спајање на сваком нивоу са m ( log₂n ) нивоа тако да важи да је: O(n/2 x log n ) <=> O ( n log n).

Итеративна верзија

Приказани алгоритам сортирања спајањем може да се претвори у итеративни, итеративним спајањем сваког следећег пара, затим група од четири итд. Итеративни алгоритам је у пракси бржи пошто нема допунске „трошкове“ великог броја позива функција. Ипак, пошто је стабло позива рекурзивне верзије алгоритма логаритамске дубине, он у току извршења не заузима много простора на стеку. За сортирање чак 4 гига елемената, потребно је само 32 записа за позиве на стеку, што је веома скроман захтев. Ако узмемо да је један запис величине чак 256 бајта, требаће нам само 8 килобајта простора на стеку. Итеративна верзија сеортирања спајањем представља мању модификацију рекурзивне верзије, а можемо да искористимо и постојећу функцију merge. Алгоритам ради тако што спаја мале, сортиране делове изворног вектора, и од њих прави веће сортиране делове. Да би ово постигли, итерирамо кроз вектор са сукцесивно све већим „корацима“.

// sort -- враћа сортирану копију низа a
function sort_iterative(array a[1..n]): array
   let result := a.copy()
   for power := 0 to log2(n-1)
     let unit := 2^power
     for i := 1 to n by unit*2
       if i+unit-1 < n: 
         let a1[1..unit] := result[i..i+unit-1]
         let a2[1..unit] := result[i+unit..min(i+unit*2-1, n)]
         result[i..i+unit*2-1] := merge(a1,a2)
       fi
     repeat
   repeat
   
   return result
end

Ово ради зато што је свака подлиста дужине 1 неког вектора, по дефиницији сортирана. Свака итерација кроз вектор (користећи бројач i) дуплира величину сортираних подлиста спајањем суседних подлиста у веће верзије. Тренутна величина сортираних подлиста алгоритма представља промењљива unit.

просторна неефикасност

Једноставно, сортирање спајањем захтева простор од 2 x n: n да запамти 2 два мања сортирана вектора и n да упише коначни резултат спајања. Али ово сортирање је и дање одговарајуће за груписања спајања.

Бинарно претраживање

Када је неки вектор сортиран, коришћењем бинарног претраживања брзо можемо да лоцирамо његове елементе. Бинарно претраживање је другачије од осталих алгоритама типа подели и владај, у томе што се углавном заснива на подели (није потребно ништа победити). Концепт на коме се базира бинарно претраживање, биће користан за разумевање алгоритама партиционисања и брзог сортирања приказаних у поглављу о рандомизацији. Налажење ставке у већ сортираном вектору је слично проналажењу имена у телефонском именику; можете почети отварајући књигу на средини. Ако је име које тражите на отвореној страници, заустављате се. Ако сте отишли предалеко, можете започети исти процес са првом половином књиге. Ако се име које тражите појављује касније у књизи, почињете процес са другом половином књиге. Исти процес понављате сужавајући сваки пут простор претраживања за пола, док не нађете оно што тражите (или док не нађете где би оно што тражите требало да се налази да постоји. Следећи алгоритам прецизно описује поменути поступак:

// binary-search -- враћа индекс вредности у датом низу или
// -1 ако вредност не може бити пронађена. Претпоставља се да је низ сортиран у растућем поретку
function binary-search(value, array A[1..n]): integer
  return search-inner(value, A, 1, n + 1)
end

// search-inner -- тражи делове низа; крај је један поред
// lпоследњег елемента 
function search-inner(value, array A, start, end): integer
  if start == end: 
     return -1                   // није пронађен
  fi

  let length := end - start
  if length == 1:
    if value == A[start]:
      return start
    else:
      return -1 
    fi
  fi
  
  let mid := start + (length / 2)
  if value == A[mid]:
    return mid
  else-if value > A[mid]:
    return search-inner(value, A, mid + 1, end)
  else:
    return search-inner(value, A, start, mid)
  fi
end

Приметите да се сви рекурзивни позиви појављују на крају функције (терминална, крајња рекурзија), тако да је алгоритам итеративан. Можемо експлицитно да уклонимо ове позиве, ако програмски језик то већ не уради за нас претварајући вредности аргумената прослеђених рекурзивним позивима у додељивање вредности, и затим поново скочимо на почетак тела функције:

// binary-search -- враћа индекс вредности у датом низу, или
// -1 ако вредност не може бити пронађена. Претпоставља се да је низ сортиран у растућем поретку
function binary-search(value, array A[1,..n]): integer
  let start := 1
  let end := n + 1
  
  loop:
    if start == end: return -1 fi                 // није пронађен
  
    let length := end - start
    if length == 1:
      if value == A[start]: return start
      else: return -1 fi
    fi
  
    let mid := start + (length / 2)
    if value == A[mid]:
      return mid
    else-if value > A[mid]:
      start := mid + 1
    else:
      end := mid
    fi
  repeat
end

Иако имамо један итеративни алгоритам, лакше је промишљати о рекурзивној верзији. Ако је број корака алгоритма $T(n)$, онда имамо следећу рекурентност (понављање) коју дефинише $T(n)$:

$T(n)=1\cdot T\left({\frac {n}{2}}\right)+O(1).$

Величина сваког рекурзивног позива зависи од половине величине улаза ($n$), а постоји и константна количина времена која се троши ван рекурзије (на пример за израчунавање length и mid ће се утрошити иста количина времена, без обзира на то колико елемената вектор садржи). Према Главној теореми ова рекурентност има вредности, што представља уравнотежено стабло, па је

$T(n)=\Theta (n^{k}\cdot \log n)=\Theta (\log n).$

Тако долаазимо до тога да овај алгоритам користи логаритамско време. Типично, чак и када је n велик, безбедно је да се допусти да стек расте за активационих записа за рекурзивне позиве.

Потешкоће у иницијално исправним имплементацијама бинарног претраживања

Чланак на Википедији о бинарном претраживању помиње потешкоће приликом писања исправног кода за овај алгоритам. На пример, имплементација преоптерећене Јава функције Arrays.binarySearch(..) врши итеративно бинарно претраживање које не ради када код целобројне промењљиве (large integer) долази до прекорачења у једноставном изразу за израчунавање mid, mid = ( end + start) / 2, т.ј. када је end + start > max_positive_integer. Стога је горњи алгоритам исправнији када користи да је length = end - start и дода половина length на start. Јава алгоритам за бинарно претраживање враћа резултат који је користан за налажење позиције најближег кључа који је већи од кључа по ком се претражује, т.ј. позиције на који кључ претраживања може да се уметне. То јест, враћа се (keypos+1) ако кључ претраживања није пронађен, али је потребна позиција за уметање кључа претраживања (insertion_point = -return_value – 1). Гледајући граничне вредности, позиција уметања може да се налази одмах на почетку листе (ip = 0, return value = -1) до позиције одмах иза последњег елемента (ip = length(A), return value = - length(A) - 1). Покушајте да имплементирате функционалност горњег итеративног алгоритма за бинарно претраживање као вежбу која ће бити корисна за боље разумевање изложеног.

Школско множење

Како да представимо велики цео број састављен из више речи? Можемо да имамо бинарни приказ користећи вектор речи (или додељени блок меморије) које представљају битове великог целог броја. Претпоставимо да имамо два цела броја, и и желимо да их помножимо. Ради једноставности, усвојићемо да су и и дужине битова (ако је неки од њих краћи, увек можемо да га попунимо нулама на почетку). Основни начин да се помноже цели бројеви је да се користи школски алгоритам монжења. Ово је још једноставније у бинарном систему јер множимо само са 1 или 0:

         x6 x5 x4 x3 x2 x1 x0
      &пута;  y6 y5 y4 y3 y2 y1 y0
      -----------------------
         x6 x5 x4 x3 x2 x1 x0 (када y0 је 1; 0 иначе)
      x6 x5 x4 x3 x2 x1 x0  0 (када y1 је 1; 0 иначе)
   x6 x5 x4 x3 x2 x1 x0  0  0 (када y2 је 1; 0 иначе)
x6 x5 x4 x3 x2 x1 x0  0  0  0 (када y3 је 1; 0 иначе)
  ... итд.

Овако би изгледало описано множење као алгоритам:

// multiply -- враћа производ два бинарна цела броја, који су дужине n
function multiply(bitarray x[1,..n], bitarray y[1,..n]): bitarray
  bitarray p = 0
  for i:=1 to n:
    if y[i] == 1:
      p := add(p, x)
    fi
    x := pad(x, 0)         // додаје се још једна нула на крај броја x
  repeat
  return p
end

Подрутина add сабира два бинарна цела броја и враћа резултатa, а подрутина pad поставља допунску цифру на крај броја (додавање нуле је исто што и шифтовање броја улево за једно место, што је истоветно његовом множењу са два). Овде пролазимо петљу n пута и у најгорем случају исто толико пута позивамо add. Бројеви који се прослеђују подрутини add биће, највише, дужине $2n$. Даље, можемо да очекујемо да подрутина add може да се изврши у линеарном времену. Следи, да ако се направи n позива подрутине $O(n)$, цео алгоритам ће утрошити $O(n^{2})$ времена.

Множење подели и владај

Као што можете да приметите, ово није крај приче. Приказали смо „очигледан“ алгоритам множења. Погледајмо да ли нам стратегија подели и владај пружа нешто више. Један правац који желимо да испитамо је да покушамо је да поделимо цео број на два дела. На пример цео број x може да се подели на два дела $x_{h}$ и $x_{l}$, који представљају половине вишег и нижег реда $x$. На пример ако if $x$ има n битова, имамо

$x=x_{h}\cdot 2^{n/2}+x_{l}$

Исто можемо да урадимо и за:

$y=y_{h}\cdot 2^{n/2}+y_{l}$

Али из ове поделе, није јасно како да помножимо делове на начин који омогућава да се добијени парцијални резултати обједине у коначан резултат решења проблема. Напишимо прво да би $x\times y$ требало да буде:

$x\times y=x_{h}\times y_{h}\cdot (2^{n/2})^{2}+(x_{h}\times y_{l}+x_{l}\times y_{h})\cdot (2^{n/2})+x_{l}\times y_{l}$

Ово потиче од простог множења нових hi/lo репрезентација за $x$ и $y$ . Множење мањих делова означено је симболом "$\times$". Приметимо да је множење са $2^{n/2}$ и $(2^{n/2})^{2}=2^{n}$ и да захтева право множење: уместо тога можемо само да број попунимо десно са одговарајућим бројем нула. Ово доводи до следећег алгоритма подели и владај:

// multiply -- враћа производ два бинарна цела броја, који су дужине n
function multiply(bitarray x[1,..n], bitarray y[1,..n]): bitarray
  if n == 1: return x[1] * y[1] fi          // помножити поједине цифре: O(1)
  
  let xh := x[n/2 + 1, .., n]               // сечење низа, O(n)
  let xl := x[0, .., n / 2]                 // сечење низа, O(n)
  let yh := y[n/2 + 1, .., n]               // сечење низа, O(n)
  let yl := y[0, .., n / 2]                 // сечење низа, O(n)
  
  let a := multiply(xh, yh)                 // рекурзивни позив; T(n/2)
  let b := multiply(xh, yl)                 // рекурзивни позив; T(n/2)
  let c := multiply(xl, yh)                 // рекурзивни позив; T(n/2)
  let d := multiply(xl, yl)                 // рекурзивни позив; T(n/2)
  
  b := add(b, c)                            // регуларно додавање; O(n)
  a := shift(a, n)                          // подлога нула; O(n)
  b := shift(b, n/2)                        // подлога нула; O(n)
  return add(a, b, d)                       // регуларно додавање; O(n)
end

Користићемо Главну теорему за анализу времена извршења алгоритма. Под претпоставком да је време извршења алгоритма $T(n)$, коментари показују колико времена троши сваки од корака. Пошто имамо четири рекурзивна позива, сваки са улазом величине $n/2$, имамо:

$T(n)=4T(n/2)+O(n)$

где су $a=4,b=2,k=1$ и знајући да је $4>2^{1}$ добијамо да се алгоритам налази у стаблу разгранатом при дну. За овај случај Главна теорема даје:

$T(n)=O(n^{\log _{2}4})=O(n^{2}).$

Дакле, после свог уложеног труда, још увек нисмо бољи од школског алгоритма! На срећу, бројеви и полиномијали представљају скуп података о коме имамо допунске информације. У ствари можемо смањити време извршења применом неких математичких трикова. Прво заменимо $2^{n/2}$ промењљивом z:

$x\times y=x_{h}*y_{h}z^{2}+(x_{h}*y_{l}+x_{l}*y_{h})z+x_{l}*y_{l}$

Добијамо квадратну једначину за коју знамо да су потребна само три коефицијента или тачке на графу да би се она једнозначно описала. Ипак, у горњем алгоритму користили смо укупно четири множења. Хајде да покушамо да преобликујемо $x$ и $y$ у линеарне функције:

$P_{x}(z)=x_{h}\cdot z+x_{l}$

$P_{y}(z)=y_{h}\cdot z+y_{l}$

Сада, за $x\times y$ треба само да израчунамо $(P_{x}\cdot P_{y})(2^{n/2})$. Проценићемо $P_{x}(z)$ и $P_{y}(z)$ на три тачке. Три погодне тачке за евалуацију функције биће на $(P_{x}\cdot P_{y})(1),(P_{x}\cdot P_{y})(0),(P_{x}\cdot P_{y})(-1)$.

Конверзија основе броја

Уз бинарни систем бројева, рачунарске науке користе и бројеве са основом 8 (октални систем) и 16 (хексадецимални систем). Веома је лако конвертовати бројеве из једног у други систем. Бројеви аписани октално и хексадецимално су значајно краћи у приказу од бинарних бројева. Да би приказали првих 8 бројева у бинарном систему потребна су нам 3 бита. Тако имамо 0=000, 1=001, 2=010, 3=011, 4=100, 5=101, 6=110, 7=111. Узмимо M=(2065)8. Да би добили бинарни приказ, заменићемо сваку од четири цифаре са одговарајућом тројком битова: 010 000 110 101. По уклањању водећих нула, бинарна представа је директна: M=(10000110101)₂. (Конверзија бројева хексадецималног система је слична, осим што се користи приказ од 4 бита за бројеве мање од 16.) Ова чињеница следи из општег алгоритма за конверзију и запажања да је 8=$2^{3}$ (и наравно 16=$2^{4}$ ). Изгледа да је најкраћи начин за конверзију бројева у бинарни систем, да се прво изврши конверзија у октални или хексадецимални систем. Погледајмо сада како се општи алгоритам за конверзију програмски имплементира. Ради референце, представљање броја у систему са основом (базом) N може да се састоји само од цифара мањих од N. Тачније, ако:

$(1)M=a_{k}N^{k}+a_{k-1}N^{k-1}+...+a_{1}N^{1}+a_{0}$

где је $0<=a_{i}<N$ имамо представљање броја М у систему са основом N и записујемо:

$M=(a_{k}a_{k-1}...a_{0})N$

Ако препишемо (1) као:

$(2)M=a_{0}+N*(a_{1}+N*(a_{2}+N*...))$

алгоритам за добијање коефицијената постаје очигледнији. На пример, $a_{0}=M\ modulo\ n$ и $a_{1}=(M/N)\ modulo\ n$ и тако даље.

Рекурзивна имплементација

Прикажимо алгоритам мнемонички: (резултат је низ симбола, у који једну по једну додајемо израчунате цифре).

result = "" 
if M < N, result = 'M' + result. Stop. 
S = M mod N, result = 'S' + result
M = M/N 
goto 2 

A few words of explanation.

Наколико речи објашњења. "" је празан низ. Можда се сетите да је то нулти елемент при конкатенацији низова. Овде ћемо проверити да ли процедура конверзије терминира. Она се зауставља када је M мање од N и у том случају је M цифра (или неки изабрани симбол за N>10) и нема потребе за допунским акцијама. Само је додајте испред осталих цифара које сте раније добили. Знак '+' означава конкатенацију. Ако M није мање од N, прво ћемо издвојити остатак дељења са N, додати добијену цифру резултату, као што је претходно описано, и доделити нову вредност М једнаку M/N. Цео процес треба да се понови почев од корака 2. Треба нам функција Conversion која има два аргумента M и N и која враћа приказ броја M у систему са основом N. Ова функција може да изгледа отприлике овако:

1 String Conversion(int M, int N) // враћа стринг, осим два цела броја
2 {  
3     if (M < N) // see if it's time to return 
4         return new String(""+M); // ""+M прави стринг као низ цифара
5     else // још увек није време за то
6         return Conversion(M/N, N) +
           new String(""+(M mod N)); // наставити
7 }  

Ово је практично радна верзија Јава функције и скоро исто би изгледала у C++, а за реализацију у језику C су потребне мање модификације. Као што се види у неком тренутку функција позива саму себе са другачијим првим аргументом. Може да се каже да је функција дефинисана у односу на саму себе. Такве функције се зову рекурзивне. (Најпознатија рекурзивна функција је факторијал: n!=n*(n-1)!.) Функција позива саму себе и примењује се са својим аргументима и затим се (природно) примењује са својим новим аргументима и онда ... и тако даље. Можемо да будемо сигурни да ће се процес на крају зауставити зато што низ аргумената (први аргумент) опада. Тако ће, пре или касније, први аргумент постати мањи од другог и процес ће корак по корак излазити из рекурзије.

Итеративна имплементација

Не дозвољавају сви језици рекурзивне позиве функција. Рекурзивне функције могу да буду непожељне у случају да се очекује прекид процеса из било ког разлога. На пример, код проблема Ханојске куле, корисник може да пожели да прекине демонстрацију зато што хоће да провери своје разумевање решења. Постоје компликације условљене начином на који рачунари извршавају програме, које се јављају када је потребно да се искочи из више нивоа рекурзивних позива одједном. Приметимо ипак да добијени низ који производи алгоритам конверзије има погрешан редослед: све цифре се прво рачунају и онда уписују у низ тако што је последња цифра прва. Рекурзивна имплементација са овим лако излази на крај. Са сваким позивом функције Conversion, рачунар прави ново окружење у којем се памте вредности које се предају M и N и новоизрачунато S. По окончању позива функције, т.ј. по повратку из функције, налазимо да је окружење исто као што је било и пре позива. Рекурзивне функције имплицитно памте секвенце обраде. Елиминисање рекурзивних позива подразумева да морамо израчунате цифре да сачувамо експлицитно и да их касније вратимо обрнутим редом. У рачунарској науци се овај механизам назива LIFO (Last In First Out) – последњи који је ушао, први излази. Овај механизам се најбоље имплементира помоћу структуре података типа стек. Стек има само две операције: push (стави на стек) and pop (извади са стека). Интуитивно, стек се може визуализовати како гомила објеката који су сложени један преко другог. Ако је потребан неки одређени објекат морају се прво уклонити сви објекти изнад њега. Очигледно је да је једини објекат који може одмах да се извади, онај који је на гомилу последњи стављен. Итеративна имплементација функције Conversion могла би да изгледа као што је приказано ниже.

 1 String Conversion(int M, int N) // враћа стринг, осим два цела броја 
 2 {  
 3     Stack stack = new Stack(); // креира стек
 4     while (M >= N) // јасно се види петља која се понавља
 5     {  
 6         stack.push(M mod N); // ускладишти цифру
 7         M = M/N; // find new M 
 8     }  
 9     // сада треба скупити све цифре заједно  
10     String str = new String(""+M); // креирати стринг са једном цифром M 
11     while (stack.NotEmpty())  
12         str = str+stack.pop() // узети са стека следећу цифру 
13     return str;  
14 }

Најближи пар тачака

Ако желите да из неког скупа тачака у равни нађете пар тачака које су најближе, треба да упоредите сваку тачку са сваком другом у времену $O(n^{2})$, или да употребите алгоритам подели и победи.

Увод

Приступ „грубом силом“ проблему најближег пара (т.ј. провера сваког могућег пара тачака) користи квадратно време. Желели би сада да представимо бржи „подели и владај“ алгоритам за решавање проблема најближег пара. За задати скуп тачака у равни S, наш приступ ће бити поделимо скуп на два приближно једнака дела (S1 и S2) за које већ имамо решење и онда да спојимо половине у линеарном времену да би добили један O(nlogn) алгоритам. Међутим, стварно решење је далеко од очигледног. Могуће је да тражени пар има једну тачку у S1, а другу у S2. Не присиљава ли нас ово да поново проверимо све могуће парове тачака? Приступ подели и владај, који је овде приказан, представља директну генерализацију једнодимензијалног алгоритма који је описан у претходном применом одељку.

Најближи пар у равни

У реду, генерализоваћемо наш једнодимензионални 1-D алгоритам колико год је могуће директније (погледај слику 3.2). Дати скуп тачака S у равни делимо на два скупа S1 и S2 вертикалном линијом l таквом да су тачке из S1 лево од l, а оне из S2 десно од l. Сада рекурзивно решавамо проблем над ова два скупа и добијамо минимална растојања d1 (за S1) и d2 (за S2). Допустићемо да је d њихов минимум. Сада, исто као и у случају 1-D, ако се најближи пар целог скупа састоји из по једне тачке из сваког подскупа, онда ове две тачке морају да буду у оквиру d од l. Ова зона је представљена са две траке P1 и P2 са обе стране од l. До сада смо били потпуно у корак са случајем 1-D. Сада, међутим, допунска димензија проузрокује проблеме. Желимо да утврдимо да ли је нека тачка, рецимо из P1, удаљена мање од d од друге тачке из P2. Међутим у равни ми немамо луксуз који смо имали на линији, када смо видели да само једна тачка у сваком скупу може да буде у оквиру d од средње линије. У ствари, у две димензије, све тачке могу да буду у траци! Ово је катастрофално, зато што ћемо морати да упоређујемо n2 парова тачака да би спојили скуп, и стога нам наш алгоритам подели и владај неће пружити већу ефикасност. Срећом, сада можемо да направимо још једну спасоносну опсервацију. За сваку поједину тачку p у једној траци, само тачке из друге траке које одговарају следећим ограничењима морају да се провере:

• оне тачке у оквиру d од p у правцу друге траке
• оне у оквиру d од p у правцу позитивне и негативне y осе.

Једноставно зато што тачке ван овог граничног оквира не могу бити мање d удаљене од p (види слику 3.3). Тако се дешава, да зато што је свака тачка у граничном оквиру најмање удаљена за d, у оквиру може да буде само шест тачака. Сада нема потребе да се проверава свих n2 тачака. Све што треба да урадимо је да сортирамо тачке из траке по њиховим y координатама и да редом скенирамо тачке проверавајући сваку тачку у односу на максимум 6 суседних. Ово значи да је највише 6*n поређења потребно да би се проверили парове кандидате. Међутим, пошто смо сортирали тачке из траке по њиховим y координатама, процес спајања наша два скупа није линеаран, већ узима O(nlogn) времена. Стога наш комплетан алгоритам још увек није O(nlogn), али је ипак побољшање у односу на квадратне перформансе приступа грубом силом (као што ћемо видети у следећем одељку). У одељку 3.4, показаћемо како да се овај алгоритам направи да буде још ефикаснији, поткрепљивањем нашег рекурзивног подрешења.

Кратак преглед и анализа 2-D алгоритама

Овде ћемо корак по корак, представити кратак преглед алгоритма приказаног у претходном одељку, а затим и анализу његових перформанси. Алгоритам је једноставно написан у облику листе, зато што сматрам да је псеудо-код оптерећујући и непотребан за разумевање алгоритма. Приметите да смо пре-сортирали тачке по њиховим x координатама и сачували посебну структуру која садржи тачке сортиране по вредностима y (за корак 4), које за себе узимају O(nlogn) времена. ClosestPair (најближи пар) скупа тачака:

1. Поделите скуп на два једнака дела линијом l и рекурзивно израчунајте минималну раздаљину у сваком делу.
2. Нека је d минимум два минимална растојања.
3. Елиминишите тачке које леже даље од d у односу на l.
4. Размотрите преостале тачке у односу на њихове y координате.
5. Скенирајте остале тачке уређене по y и израчунајте растојање сваке тачке у односу на суседне које су удаљене не више од d (зато нам је потребно да буду пре-сортиране по y). Приметите да нема више од таквих тачака (види претходни одељак).
6. Ако је било које од ових растојања мање од d, ажурирајте вредност d.

Анализа:

• Ефикасност алгоритма ћемо означити са T(n)
• Корак 1 узима 2T(n/2) (примењујемо алгоритам на обе половине)
• Корак 3 узима O(n) времена
• Корак 5 узима O(n) времена (као што смо видели у предходном одељку)

тако да је,

$T(n)=2T(n/2)+O(n)$

што према Главној теореми, резултира са:

$T(n)\in O(nlogn)$ Стога над спајањем под-решења доминира сортирање у кораку 4 и стога и зато узима O(nlogn) времена. Код алгоритма подели и владај, ово мора да се понови једанпут за сваки ниво рекурзије и стога цео алгоритам ClosestPair троши O(logn*nlogn) = O(nlog2n) времена.

Усавршавање алгоритма

Можемо мало да побољшамо алгоритам смањењем времна потребног за сортирање по y координати у кораку 4. То се ради тако што се тражи да рекурзивно решење у кораку 1 враћа тачке сортиране по њиховим y координатама. То ће дати две сортиране листе тачака које само треба спојити (линеарна временска функција) у кораку 4 да би се добила комплетна сортирана листа. Стога ревидирани алгорита укучује следеће измене: Корак 1: Step 1: Подели скуп на ..., и рекурзивно израчунај раздаљину у сваком од делова, враћајући тачке у скупу сортиране y координати. Корак 4: Спојити две сортиране листе у времену O(n). Као што се види процесом спајања сада доминирају кораци линеарног времена чиме се добија O(nlogn) алгоритам за налажење најближег пара из скупа тачака у равни.

Проблем Ханојских кула

Постоји n дискова различите величине и три клина. Дискови су постављени на леви клин редоследом који је одређен њиховом величином. Најмањи је на врху, док је највећи на дну. Циљ игре је да се сви дискови преместе са левог клина.

Правила

1) У савом кораку може да се премести само један диск 2) Само диск који је на врху може да се премешта. 3) Сваки диск може да се постави само на већи диск.

Решење

Интуитивна идеја Да би преместили највећи диск са левог клина на средњи, прво треба преместити мање дискове на десни клин. Пошто је највећи диск премештен, мањи дискови могу да се преместе са десног на средњи клин.

Рекурентност

Претпоставимо да је n број дискова. Да би преместили n дискова са клина а на клин b потребно је: 1) за n>1 треба премстити n-1 дискова са клина a на клин c 2) преместити n-и диск са клина а на клин b 3) за n>1 преместити n-1 дискова са клина c на клин a

Псеудокод

void hanoi(n,src,dst){
  if (n>1)
    hanoi(n-1,src,pegs-{src,dst});
  print "move n-th disc from src to dst";
  if (n>1)
    hanoi(n-1,pegs-{src,dst},dst);
}

Анализа

Анализа је тривијална. $T(n)=2T(n-1)+O(1)=O(2^{n})$

---