Пълно изчерпване

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

Много често се налага да се изчерпват всички пермутации на $N$ елемента и да се определи кои от тях изпълняват дадено свойство. За улеснение нека си мислим, че трябва да итерираме през всички пермутации на числата $1,2,3,\dots,N$. Обикновено за таково пълно изчерпване в езика C++ се използва функцията next_permutation от стандартната библиотека algorithm. На тази функция се подава пермутация в масив или вектор и тя записва в него следващата (в лексикографски ред) пермутация, ако има такава. Връща булев резултат - лъжа, ако е достигната последната пермутация (...), в който случай не се променя подадената пермутация, и истина в останалите случаи. Следният код илюстрира скелета на такъв тип пълно изчерпване:

Такова решение има голяма сложност - $O(N!*check)$, където check е функцията на сложността на check_permutation в програмата. В някои задачи може да се разшири действието на такова пълно изчерпване. Понеже имаме само едно число, от което зависи крайния отговор, то спокойно бихме могли да пуснем нашето решение и да запишем какви отговори дава за $N=1,2,3,\dots$, докъдето има смисъл, предвид голямата сложност. Така за същинското решение ще запишем получените отговори в някакъв масив и ще гледаме отговорите от него. Тази техника се нарича precompute или преизчисляване на отговорите. Разбира се, тук става дума само за малко разширяване на действието на такъв алгоритъм, защото много бързо се покачва времето, което трябва да се чака за намирането на даден отговор. Ако искаме да намерим всички отговори за $N=1,2,\dots,k$, то сложността става грубо $O(k*k!*check)$.

При това пълно изчерпване има оптимизация, която може да се използва в голяма част от случаите, ако знаем точното $k$, до което искаме да намерим отговорите (например гледайки ограниченията на подзадачите). За да е по-ясно, можем да погледнем следната задача. Концетрираме се само върху първа и втора подзадача. Първа подзадача може да стане с досега описаното пълно изчерпване. За втората подзадача трябва да използваме преизчисляване на отговорите. Тук гледайки ограничението $N \le 13$ е ясно, че ще ни трябват отговорите до 13. Оптимизацията, която ще направим е следната. Вместо да пускаме пълното изчерпване за всички $N$, ще го пуснем само за най-голямото (13) и от него ще намерим отговорите и за по-малките числа. Това можем да направим, понеже в префиксите на пермутациите на числата от 1 до 13 се съдържат всички пермутации на числата от 1 до 12, всички пермутации на числата от 1 до 11 и т.н.

Нека сега си представяме, че обхождаме пермутацията $1,3,2,4,5$, за да проверим дали се "дели" на 11. Искаме когато стигнем, до третата позиция да знаем, че това е валидна пермутация на числата от 1 до 3. Същото важи и за четвърта и пета позиция. Можем да направим следното наблюдение. Нека сме на позиция $i$. Тогава ако максималното число, което се е срещнало до тази позиция включително също е $i$, то това е валидна пермутация на числата $1,2,\dots,i-1,i$, защото сме имали на тези позиции $i$ различни числа от 1 до $i$. По този начин константно разбираме за дадена позиция дали в нея завършва валидна пермутация. Ясно е, че в случая проверката, която трябва да направим за делимост на 11, става константно за всеки префикс на пермутацията (...). Последният проблем е следният - броим по-малките пермутации по няколко пъти. За горния пример, пермутацията $1,3,2$ ще я преброим още един път - при обхождането на пермутацията $1,3,2,5,4$. Лесно се вижда, че всяка пермутация на $i$ на брой числа ще я преброим $(N-i)!$ пъти - колкото са разместванията на останалите числа. Следният код на езика C++ показва примерно решение, което преизчислява отговорите до 13 за нашата задача:

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

Обикновено можем да оптимизираме такъв вид пълно изчерпване от $N!$ до $2^N$. За по-добро разбиране, първо е хубаво да сте минали темата за динамични по подмножества. Това, което се изполва за оптимизацията е следното. Нека си представим, че генерираме пермутациите с рекурсия и сме стигнали до някаква текуща позиция за пермутация. Единствената информация, която трябва да знаем, е точно кои числа са използвани в пермутацията досега и какъв остатък при деление на 11 дават слепените числа до сега. Това, което не ни е нужно е точният ред, в който са били тези числа. Затова е достатъчно на дадена позиция да знаем само множеството от числата, които са били, и остатъкът им. Така можем да направим следната мемоизация на рекурсията за генериране на пермутации - $dp[mask][remainder]$, където $mask$ е битовата маска на включените числа досега, а $remainder$ е остатъкът на слепените числа досега.

Сложността на това решение е $O(2^N*11*N)$ и то решава третата подзадача. Лесно се вижда, че използвайки това по-бързо пълно изчерпване, можем да направим доста по-добро преизчисление на отговорите. Така ще успеем да намерим дори отговорите до 24, което ще стигне за четвъртата подзадача. В интерес на истината, това пълно изчерпване расте много по-бавно с нарастването на $N$ и би могло за разумно време да намери още отговори. Проблем обаче започва да става паметта, защото памет от порядъка на $O(2^N*11)$ става твърде много (...).

Тази оптимизация се използва за една много известна задача - търсене на Хамилтонови пътища или цикли. Това е известен нерешим проблем от класа $NP$-пълни задачи (...). Нека разглеждам графи с $N$ върха. Стандартното пълно изчерпване, което е да обходим всички възможни пътища\цикли, в най-лошия случай е еквивалентно да обходим всички възможни пермутации на върховете. Сложността е $O(N!*N)$. Лесно може да се забележи, че тук важи отново горното наблюдение - като сме стигнали до даден връх ни интересува единствено текущия връх и множеството от върхове, през които сме минали досега. Така че можем да оптимизираме решението на тази задача до $O(2^N*N^2)$.

Това е другата често срещана конфигурация. Нека си мислим, че искаме да итерираме през всички подмножества на множеството $S=\{0,1,2,\dots,N-1\}$. Отново ще си говорим как става най-лесно такъв вид пълно изчерпване. Един вариант е да итерираме всички подмножества чрез рекурсивна функция, но има вариант, който е по-бърз и поучителен. Нека разгледаме например $N=4$, т.е. $S=\{0,1,2,3\}$. Тогава множеството $\{0,2,3\}$ се явява подмножество на $S$. Всяко подмножество можем да асоциираме с двоично число, на което всеки бит, който е 1, показва, че дадено число участва в подмножеството. А всеки бит, който е 0, показва, че съответното число не участва в подмножеството. За множеството $\{0,2,3\}$, съответстващото двоично число е $1101_{(2)}=13_{(10)}$. Това съответствие е взаимно-еднозначно. Така че броят подмножество на дадено $N$-елементно множество, не случайно е $2^N$. На всяко подмножество съответства еднозначно число от 0 до $2^N-1$, което се нарича битова маска. Това ни позволява да напишем пълно изчерпване по подмножества по следната кратка схема:

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