Разделяй и владей

Divide and Conquer

В темите до сега разгледахме няколко задачи за търсене и сортиране, в които итерирахме елементите на дадено множество. Не винаги се налагаше да итерираме всички елементи на множеството - например, в задачата за търсене на X в масив, понякога спирахме итерацията по-рано (ако намерим съвпадение). В много задачи ще ползваме това като оптимизация на алгоритъма ни - да не изброяваме всички елементи, когато това не е нужно.

Нещо повече, в тази тема ще покажем една хитра техника, която ни позволява да разглеждаме само тези от елементите на множеството, които са ни достатъчни за да изпълним поставената задача. Това понякога намаля броя разглеждани елементи в итерацията с огромен процент, като в резултат получаваме много по-бързи алгоритми.

Произход

Има няколко (що-годе) различни мита откъде произлиза израза "Разделяй и Владей", като може би най-близкият до идеята на алгоритмичната техника е следният. При разширяването на Римската империя, управниците (или генералите) са ползвали тактиката да разединят населението на дадена територия, преди да я нападнат. Чрез подкупи и фиктивни конфликти те са насъсквали местните племена едно срещу друго, като така са ги правили много по-слаб противник. В последствие Римляните са воювали само с отделни племена или части от разединеното население, като са печелили битките много по-лесно. Разделени, поданиците на империята не са могли да осъществят и големи бунтове, което е позволило да бъдат под римско владение векове наред.

Идея

Идеята на техниката "Разделяй и Владей" е същата - да разделим поставения ни проблем на по-малки такива, които можем да решим (завладеем) по-лесно, като в последствие обединим резултатите им и изградим отговор за целия проблем.

Разделяй

В процеса на разделяне ще гледаме да разбием задачата на по-малки, незастъпващи се подпроблеми, които можем да решим или тривиално (толкова са малки, че знаем отговора), или с допълнително раздробяване.

Защо по-малки?

Ако проблемите са по-малки, то най-вероятно ще са и по-лесни, като най-малките им варианти (базовите случаи) можем да сметнем и наум (или вече знаем отговора) и да хардкоднем в програмата си.

Защо незастъпващи се?

Ако подпроблемите се застъпват, то, най-вероятно, резултатът на единия ще зависи от резултата на другия. Това е нещо, което не можем да сметнем, и означава, че не сме разбили проблема като хората (ако той изобщо може да бъде разбит).

Дори ако резултатът на всеки от подпроблемите не зависи от резултата на никой от останалите такива, макар и да се застъпват, то е възможно застъпването да доведе до много повтаряща се работа, която изчисляваме отново и отново (правейки решението ни експоненциално -- тоест много бавно). Такива проблеми се решават с техниката динамично оптимиране.

Владей

Важно е след като сме изчислили резултатите на подпроблемите, да има начин, по който да ги съчетаем, за да получим отговора на проблема, който решаваме.
Както може би се досещате - да. Ще си разделят задачите на три (що-годе равни) части - 7, 7 и 6 задачи, като ще се нуждаят от, съответно, 35, 35, 30 минути за решаване на тяханата част, и 13, 13, 14 минути, за да препишат отговорите.
Всеки от тях първо решава всички поставени му задачи и после почва да преписва останалите (вече решени) задачи. Така ще са им нужни 48 минути за целия тест.

Тук частта "Разделяй" е това, че си поделят задачите помежду си (по-лесно се решават 7 задачи, отколкото 20), а "Владей" е това да препишат отговорите на задачите, които не са решили (но са решени от друг).
В тази (донякъде подобна) задача, номерът с разделяне на темите помежду им не работи. Макар и те да могат да направят това, като научават по 30 теми всеки (за което са им нужни 30 седмици), то тъй като задачите изискват знания от всички теми, то никой от тях не може да реши никоя от задачите (тоест наученото не може да бъде комбинирано). Точно това, че не можем да приложим стъпката "Владей", не разрешава тази задача да бъде решена с тази техника.

Примери

Техниката е приложима в наистина много ситуации. Ще разгледаме два примера, които илюстрират как тя може да влезе в истинска задача, където разделянето и владеенето не е изобщо толкова очевидно, колкото при горните хипотетични задачи.

Ханойски кули

Задачата за Ханойските Кули е много известна и със сигурност ще я срещнете и друг път (ако вече не сте). Съществува стратегия, която извършва местенето с доказан минимален брой ходове.
Всъщност, ако не сте срещали задачата преди я помислете :) Колко хода ви трябват за да преместите 5 диска?

?

Съществува яка легенда, свързана с Ханойските кули. Тя гласи, че в Индия има храм, в който има стая с три такива стълба и 64 златни диска, като монасите ги местят по правилата на гореописаната задача. Когато преместят и последния диск, светът ще свърши. Добрата новина е, че дори това да е вярно и те да ползват оптимална стратегия и местенето на един диск отнема само една секунда, то цялата задача ще им отнеме 585 милярда години.

