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

Dynamic Programming, Part III

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

Битова маска

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

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

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

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

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

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

Нека, например, сме в стейт с маска mask. За да проверим дали даден елемент k е ползван или не, трябва да видим дали битовата маска съдържа единица или нула на съответната позиция:
if
(contains(mask
,
k)) { ... }
Или по-просто без функция:
if
(mask
&
(
1
<
<
k)) { ... }

Ако решим да го ползваме, ни трябва нова маска, която да е същата като досегашната, но с k-ти бит сетнат на единица. Това може да стане по следния начин:
int
nmask
=
unite(mask
,
(
1
<
<
k))
;
Или дори по-просто без функция:
int
nmask
=
mask
|
(
1
<
<
k)
;

Много често можем да не ползваме допълнителна променлива изобщо, а да извършваме побитовата операция директно когато ни трябва:
for
(
int
k
=
0
;
k
<
N
;
k
+
+
) {
if
(
!
(mask
&
(
1
<
<
k))) { ans
=
min(ans
,
recurse(mask
|
(
1
<
<
k)))
;
} }

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

Една примерна задача, която директно илюстрира ползването на този тип динамични, е задачата

Distance

Shumen 2007

Author: Alexander Georgiev
Tags: Easy, Dynamic Programming, Bitmasks
Statement | Archive | Online Judge
Distance. Накратко условието е:
Дадени са ви 2 ≤ N ≤ 22 елемента (N е четно), като трябва да ги групирате по двойки. Знаете печалбата, която ще получите, ако групирате всеки два елемента като двойка. Всеки елемент може да участва само в една двойка. Каква е максималната печалба, която можете да получите?
Както и при много други динамични задачи, и тук донякъде интуитивно човек може да си помисли, че алчна стратегия би работела. Например най-очевидната от тях е следната: намираме двойката все още неизползвани елементи, чиято печалба е най-голяма, и ги взимаме (тоест отбелязваме като използвани и прибавяме печалбата към отговора). Това, обаче, не винаги е оптимално. Например ако имаме 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) също не би довела до оптимален отговор. Като цяло, може да се създаде тест, в който оптималната двойка, която трябва да се вземе на текущия ход, не е дори близо до тези, носещи най-голяма печалба.

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

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

Ако си представим, че печалбата е изчислена в двумерен масив, в който елементът win[i][j] показва каква е печалбата, ако вземем (i, j) като двойка, имплементацията би била:
unsigned
recurse(
int
mask) {
if
(dyn[mask]
!
=
INF)
return
dyn[mask]
;
unsigned
ans
=
0
;
for
(
int
i
=
0
;
i
<
n
;
i
+
+
)
if
(
!
(mask
&
(
1
<
<
i))) {
for
(
int
c
=
i
+
1
;
c
<
n
;
c
+
+
)
if
(
!
(mask
&
(
1
<
<
c))) {
int
nmask
=
mask
|
(
1
<
<
i)
|
(
1
<
<
c)
;
ans
=
max(ans
,
win[i][c]
+
recurse(nmask))
;
} }
return
dyn[mask]
=
ans
;
}
В кода горе считаме, че unsigned dyn[1 << 22] е динамичната ни таблица, която в началото сме инициализирали с константата INF.

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

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

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

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

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

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

HamellytonianPath

MayCamp Contest

Author: Alexander Georgiev
Tags: Medium, DP, Bitmasks
Statement | Archive | Online Judge
HamellytonianPath, в която това се изискваше.

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

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


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

Подсказки

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

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

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

В някои случаи е почти очевидно, че трябва да ползваме динамично по битова маска, но е трудно да се досетим как да го направим достатъчно бързо. Нека разгледаме следната примерна задача:
Ели иска да сложи паркет в стаята си. Стаята е с размер N на М (1 ≤ N, M ≤ 16), а всяко блокче паркет е с размер 1 на 2, като може да бъде завъртяно както хоризонтално, така и вертикално.

