Динамично оптимиране. Задача за разделянето

Преслав Наков

preslav@rila.bg

сп. Byte/Bulgaria, 11/1999

Често за решаването на една задача се оказва удачно тя да бъде разбита на по-малки подзадачи, които се решават по-лесно. По-малките подазачи често са по-прости за решаване и дават възможност за съсредоточване върху някои детайли и частни случаи, които не са така очевидни при изходната задача. Освен това подходящото разбиване ни дава съответно рекурсивно решение. Съществуват най-общо две ефективни алгоритмични схеми, основаващи се на разбиване на изходната задача на подзадачи: динамично оптимиране и разделяй и владей. В програмирането римският принцип “Разделяй и владей най-често се свежда до разделяне на изходната задача на две подзадачи с еднаква или приблизително еднаква размерност. На практика няма никакви ограничения върху броя на подзадачите, както и върху тяхната размерност, като единственото изискване, което се поставя, е никои две подзадачи да не се пресичат и решаването им да дава възможност за директно получаване на решение на изходната задача. От своя страна динамичното оптимиране е свързано най-често с премахване на единствен елемент, а подзадачите му се задължително се пресичат. По-долу въпросът ще бъде разгледан по-строго и ще бъдат приведени две необходими условия за прилагане на метода.

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

Горната дефиниция би могла да се стори на читателя прекалено математическа и в известна степен абстрактна. В действителност става въпрос за проста програмистка техника, подобна на “разделяй и владей”: задачата се разбива на подзадачи, те от своя страна отново се разбиват на подзадачи и т.н. до достигане на достатъчно прости задачи, които могат да се решат директно. След това решенията на подзадачите се комбинират по подходящ начин, така че да се получи решение н изходнта задача. За разлика от “разделяй и владей” обаче, тук не се изисква множествата на подзадачите да са непресичащи се, което означава, че динамичното оптимиране е по-обща техника от “разделяй и владей”. Отказът от изискването за непресичане на подмножествата от задачи обаче води до проблеми. В общия случай са налице полиномиален брой подзадачи на изходната, но в процеса на декомпозиция се оказва че едни и същи задачи се решават няколко пъти, при което получаваме екпоненциална сложност на алгоритъма. Типичен пример в това отношение е следната функция за пресмятане числата на Фибоначи:

int fib(int n) {

if (n < 2) return n;

else return fib(n-1) + fib(n-2); }

Какво може да се направи, за да се ускори функция, подобна на горната? Едно очевидно решение е да се въведе таблица на всички вече пресметнати стойности на функцията. Всеки път, когато трябва да пресметнем fib(n) за някоя конкретна стойност на n, първо ще проверяваме, дали вече не сме я записали в таблицата и едва тогава, в случай че задчата все още не е била решавана, ще извършваме съответните пресмятания. Така достигаме до втора, чисто “програмистка”

Дефиниция: Запълването на таблица с резултатите от решенията на вече решените подзадачи с цел избягване на излишните пресмятания се нарича динамично програмиране.

Макар основният принцип на динамичното оптимиране да е приложим и при задачи с единствено решение, като тази за намиране на n-тото число на Фибоначи, основното му приложение си остава решаването на оптимизационни задачи. Става въпрос за задачи с множество решения. На всяко решение се съпоставя някакво число с помощта на предварително дефинирана функция. Целта е да се намери такова решение, за което функцията приема своята оптимална (максимална или минимална) стойност. Прието е тази функция да се нарича целева функция. Възможно е задачата да има повече от едно оптимални решения, като в общия случай прилагането на динамичното оптимиране ще ни даде някое, но точно едно от тях.

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

Следва да се отбележи още, че динамичното оптимиране невинаги е приложимо. От една страна невинаги решението на изходната задача може да се получи чрез комбиниране на резултатите от решаването на част или всички нейни подзадачи. От друга страна, дори и когато такова комбиниране е възможно, може да се окаже, че броят на подзадачите, които следва да се разгледат е недопустимо голям. Към това следва да прибавим и липсата на ясен критерий, характеризиращ задачите, които могат да бъдат решени с помощта на описания метод: оказва се, че за редица задачи, стандартните алгоритми се оказват далеч по-ефективни от динамичното оптимиране, а за други — методът изобщо не е приложим.

