Динамично оптимиране, част III

Dynamic Programming, Part III

Битова маска

Една много честа разновидност на динамичното оптимиране са задачи, в които стейтът съдържа информация кои елементи от дадено множество са използвани и кои не. Тъй като за всеки елемент имаме точно две възможности - или вече е използван, или все още не е - то ако имаме N елемента, динамичната таблица би била с N измерения [2][2][2]...[2]. Това е ужасно неудобно за използване и индексиране, затова е хубаво да обединим размерностите, както показахме в темата трикове в динамичното оптимиране.

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

Обединените N размерности [2][2][2]...[2] ще представим като едно единствено число, което се нарича битова маска и ще бележим като mask. В състезателни задачи рядко ще имаме памет за повече от 24 елемента, тъй като за да пазим N-мерна таблица [2][2][2]...[2] са нужни 2^N клетки. С всеки допълнителен елемент на множеството, нужната памет се увеличава двойно (тоест расте експоненциално). От това следва, че битовата маска mask може спокойно да е от тип int - тъй като той е (поне) 32-битов на днешните компютри, ще поддържа (поне) 32 елемента.

Динамично по битова маска

Стейтът при такова динамично би бил следният. Едното измерение ще е битовата маска, която ще отговаря за "използваност" на елементите от някакво множество. То ще е с големина 2^N (което в кода можем да представим като: (1 << N)), в случай, че множеството се състои от N елемента. Възможно е освен него да имаме и други измерения, носещи допълнителна информация (примерно последно използван елемент) - тях си ги държим като отделни размерности и няма да вкарваме в маската.

Когато искаме да обновим информацията за елементите, просто прилагаме съответната побитова операция (ще ползваме функциите contains() и unite() от темата за побитови операции) като запазваме резултата в някаква нова променлива, примерно nmask (от "new mask"). Ползваме нова променлива, защото не искаме да променяме текущата mask - нейната оригинална стойност ще ни трябва в края на функцията, когато попълваме динамичната таблица.

Промяна на маската

Нека, например, сме в стейт с маска mask. За да проверим дали даден елемент k е ползван или не, трябва да видим дали битовата маска съдържа единица или нула на съответната позиция: Или по-просто без функция:
Ако решим да го ползваме, ни трябва нова маска, която да е същата като досегашната, но с k-ти бит сетнат на единица. Това може да стане по следния начин: Или дори по-просто без функция:
Много често можем да не ползваме допълнителна променлива изобщо, а да извършваме побитовата операция директно когато ни трябва:

Примерна задача с битови маски

Една примерна задача, която директно илюстрира ползването на този тип динамични, е задачата Noise. Накратко условието е: Както и при много други динамични задачи, и тук донякъде интуитивно човек може да си помисли, че алчна стратегия би работела. Например най-очевидната от тях е следната: намираме двойката все още неизползвани елементи, чиято печалба е най-голяма, и ги взимаме (тоест отбелязваме като използвани и прибавяме печалбата към отговора). Това, обаче, не винаги е оптимално. Например ако имаме 4 елемента и печалбите са съответно:

1. (1, 2) = 8
2. (1, 3) = 5
3. (1, 4) = 2
4. (2, 3) = 7
5. (2, 4) = 5
6. (3, 4) = 1

То алчната стратегия би взела (1, 2) с печалба 8 и после (3, 4) с печалба 1 (за общ резултат 9). Но оптималният отговор би бил (1, 3) с печалба 5 и (2, 4) с печалба 5 (за общ резултат 10). Забележете, че дори втората по големина двойка (2, 3) също не би довела до оптимален отговор. Като цяло, може да се създаде тест, в който оптималната двойка, която трябва да се вземе на текущия ход, не е дори близо до тези, носещи най-голяма печалба.

Какво казахме че правим, когато не знаем какво да правим? Пробваме всичко! Разбира се, тук ще използваме динамично оптимиране да забързаме този процес.

Стейтът не е нищо друго, освен това, кои елементи вече сме ползвали. В случая това ще е едно единствено измерение, в което можем да пазим двоично число с до 24 бита, тоест (1 << 24) = 2²⁴.

Ако си представим, че печалбата е изчислена в двумерен масив, в който елементът win[i][j] показва каква е печалбата, ако вземем (i, j) като двойка, имплементацията би била: В кода горе считаме, че unsigned dyn[1 << 24] е динамичната ни таблица, която в началото сме инициализирали с константата INF.

Сложността на тази имплементация е O(2N∙N2).

Оптимизация на паметта

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

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

Оптимизация на бързодействието

Тук може да бъде приложена и една оптимизация по време, която не е много очевидна. Тъй като всеки елемент трябва да бъде използван, то рано или късно ще използваме първия все още неизползван. Защо, тогава, да не направим това още на тази стъпка? Съответно можем винаги да вземаме първия неизползван и да търсим само кой от останалите ще съчетаем с него. Така сваляме сложността на алгоритъма до O(2N∙N). В тази версия на задачата това се и изисква, тъй като иначе най-вероятно ще получите Time Limit. Друг пример за задача с битови маски е The Price Is Right, в която отново трябва да приложите тази оптимизация.

Търговски пътник

Някои от вас може би са чували задачата за Търговския Пътник - тя е много популярна, тъй като е най-известният пример за задача от класа NP. Ще говорим по-подробно за нея по-късно в темата за NP задачи. Накратко, нейното условие е следното: До ден днешен тази задача няма известно полиномиално решение. За сравнително малък брой върхове, обаче, съществува решение, базирано на динамично оптимиране с битови маски. Можете ли да го конструирате?


Тук проблемът е, че ако стейтът ни е само битовата маска на посетените градове, няма да знаем в кой град се намираме в момента.
Затова ще добавим второ измерение с размер N, което указва текущия град, в който се намираме. Така целият стейт става [1 << N][N], и тъй като за всеки стейт трябва да разгледаме всички съседи на текущия връх (потенциално до N на брой), цялата сложност става O(N2∙2N).

Подсказки

Често подсказки, че дадена задача може да се реши по подобен начин е наличието на елементи, които можем да вземем или не максимум по веднъж, както и сравнително малки ограничения (от 15 до около 22-24). Ограниченията са такива, тъй като, както казахме по-горе, паметта е поне колкото броя стейтове има динамичната таблица. Ако имаме по-голям брой, например 30, ще са ни нужни поне 2³⁰ = 1073741824 байта = 1GB памет, което много рядко е разрешено на състезание. Допълнително, самото изпълнение на толкова операции ще е значително бавно и ще изисква поне няколко секунди.

Защо пък няма да е под 15 (или нещо сходно)? Ами, най-глупавото bruteforce решение с бектрек е със сложност O(N!), което за N ≤ 11 е напълно направимо на модерен компютър. Нещо повече, голяма част от бектреците могат лесно да бъдат оптимизирани (като се режат невъзможни или очевидно неоптимални преходи), което допълнително забързва изпълнението и позволява глупавият алгоритъм да работи дори за по-големи числа.

Плъзгащи се битови маски

В някои случаи е почти очевидно, че трябва да ползваме динамично по битова маска, но е трудно да се досетим как да го направим достатъчно бързо. Нека разгледаме следната примерна задача: "По колко начина" веднага трябва да ни насочва към динамично. Допълнително, размерите до 16 за N и M си плачат за битова маска. Стейтът може да изглежда нещо от сорта на [16][1 << 16], като първото измерение пази до кой ред сме стигнали, а второто - как "стърчат" вертикалните блокчета паркет, започващи от предния ред.

Все пак, самото тяло на динамичното не е очевидно. Как преминаваме от стейт в стейт?

?	Все пак, това понякога би ви свършило работа, като например в задача Art от CodeIT Round 4, 2014. В нея ограниченията бяха едва до 12, което позволяваше дори това решение да мине.

Един относително очевиден начин е да пробваме всички варианти дали да са вертикални или хоризонтални блокчетата на текущия ред и да видим, дали се съчетават добре с колоните и със стърчащите от горния ред. Това, обаче, би довело до сложност O(N∙2M∙2M), което е много над това, което можем да си позволим.