Стаята има определен брой колони от земята до тавана, които, очевидно, не трябва да се паркетират. Цялата стая и колоните в нея ще ви е зададена като ASCII арт - N на брой реда, всеки съдържащ стринг с M символа. Всеки символ е или '#', указващ колона, или '.', указващ под, който трябва да се покрие с парче от паркет.

За да запази красивия вид на паркета, Ели не иска нито едно от парчетата да бъде разрязано. По колко начина може да се сложи паркета, така че целият под да бъде покрит? Считаме две слагания на паркет за различни, ако има клетка от стаята, в която в едното разположение парчето паркет да е сложено хоризонтално, а в другото - вертикално.
"По колко начина" веднага трябва да ни насочва към динамично. Допълнително, размерите до 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 - за следващия.

Това откъм код ще изглежда по следния начин:
int
dyn[MAX][MAX][
1
<
<
MAX]
;
int
recurse(
int
row
,
int
col
,
int
mask) {
if
(row
>
=
n)
return
!
mask
;
if
(col
>
=
m)
return
recurse(row
+
1
,
0
,
mask)
;
// Already occupied
if
(board[row][col]
=
=
'#'
|
|
(mask
&
(
1
<
<
col)))
return
recurse(row
,
col
+
1
,
mask
&
~
(
1
<
<
col))
;
int
ans
=
0
;
// Horizontal
if
(col
+
1
<
m
&
&
board[row][col
+
1
]
=
=
'.'
&
&
!
(mask
&
(
1
<
<
(col
+
1
)))) ans
+
=
recurse(row
,
col
+
2
,
mask)
;
// Vertical
if
(row
+
1
<
n
&
&
board[row
+
1
][col]
=
=
'.'
) ans
+
=
recurse(row
,
col
+
1
,
mask
|
(
1
<
<
col))
;
return
dyn[row][col][mask]
=
ans
;
}
Тъй като имаме само константни операции в тялото на динамичното, сложността му е равна на броя клетки на динамичната таблица: O(N∙M∙2M).

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

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

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

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

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

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

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

Идеята е следната. Нека сме сложили няколко букви. От гледна точка на стейта, няма значение коя от следните три конфигурации сме ползвали:
ABGH..... или AEFG..... или ABEH..... CFI...... или BHI...... или CDG...... D........ или C........ или F........ E........ или D........ или I........ ......... или ......... или .........
И трите разположения можем да кодираме по един и същ начин, тъй като:
  1. Следващата буква ('J') може да бъде сложена надясно и надолу от всяка от досега сложените;
  2. Следващата буква може да бъде сложена само на позиции, допиращи се отгоре и отляво до други букви (или краищата на дъската).

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

Задачи

Задачата

Keys

TopCoder Custom Round

Author: Alexander Georgiev
Tags: Medium, Dynamic Programming, Bitmasks
Statement | Archive | Online Judge
Keys е чисто приложение на идеята за динамично по битова маска. Задачата

Friday

Winter Contest 2012, Group B

Author: Alexander Georgiev
Tags: Medium, Dijkstra, Graph, Masks
Statement | Archive | Online Judge
Friday пък използва разширяване на графа чрез битови маски (и прилагане на стандартен графов алгоритъм).

Bribes

TopCoder SRM 483, Div1 500

Author: Alexander Georgiev
Tags: Hard, DP, Bitmasks, Ad-hoc
Statement | Archive | Online Judge
Bribes, освен, че е мой персонален ачийвмънт (вкарах думата "шуробаджанащина" в условие в TopCoder), "прикрива" нуждата от (плъзгащи се) битови маски по як начин.

Malls

NOI 2012, K3, Group A

Author: Alexander Georgiev
Tags: Hard, DP, Map, Bitmasks
Statement | Archive | Online Judge
Malls пък е задача, ползваща трика за динамично с map и битови маски.

Още задачи

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

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


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

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

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

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