Въпреки това съществуват две важни необходими условия за прилагане на метода: оптимална подструктура на решението и припокриване на подзадачите. Оптималната подструктура на решението означава, че оптималното решение на изходната задача може да бъде намерено като комбинация на оптималните решения на подзадачите. Обикновено изпълнението на този критерий ни води до намиране на подходящо “естествено” подпространство на подзадачите, които следва да бъдат разгледани. Така например при решаването на задачата за умножението на матриците, разгледана по-долу, ще видим, че е достатъчно да се разглеждат само подпоследователности на изходната последователност от матрици, а не произволни нейни подмножества. Това води до силно ограничаване множеството на подзадачите, откъдето и до по-голяма ефективност на метода. Второто необходимо условие за прилагане на динамичното оптимиране е припокриването на подзадачите. Динамичното оптимиране умее да се възползва умело от припокриването на подзадачите, пресмятайки решението на всяка от тях само веднъж, силно ограничавайки по този начин действителния брой решени подзадачи. Колкото по-рядко се налага действително решаване на нова подзадача, толкова по-ефективен е методът. Липсата на припокриване на подзадачите е сигурен индикатор, че прилагането на динамичното оптимиране е неподходящо. В такъв случай е добре да се опита с метода “разделяй и владей”, който, в случай че е приложим, ще даде по-добри резултати.

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

Обикновено задачите от динамично оптимиране се решават итеративно отдолу-нагоре, т.е. първо се решават тривиалните подзадачи, след това тези, чиито подзадачи вече са решени и т.н. Основен недостатък на този подход е, че изисква решаване на всички подзадачи с размерност, по-малка от тази на изходната задача, при което често се пресмятат решенията на подзадачи, чието решаване не е нужно за решаване на изходната. По-долу ще разгледаме конкретни примери. Обикновено това не е толкова опасно и не води до съществено забавяне. Понякога обаче премахването на излишните пресмятания може да доведе до значително увеличение на скоростта. В такъв случай се прилага специален вариант на динамичното оптимиране, известен в англоезичната литература като memoization. Идеята е да се използва рекурсивна функция, при което да се обърне редът на пресмятане на решенията на подзадачите: отгоре-надолу. Преди да се извърши обръщение към функцията, масивът, в който пазим стойностите на решенията на подзадачите, се инициализира със специална стойност-индикатор, указваща че решението все още не е било пресмятано. Рекурсивната функция извършва пресмятане, само ако съответният елемент на масива съдържа въпросния индикатор, след което записва там резултата. В противен случай резултатът се взема наготово от таблицата. Така се пресмятат само тези подзадачи, които реално могат да участват в оптималното решение.

Динамичното оптимиране често се подценява, или по-точно — недооценява. Сред някои програмисти битува мнението, че то е сложно и объркано. В действителност става въпрос за една от най-простите и същевременно ефективни алгоритмични техники. Веднъж разбрал основните му принципи, за читателя ще бъде по-лесно откриването и съставянето на собствени схеми, отколкото откриването им литературата. Тъй като подобни знания се усвояват най-лесно на базата на конкретни примери, ще разгледаме една задача използваща посочения метод*.

(*) Б.р.: Предложената задача е задачата с библиотеката от ЗМС’2000, която я има във файла bibliot.pdf, затова сметнахме за ненужно публикуването и тук.

Литература:

[Бонев-1996] Бонев Ст., “Итерация или рекурсия — предимства и недостатъци”, сп. “PC&MAC World” 4/1996.

[Калихман-1979] Калихман И., М. Войтенко, “Динамическое программирование в примерах и задачах”, “Высшая школа”, Москва, 1979.

[Brassard,Bratley–1987] Brassard G., Bratley P., Fundamentals of Algorithmics, Prentice-Hall, 1996.

[Cormen,Leiserson,Rivest–1998] Cormen T., Leiserson C., Rivest R., Introduction to Algorithms, The MIT Press, 1998.

[Parberry-1995] Parberry I., “Problems on Algorithms”, Prentice-Hall, 1995.

[Sedgewick-1990] Sedgewick R., “Algorithms in C”, Addison-Wesley Publishing Company, New York, 1990.

[Skiena-1997] Skiena S., “The Algorithm Design Manual”, Springer-Telos, 1997.