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

Divide and Conquer

Произход и идея на техниката. Части.
Сложност на алгоритми, базирани на "Разделяй и Владей".
Автор: Александър Георгиев

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

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

Произход

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

Идея

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

Разделяй

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

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

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

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

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

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

Владей

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

Тук частта "Разделяй" е това, че си поделят задачите помежду си (по-лесно се решават 7 задачи, отколкото 20), а "Владей" е това да препишат отговорите на задачите, които не са решили (но са решени от друг).
След доброто си представяне на теста по математика, Ели, Крис и Станчо решиха да станат състезатели по информатика. Сайтът, където се подготвят, съдържа 90 теми, като всяка от темите отнема по, приблизително, една седмица за да бъде научена. До важното състезание, за което се подготвят, остава точно една година (52 седмици), като на него има много сложни задачи, изискващи теория и/или трикове от всяка една от темите. Могат ли да се подготвят те?
В тази (донякъде подобна) задача, номерът с разделяне на темите помежду им не работи. Макар и те да могат да направят това, като научават по 30 теми всеки (за което са им нужни 30 седмици), то тъй като задачите изискват знания от всички теми, то никой от тях не може да реши никоя от задачите (тоест наученото не може да бъде комбинирано). Точно това, че не можем да приложим стъпката "Владей", не разрешава тази задача да бъде решена с тази техника.

Примери

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

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

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

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

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

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

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

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

Ще приложим примерна имплементация на алгоритъма. На функцията подаваме четири числа - първото е N, тоест колко диска имаме да преместим, а останалите три са кой е началният стълб, кой е временният такъв и кой е крайният. За простота сме означили левия с нула, средния - с едно и десния - с две.
const
char
*
pegs[
3
]
=
{
"left"
,
"middle"
,
"right"
}
;
void
hanoiTowers(
int
n
,
int
initial
,
int
temporary
,
int
final) {
if
(n
<
=
0
)
return
;
// Местим по-малките дискове от началния стълб на временния, ползвайки
// крайния за временен (накрая той остава пак празен).
hanoiTowers(n
-
1
,
initial
,
final
,
temporary)
;
// Местим най-големия диск директно
fprintf(
stdout
,
"Moving disc from %s to %s.\n"
,
pegs[initial]
,
pegs[final])
;
// Местим по-малките дискове от временния стълб на крайния, ползвайки
// началния за временен (накрая той остава пак празен).
hanoiTowers(n
-
1
,
temporary
,
initial
,
final)
;
}

Тримино

Друга интересна задача, свързана с техниката, е задачата за триминота. Тук стъпката "разделяй" изисква малко креативност, но създава особено красиво решение.
Даден е квадрат със страна 2N, разделен на малки квадратчета (плочки) със страна 1. Едно от тях е оцветено в черно, всички останали в бяло. На всеки ход ние можем да поставим trimino, успоредно на страните на квадрата, ако то е разположено само върху бели плочки. Trimino е плочка от три квадратчета под формата на Г (евентуално завъртяно). Тоест квадрат с размер 2 на 2, на който липсва една от плочките. След поставянето му, трите бели плочки, върху които лежи, стават черни. Възможно ли е да се оцвети целият квадрат в черно с поставяне на trimino-та? Как?
Първо помислете сами малко.

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

Така. Ако сте успели да го измислите, можете да се чувствате много горди от себе си. Ако не сте, ето и решението. Ако дъската е 1 на 1, очевидно има решение (без нито едно тримино). Ако дъската е 2 на 2, то също очевидно има решение. Нека разгледаме случая, в който дъската е 4 на 4.
....
=
>
1122
или ....
=
>
5544
или #...
=
>
#122 .#..
=
>
1#32 ....
=
>
5334
....
=
>
1132
....
=
>
4335
....
=
>
2311
....
=
>
4335
....
=
>
4455
..#.
=
>
22#1 ....
=
>
4455
Намерихме решение на три от възможните начални разположения. След известно наблюдение се забелязва, че всяка дъска с размер 4 на 4 има решение чрез ротация и/или симетрия на някоя от горните три дъски. Бихме могли да предположим, че всяка дъска със страна 2N има решение. Сега да намерим стратегия и как да намираме самите решения.

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

Задачи

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

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

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

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

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



За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 6285 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: