Подели па владај (информатика)

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

Ова стратегија је основа ефикасних алгоритама за решавање разноликих проблема, као што је проблем сортирања (нпр. Алгоритам брзог сортирања, Алгоритам сортирања обједињавањем, проблем множења великих бројева (нпр. Карацубин алоритам), проблем проналажења две најближе тачке, синтаксна анализа (нпр. анализа наниже и израчунавање дискретне Фуријеове трансформације.

Схватање и дизајн алгоритама заснованих на овој стратегији је сложена вештина која захтева добро разумевање природе проблема који треба да се реши, као што при доказивању теореме математичком индукцијом почетни проблем треба заменити општијим или компликованијим проблемом, како би се кренуло у рекурзивно решавање, при чему не постоји општи метод за проналажење праве генерализације. Овакве компликације се изражавају при оптимизацији израчунавања Фибоначијевог броја ефикасном двоструком рекурзијом.

Исправност алгоритама заснованих на разлагању се обично доказује математичком индукцијом, а сложеност израчунавања се одређује решавањем рекурентних једначина.

Поједностави па владај

Назив подели па владај се понекад користи и за алгоритме који смањују почетни проблем на само један подпроблем, као код алгоритма бинарне претраге за проналажење вредности у повезаној листи или нумеричком израчунавању алгоритмом бисекције за проналажење корена^[1]. Овакви алгоритми се могу имплементирати ефикасније другим стратегијама, на пример ако је у питању репна рекурзија, она се може заменити једноставним петљама. По дефиницији, у ширем смислу, сваки алгоритам који је заснован на петљама и рекурзији се може сматрати Подели па владај алгоритмом, стога неки аутори сматрају да овај назив треба користити само када се почетни проблем разлаже на два или више подпроблема^[2]. Назив који они предлажу за алгоритме који почетни проблем разлажу на само један подпроблем је Поједностави па владај^[3].

Важна примена поједностави па владај алгоритама је оптимизација, где ако се простор претраге смањује за константан фактор у сваком кораку, целокупан алгоритам има исту асимптотску сложеност као и корак одсецања, при чему константа зависи од фактора одсецања (од суме геометријског реда). На овај начин се добија алгоритам који се назива Претрага одсецањем (ен. prune and search).

Пример: Максимална вредност низа

Нека је дат низ a = {2, 3, -2, 5, 12, 15, 100, 22, -5}, у којем треба пронаћи максималну вредност. Рекурзивно решење по овом принципу би гласило:

Претпозив:
0. Позови алгоритам max за низ a, у границама од првог до последњег елемента (означавамо их, редом, са l и r).

Алгоритам:
1. Уколико је l > r, завршило се са претрагом низа или је низ био празан.
   Врати најмању могућу вредност.
2. Уколико је l = r, то значи да више нема елемената за
   поређење. Резултат је a[l], односно a[r].
3. Уколико је разлика између l и r само 1, упоредити a[l] и a[r]
   и вратити већи од њих.

4. У осталим случајевима израчунати p = (l+r)/2 и позвати овај исти
   алгоритам два пута:
      1. За низ a у границама од l до p
      2. За низ a у границама од p+1 до r

   Резултате оба позива упоредити и вратити већи број.

Поједностављење, које се постиже овим алгоритмом, је да се увек пореде два елемента или врати само један преостали број; тј. када низ има дужину већу од 2, у једном позиву алгоритма се не пореде сви елементи. Следи шематски приказ на коме се може видети на који начин алгоритам дели и обрађује низ:

Легенда:

- Прослеђене границе (под)низова

- Враћени максимуми (под)низова

- Нумерација поднизова

Треба приметити да се обрада поднизова I и VI може паралелизовати, јер би се радило о позивима истог алгоритма над два подниза. Ови позиви не морају да знају ништа о другим позивима, већ само да позиву у коме су позвани врате своје резултате које ће он обрадити.

Под условом да се сви потребни позиви могу паралелизовати, сложеност оваквог алгоритма је одређена висином нацртаног графа. Конкретно, пошто се низ стално дели на два дела, сложеност овог алгоритма при обради низа од n елемената ће бити O(log₂n), што је мање од O(n), колико би износила сложеност линеарне претраге.

Рани историјски примери

Рани примери оваквих алгоритама су првенствено Поједностави па владај, односно базни проблем који се сукцесивно разлаже на један подпроблем се заиста може решити итеративно.

Алгоритам бинарне претраге, односно поједностави па владај алгоритам у коме је величина подпроблема половина почетног има дугу историју. Иако се целокупан опис алгоритма појавио 1946. године у чланку Џона Моучлија, идеја употребе сортиране листе предмета ради олакшавања претраге датира још из Вавилона, око 200. године п.н.е.^[4]. Еуклидов алгоритам који је описан око 300. године п.н.е. је још један пример старих поједностави па владај алгоритама.

Рани пример подели па владај алгоритама са већим бројем подпроблема је Гаусов опис из 1805. године, који је данас познат као алгоритам Коли-Тукејеве брзе Фуријеове трансформације^[5]. Како Гаус није анализирао број операција потребних за његово извршавање, овај алгоритам није постао широко распрострањен све до његовог поновног открића, више од једног века касније.

Други пример је алгоритам сортирања обједињавањем, који почетни проблем дели на два подпроблема. Овај подели па владај алгоритам је развио Џон фон Нојман 1945. године^[6].

Још један значајан пример је алгоритам Анатолија Карацубе из 1960. године^[7] којим би се два n-тоцифрена броја могла помножити у $O(n^{\log _{2}3})$ операција (изражено у велико О нотацији). Овај алоритам је оповргао Андреј Колмогоров 1956. године хипотезом да би било потребно $\Omega {(n^{2})}$ операција за извршавање алгоритма.

Као још један пример подели па владај алгоритама, који није изворно развијен за рачунаре, је Кнутов метод који пошта обично користи за усмеравање пошиљки: писма се сортирају у различите џакове за различита географска подручја, а затим се садржај сваког џака сортира у пакете за мања подручја и слично, све док не буду испоручена^[4]. Овај метод је повезан и са радикс сортирањем, описаним за сортирање бушених картица још 1929. године^[4].

Предности

Решавање тешких проблема

Стратегија подели па владај је посебно погодна за решавање концептуално тешких проблема: све што је потребно је да се пронађе начин да се полазни проблем подели на подпроблеме, као и да се реше тривијални случајеви и искомбинују решења подпроблема. Слично, стратегија поједностави па владај захтева једино да се проблем поједностави, чиме се добија "мањи" проблем. Класичан пример је проблем кула Ханоја у коме се почетни број, односно n, дискова своди на подпроблем величине n-1.

Ефикасност алгоритама

Парадигма подели па владај често води откривању ефикасних алгоритама. Неки проблеми за које је ова парадигма била кључна су Карацубин метод брзог множења бројева, алгоритми брзог сортирања и сортирања обједињавањем, Штрасенов алгоритам за множење матрица, као и брзе Фуријеове трансформације.

У овим примерима, приступ подели па владај је довео до побољшања асимптотске сложености решења. На пример, ако је величина базних случајева константна, подела проблема и комбиновање парцијалних проблема је пропорционална величини полазног проблема n, и ако постоји p потпроблема приближне величине n/p у сваком кораку, тада је асимптотска сложеност подли па владај алгоритма $O(n\log _{p}{n})$ .

Паралелизам

Алгоритми засновани на стратегији подели па владај су природно погодни за извршавање на вишепроцесорским машинама, поготово на системима са дељеном меморијом, где ток података између више процесора не мора да буде унапред испланиран јер засебни подпроблеми могу да се извршавају на различитим процесорима.

Приступ меморији

Подели па владај алгоритми природно ефикасно употребљавају кеш меморију јер када је подпроблем довољно мали, он и сви његови подпроблеми могу, у принципу, да буду решени у оквиру кеша, без потребе за приступом споријој главној меморији. Алгоритам који је дизајниран тако да кеш меморију користи на овако описан начин се назива алгоритам који није свестан кеш меморије, због тога што не садржи експлицитно величину (или величине) кеша као параметар.^[8] Штавише, ова стратегија се може употребити за конструкцију важних алгоритама (нпр. сортирање, брзе Фуријеове трансформације, множење матрица) тако да користи кеш меморију на оптималан начин, у асимптотском смислу, без обзира на њену величину, за разлику од традиционалног приступа који блокира кеш. Пример блокирања кеш меморије би била оптимизација угњеждености петље, где се полазни проблем експлицитно дели на "парчиће" одговарајуће величине. Ипак, треба напоменути да и поред тога, кеш може бити оптимално искоришћен, али само у случају да је алгоритам конструисан за специфичну величину кеша конкретне машине на којој се извршава алгоритам.

Поред кеш меморије, исте погодности постоје и за остале врсте меморије (хијерархијски), као што су виртуелна меморија, али и различити нивои кеш меморије (када је подпроблем довољно мали), у датом нивоу хијерархије без приступа вишим (и споријим) нивоима.

Контрола заокруживања

При израчунавању са "заокруживом" аритметиком, нпр. са бројевима у покретном зарезу, подели па владај алгоритам може дати тачније резултате од површних еквивалентних итеративних метода. На пример, N бројева се могу сабрати помоћу једноставне петље која додаје сваки број на текућу суму, или помоћу подели па владај алгоритма суме парова који дели скуп вредности на две половине, рекурзивно израчунава суму за обе половине, после чега сабира те две вредности и тако даје коначан резултат. Иако други метод извршава исти број операција сабирања као и први, при чему постоји и цена рекурзивних позива, он је обично тачнији.^[9]

Проблеми са имплементацијом

Рекурзија

Подели па владај алгоритми се природно импелентирају рекурзивно. У том случају, парцијални подпроблеми који воде до решења почетног проблема, се аутоматски смештају на стек позива. Рекурзивна функција је заправо она функција која позива саму себе у оквиру своје дефиниције.

Експлицитан стек

Подели па владај алгоритми се такође могу имплементирати нерекурзивно, као програм који складишти парцијалне подпроблеме у неку структуру података као што су: стек, ред, или ред са приоритетом. Овакав приступ даје више слободе у избору подпроблема који треба да буде решен следећи, што је важна особина у неким применама, нпр. код претраге графа у ширину или метода сепарације и евалуације за оптимизацију. Овај приступ је такође стандардно решење програмских језика који не подржавају рекурзивне процедуре.

Величина стека

У рекурзивној имплементацији подели па владај алгоритама, треба водити рачуна да постоји довољно алоциране меморије за стек рекурзивних позива, у супротном извршавање алгоритма може да закаже због прекорачења капацитета стека. На сву срећу, подели па владај алгоритми који су временски ефикасни често немају велики број рекурзивних позива. На пример, алгоритам брзог сортирања се може имплементирати тако да никада не захтева више од $\log _{2}{n}$ угњеждених рекурзивних позива за сортирање n чланова низа.

Прекорачење капацитета стека може бити тешко за избегавање при коришћењу рекурзивних процедура, пошто многи компилатори претпостављају да рекурзивни стек заузима неки меморијски простор који се лако може проширити, а многи други алоцирају фиксан меморијски простор за стек. Компилатори, такође, могу имати више информација у стеку него што је заиста потребно, као што су адреса повратка из текућег позива, параметри који се не мењају у току позива, или локалне променљиве процедуре. Одатле следи да се ризик од прекорачења капацитета се може смањити коришћењем мањег броја параметара и локалних променљивих у оквиру рекурзивне процедуре, и/или коришћењем неке од структура података описаних раније.

Избор базних случајева

У оквиру било ког рекурзивног алгоритма, постоји одређена слобода у избору базних случајева, мањих подпроблема који се директно решавају да би се изашло из рекурзивног позива.

Избор мањих или једноставнијих могућих базних случајева је елегантнији и обично води до једноставнијих програма, јер постоји мање случајева које треба размотрити и који су лакши за решавање. На пример, алгоритам брзе Фуријеове трансформације може зауставити рекурзију када улаз представља један узорак, а алгоритам брзог сортирања се може зауставити када на улазу нема више елемената. У оба примера постоји само један базни случај за разматрање, и он не захтева даљу обраду.

Са друге стране, ефикасност се често побољшава уколико се рекурзија заустави са релативно великим базним случајевима, који се решавају нерекурзивно, чиме се добија хибридни алгоритам. Коришћењем ове стратегије избегавају се рекурзивни позиви који обављају мало или не обављају нимало посла, допушта се употреба специјализованих нерекурзивних алгоритама, који су за те базне случајеве ефикаснији од класичне рекурзије. Уобичајна процедура за једноставни хибридно рекурзивни алгоритам је кратко спајање базног случаја (arm's-length рекурзија). У овом случају, провера да ли ће следећи корак представљати базни случај за следећи рекурзивни позив се извршава пре позива функције, чиме се избегава непотребан позив. На пример, у стаблу, пре уласка у нови рекурзивни позив за следећи чвор треба проверити да ли за тренутни чвор уопште постоји следећи, уместо провере тек након уласка у нови позив, чиме се избегава половина рекурзивних позива код неких алгоритама за бинарна стабла. Како подели па владај алгоритам на крају редукује сваки проблем или подпроблем на велики број нових базних инстанци, које доста утичу на укупну цену алгоритма, нарочито када постоји мали број спајања/раздвајања у претходном позиву. Важно је узети у обзир да ова разматрања не зависе од тога да ли рекурзију имплементира компилатор или је имплементирана експлицитним коришћењем стека.

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

Алтернативно, могу се направити велики базни случајеви који би још увек користили подели па владај алгоритам, али би имплементирали алгоритам за пре-одређивање скупа фиксних величина за које би рекурзивни алгоритам прешао у нерекурзивни, алгоритам без петље, или у алгоритам без услова. На пример, овај приступ се користи у неким ефикасним имплементацијама брзих Фуријеових трансформација, у којима базни случајеви представљају развијене имплементације подели па владај алгоритама брзих Фуријеових трансформација за скуп фиксне величине.^[10] Методе за генерисање кода се могу користити за проналажење великог броја различитих базних случајева, које су пожељне за ефикасну имплементацију ове стратегије.^[10]

Генерализована верзија ове идеје је позната као "развијање" рекурзије и различите технике су предложене за аутоматизацију процедуре укрупњавања базног случаја.^[11]

Понављање подпроблема

За неке проблеме, у оквиру рекурзивног гранања, неки подпроблеми се могу израчунавати и по неколико пута. У таквим случајевима, може бити корисно одредити и сачувати решења ових преклапајућих подпроблема. Ова техника је позната као меморизација, и њеним дословним праћењем се долази до bottom-up подели па владај алгоритама, као што је случај код динамичког програмирања.

Види још

Референце

^ Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).
^ Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
^ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).
^ ^а ^б ^в Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).
^ Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform," IEEE ASSP Magazine, 1, (4), 14–21 (1984).
^ Knuth, Donald (1998). The Art of Computer Programming: Volume 3 Sorting and Searching. p. 159.
^ Karatsuba, Anatolii A.; Yuri P. Ofman (1962). "Умножение многозначных чисел на автоматах". Doklady Akademii Nauk SSSR 146: 293–294. Translated in Physics-Doklady 7: 595–596. 1963.
^ M. Frigo; C. E. Leiserson; H. Prokop (1999). "Cache-oblivious algorithms". Proc. 40th Symp. on the Foundations of Computer Science.
^ Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).
^ ^а ^б Frigo, M.; Johnson, S. G. (February 2005). "The design and implementation of FFTW3". Proceedings of the IEEE 93 (2): 216–231.
^ Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs," in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).

[1] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).

[2] Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.

[3] Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

[automatski_generisano1-4] а ^б ^в Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).

[5] Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform," IEEE ASSP Magazine, 1, (4), 14–21 (1984).

[6] Knuth, Donald (1998). The Art of Computer Programming: Volume 3 Sorting and Searching. p. 159.

[7] Karatsuba, Anatolii A.; Yuri P. Ofman (1962). "Умножение многозначных чисел на автоматах". Doklady Akademii Nauk SSSR 146: 293–294. Translated in Physics-Doklady 7: 595–596. 1963.

[8] M. Frigo; C. E. Leiserson; H. Prokop (1999). "Cache-oblivious algorithms". Proc. 40th Symp. on the Foundations of Computer Science.

[9] Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).

[automatski_generisano2-10] а ^б Frigo, M.; Johnson, S. G. (February 2005). "The design and implementation of FFTW3". Proceedings of the IEEE 93 (2): 216–231.

[11] Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs," in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]