Друг начин е да вкараме в стейта и колоната, като попълваме още една маска за следващия ред (как вертикалните парчета, започващи от този ред, стърчат надолу). Това, обаче би означавало, че трябва да пазим и втората маска в стейта, като така ще се нуждаем от O(N∙M∙2M∙2M) памет, което е абсурдно много. Можем ли, обаче, да се измъкнем от втората маска? Можем, разбира се!

Реално, ако сме на col-тата колона на даден ред row, от горната маска вече не ни интересува дали стърчат паркетчета на позициите 0, 1, ..., col - 2, col - 1. В същото време точно на тези позиции ни интересува дали стърчат надолу (към ред row + 1) парчета от текущия такъв. Затова стейтът ни ще е [16][16][1 << 16]. Първите две измерения ще пазят текущия ред и текущата колона (обхождаме стаята ред по ред, като всеки ред - колона по колона). Третото измерение ще е маска, чиито битове до col - 1 пазят информация къде стърчат парчета паркет от текущия ред към следващия, а от col нататък - как стърчат от горния ред към текущия. След като решим за текущия ред и колона дали да сложим (ако можем) парче хоризонтално или вертикално, обновяваме маската така че col-тият бит вече да пази информация за следващия ред, вместо за текущия. Така реално "плъзгаме" битовата маска циклично по редовете, като от позиция col нататък (оставащите колони на текущия ред) маската е за текущия ред, а от 0 до col - 1 - за следващия.

Това откъм код ще изглежда по следния начин: Тъй като имаме само константни операции в тялото на динамичното, сложността му е равна на броя клетки на динамичната таблица: O(N∙M∙2M).

Динамично по шаблон

Друг интересен тип динамични са динамичните по шаблон. В тях стейтът описва не какво да е ами... форма!

Представете си, например, нареденото множество (5, 1, 3, 1, 5). На пръв поглед, това не ви говори нищо, нали? Но ако видите следната ASCII карикатура бихте си представили буквата 'E', нали?

Ако допуснем, че всяко от числата показва каква е "дължината" на съответния ред, то с таблица [6][6][6][6][6] (или [46656], ако обединим измеренията в едно) бихме могли да описваме някои от латинските (че и кирилишки) букви. Забележете, че по този начин не можем да опишем всички латински букви - например не можем да описваме такива, които съдържат дупка (например 'A', 'B', 'O'...), или такива, които изискват специфична индентация на някои от редовете (например 'T').

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

Примерна задача

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

Идеята е следната. Нека сме сложили няколко букви. От гледна точка на стейта, няма значение коя от следните три конфигурации сме ползвали: И трите разположения можем да кодираме по един и същ начин, тъй като:

1. Следващата буква ('J') може да бъде сложена надясно и надолу от всяка от досега сложените;
2. Следващата буква може да бъде сложена само на позиции, допиращи се отгоре и отляво до други букви (или краищата на дъската).

Ще ползваме 5-мерно динамично, като всяка размерност ще показва колко букви има сложени в даден ред. Така горните три разположения ще се кодират като [4][3][1][1][0], тъй като имаме 4 букви в първия ред, 3 букви във втория, 1 буква в третия, 1 в четвъртия и 0 в петия.

Задачи

Задачата Keys е чисто приложение на идеята за динамично по битова маска. Задачата Friday пък използва разширяване на графа чрез битови маски (и прилагане на стандартен графов алгоритъм). Bribes, освен, че е мой персонален ачийвмънт (вкарах думата "шуробаджанащина" в условие в TopCoder), "прикрива" нуждата от (плъзгащи се) битови маски по як начин. Malls пък е задача, ползваща трика за динамично с map и битови маски. Поради популярността си, сме направили отделна секция за Динамично по Битова Маска в тренировъчната секция на системата.

Още задачи

• False Mirrors (Timus)
• Merry-go-round (Timus)
• Looking for Order (Codeforces)
• Fish (Codeforces)
• Nuclear Fusion (Codeforces)

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

1. Битови хакове
2. Динамично оптимиране, част I
3. Динамично оптимиране, част II
4. Трикове в динамичното оптимиране
5. Динамично с битови маски (cs.ubc.ca)

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

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

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