У информатици, подели па владај је стратегија дизајнирања алгоритама заснована на рекурзији са вишеструким гранањем. Овакви алгоритми се заснивају на рекурзивном разлагању проблема на два или више подпроблема истог (или сличног) типа (подели), све док проблем не постане довољно једноставан да се може директно решити (владај). Решења тих подпроблема се након тога сједињавају и дају решење полазног проблема.
Ова стратегија је основа ефикасних алгоритама за решавање разноликих проблема, као што је проблем сортирања (нпр. Алгоритам брзог сортирања, Алгоритам сортирања обједињавањем, проблем множења великих бројева (нпр. Карацубин алоритам), проблем проналажења две најближе тачке, синтаксна анализа (нпр. анализа наниже и израчунавање дискретне Фуријеове трансформације.
Схватање и дизајн алгоритама заснованих на овој стратегији је сложена вештина која захтева добро разумевање природе проблема који треба да се реши, као што при доказивању теореме математичком индукцијом почетни проблем треба заменити општијим или компликованијим проблемом, како би се кренуло у рекурзивно решавање, при чему не постоји општи метод за проналажење праве генерализације. Овакве компликације се изражавају при оптимизацији израчунавања Фибоначијевог броја ефикасном двоструком рекурзијом.
Исправност алгоритама заснованих на разлагању се обично доказује математичком индукцијом, а сложеност израчунавања се одређује решавањем рекурентних једначина.
Поједностави па владај
Назив подели па владај се понекад користи и за алгоритме који смањују почетни проблем на само један подпроблем, као код алгоритма бинарне претраге за проналажење вредности у повезаној листи или нумеричком израчунавању алгоритмом бисекције за проналажење корена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)..
Важна примена поједностави па владај алгоритама је оптимизација, где ако се простор претраге смањује за константан фактор у сваком кораку, целокупан алгоритам има исту асимптотску сложеност као и корак одсецања, при чему константа зависи од фактора одсецања (од суме геометријског реда). На овај начин се добија алгоритам који се назива Претрага одсецањем (ен. 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, у једном позиву алгоритма се не пореде сви елементи. Следи шематски приказ на коме се може видети на који начин алгоритам дели и обрађује низ:
600пЛегенда:
- Прослеђене границе (под)низова
- Враћени максимуми (под)низова
- Нумерација поднизова
Треба приметити да се обрада поднизова -{I}- и -{VI}- може паралелизовати, јер би се радило о позивима истог алгоритма над два подниза. Ови позиви не морају да знају ништа о другим позивима, већ само да позиву у коме су позвани врате своје резултате које ће он обрадити.
Под условом да се сви потребни позиви могу паралелизовати, сложеност оваквог алгоритма је одређена висином нацртаног графа. Конкретно, пошто се низ стално дели на два дела, сложеност овог алгоритма при обради низа од -{n}- елемената ће бити -{O(log2n)}-, што је мање од -{O(n)}-, колико би износила сложеност линеарне претраге.
Рани историјски примери
Рани примери оваквих алгоритама су првенствено Поједностави па владај, односно базни проблем који се сукцесивно разлаже на један подпроблем се заиста може решити итеративно.
Алгоритам бинарне претраге, односно поједностави па владај алгоритам у коме је величина подпроблема половина почетног има дугу историју. Иако се целокупан опис алгоритма појавио 1946. године у чланку Џона Моучлија, идеја употребе сортиране листе предмета ради олакшавања претраге датира још из Вавилона, око 200. године п.н.е.Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).. Еуклидов алгоритам који је описан око 300. године п.н.е. је још један пример старих поједностави па владај алгоритама.
Рани пример подели па владај алгоритама са већим бројем подпроблема је Гаусов опис из 1805. године, који је данас познат као алгоритам Коли-Тукејеве брзе Фуријеове трансформације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).. Како Гаус није анализирао број операција потребних за његово извршавање, овај алгоритам није постао широко распрострањен све до његовог поновног открића, више од једног века касније.
Други пример је алгоритам сортирања обједињавањем, који почетни проблем дели на два подпроблема. Овај подели па владај алгоритам је развио Џон фон Нојман 1945. годинеKnuth, Donald (1998). The Art of Computer Programming: Volume 3 Sorting and Searching. p. 159..
Још један значајан пример је алгоритам Анатолија Карацубе из 1960. године Karatsuba, Anatolii A.; Yuri P. Ofman (1962). "Умножение многозначных чисел на автоматах". Doklady Akademii Nauk SSSR 146: 293–294. Translated in Physics-Doklady 7: 595–596. 1963. којим би се два n-тоцифрена броја могла помножити у операција (изражено у велико О нотацији). Овај алоритам је оповргао Андреј Колмогоров 1956. године хипотезом да би било потребно операција за извршавање алгоритма.
Као још један пример подели па владај алгоритама, који није изворно развијен за рачунаре, је Кнутов метод који пошта обично користи за усмеравање пошиљки: писма се сортирају у различите џакове за различита географска подручја, а затим се садржај сваког џака сортира у пакете за мања подручја и слично, све док не буду испоручена. Овај метод је повезан и са радикс сортирањем, описаним за сортирање бушених картица још 1929. године.
Предности
Решавање тешких проблема
Стратегија подели па владај је посебно погодна за решавање концептуално тешких проблема: све што је потребно је да се пронађе начин да се полазни проблем подели на подпроблеме, као и да се реше тривијални случајеви и искомбинују решења подпроблема. Слично, стратегија поједностави па владај захтева једино да се проблем поједностави, чиме се добија "мањи" проблем. Класичан пример је проблем кула Ханоја у коме се почетни број, односно n, дискова своди на подпроблем величине n-1.
Ефикасност алгоритама
Парадигма подели па владај често води откривању ефикасних алгоритама. Неки проблеми за које је ова парадигма била кључна су Карацубин метод брзог множења бројева, алгоритми брзог сортирања и сортирања обједињавањем, Штрасенов алгоритам за множење матрица, као и брзе Фуријеове трансформације.
У овим примерима, приступ подели па владај је довео до побољшања асимптотске сложености решења. На пример, ако је величина базних случајева константна, подела проблема и комбиновање парцијалних проблема је пропорционална величини полазног проблема n, и ако постоји p потпроблема приближне величине n/p у сваком кораку, тада је асимптотска сложеност подли па владај алгоритма .
Паралелизам
Алгоритми засновани на стратегији подели па владај су природно погодни за извршавање на вишепроцесорским машинама, поготово на системима са дељеном меморијом, где ток података између више процесора не мора да буде унапред испланиран јер засебни подпроблеми могу да се извршавају на различитим процесорима.
Приступ меморији
Подели па владај алгоритми природно ефикасно употребљавају кеш меморију јер када је подпроблем довољно мали, он и сви његови подпроблеми могу, у принципу, да буду решени у оквиру кеша, без потребе за приступом споријој главној меморији. Алгоритам који је дизајниран тако да кеш меморију користи на овако описан начин се назива алгоритам који није свестан кеш меморије, због тога што не садржи експлицитно величину (или величине) кеша као параметар.M. Frigo; C. E. Leiserson; H. Prokop (1999). "Cache-oblivious algorithms". Proc. 40th Symp. on the Foundations of Computer Science. Штавише, ова стратегија се може употребити за конструкцију важних алгоритама (нпр. сортирање, брзе Фуријеове трансформације, множење матрица) тако да користи кеш меморију на оптималан начин, у асимптотском смислу, без обзира на њену величину, за разлику од традиционалног приступа који блокира кеш. Пример блокирања кеш меморије би била оптимизација угњеждености петље, где се полазни проблем експлицитно дели на "парчиће" одговарајуће величине. Ипак, треба напоменути да и поред тога, кеш може бити оптимално искоришћен, али само у случају да је алгоритам конструисан за специфичну величину кеша конкретне машине на којој се извршава алгоритам.
Поред кеш меморије, исте погодности постоје и за остале врсте меморије (хијерархијски), као што су виртуелна меморија, али и различити нивои кеш меморије (када је подпроблем довољно мали), у датом нивоу хијерархије без приступа вишим (и споријим) нивоима.
Контрола заокруживања
При израчунавању са "заокруживом" аритметиком, нпр. са бројевима у покретном зарезу, подели па владај алгоритам може дати тачније резултате од површних еквивалентних итеративних метода. На пример, N бројева се могу сабрати помоћу једноставне петље која додаје сваки број на текућу суму, или помоћу подели па владај алгоритма суме парова који дели скуп вредности на две половине, рекурзивно израчунава суму за обе половине, после чега сабира те две вредности и тако даје коначан резултат. Иако други метод извршава исти број операција сабирања као и први, при чему постоји и цена рекурзивних позива, он је обично тачнији.Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).
Проблеми са имплементацијом
Рекурзија
Подели па владај алгоритми се природно импелентирају рекурзивно. У том случају, парцијални подпроблеми који воде до решења почетног проблема, се аутоматски смештају на стек позива. Рекурзивна функција је заправо она функција која позива саму себе у оквиру своје дефиниције.
Експлицитан стек
Подели па владај алгоритми се такође могу имплементирати нерекурзивно, као програм који складишти парцијалне подпроблеме у неку структуру података као што су: стек, ред, или ред са приоритетом. Овакав приступ даје више слободе у избору подпроблема који треба да буде решен следећи, што је важна особина у неким применама, нпр. код претраге графа у ширину или метода сепарације и евалуације за оптимизацију. Овај приступ је такође стандардно решење програмских језика који не подржавају рекурзивне процедуре.