Сега ще ви подскажем, че има решение, базирано на "Разделяй и Владей". Голяма подсказка, имайки предвид, че даваме задачата като пример в темата. Ако не сте измислили оптималното решение по-рано (отговорът за 5 е 31), то помислете как техниката може да бъде приложена тук.

Решението, всъщност, не е много трудно. Нека разгледаме по-общата задача, в която всички дискове са на някой от стълбовете (не задължително най-левия), който ще наричаме "начален". Искаме да ги преместим на някой друг (не задължително най-десния), който ще наричаме "краен". Третия стълб (който не е нито начален нито краен) ще наричаме "временен". Стратегията ни е да преместим горните N-1 диска на временния, после да преместим N-тия диск (който е останал сам на началния стълб) на крайния, след което да преместим N-1-те от временния на крайния стълб.

Тук "разделяме" дисковете на две части - в едната са горните N-1, а в другата - само най-големият. Самата задача бива разделена на три части (три етапа на "владеене"), но в две от тях местим еднаква група дискове.

Да преместим N-1 диска от началния стълб на временния (ползвайки крайния за временен) е по-малка задача от същия тип. И тъй като задачата с 1 диск е тривиална, то подобно свеждане на задача към по-малка подзадача е хубаво за нас (тъй като рано или късно ще стигнем до случай, който знаем как да решим). Преместването на най-големия диск (след като сме преместили по-малките) е тривиална задача. След това местим отново N-1 диска, като при първата част.

Ще приложим примерна имплементация на алгоритъма. На функцията подаваме четири числа - първото е N, тоест колко диска имаме да преместим, а останалите три са кой е началният стълб, кой е временният такъв и кой е крайният. За простота сме означили левия с нула, средния - с едно и десния - с две.

Тримино

Друга интересна задача, свързана с техниката, е задачата за триминота. Тук стъпката "разделяй" изисква малко креативност, но създава особено красиво решение. Първо помислете сами малко.

Хайде де, още малко, нали целта е вие да се научите да измисляте хитри неща.

Така. Ако сте успели да го измислите, можете да се чувствате много горди от себе си. Ако не сте, ето и решението. Ако дъската е 1 на 1, очевидно има решение (без нито едно тримино). Ако дъската е 2 на 2, то също очевидно има решение. Нека разгледаме случая, в който дъската е 4 на 4. Намерихме решение на три от възможните начални разположения. След известно наблюдение се забелязва, че всяка дъска с размер 4 на 4 има решение чрез ротация и/или симетрия на някоя от горните три дъски. Бихме могли да предположим, че всяка дъска със страна 2^N има решение. Сега да намерим стратегия и как да намираме самите решения.

Нека разделим началната дъска на 4 равни части (два разреза: един през средата по X и един през средата по Y). В една от тях е първоначалното черно квадратче, a останалите 3 са изцяло бели. Но ако сложим едно тримино в центъра (там, където двата разреза се пресичат) така, че липсващата му плочка да застъпва частта, която съдържа началната черна плочка, то вече всяка от четирите части е с размер 2^N-1 и има по една черна плочка. Но това е същата задача с по-малък размер! Следователно можем да решим рекурсивно със същия алгоритъм всяка от четирите подзадачи и да "съединим" решенията, получавайки решение и за големия квадрат. Дъното на рекурсията може да бъде дъска с размер 1 или 2, което предпочетем. Нека видим как би изглеждало първото разрязване на дъска с размер 8 на 8: Яко, нали? Ако искате да напишете цяло решение на задачата, може да се пробвате да направите това в задачата Gamers.

Задачи

Съществуват много алгоритми и техники, базирани на техниката "Разделяй и Владей". Примери за известни такива са: двоично търсене, merge sort, бързо вдигане на степен, бързо умножение на матрици, бързо умножение на дълги числа, алгоритъм на Евклид, и други.

В процеса на изучаване на следващите теми ще се сблъскате с много задачи, чиято идея е базирана на "Разделяй и Владей". Най-често те ще се решават с двоично търсене, но съществуват и по-сложни (и интересни) проблеми, които са податливи на тази техника.

Една още по-хитра от горните задачи, която може да се реши така, е задачата Eavesdropping от втория кръг на НОИ през 2011 година.

Малко по-сложна задача, която може да се реши така, е Monopoly. За нея има и алтернативно решение със стек, но се опитайте да измислите как може да стане с Разделяй и Владей (което е предпоследното описано в анализа на задачата).

Допълнителни материали

• Divide & Conquer (en.wikipedia.org)
• Divide-and-Conquer algorithms (cs.berkeley.edu)

предишна тема

версия за печат

следваща тема