Научно-изследователската работа, вероятно, е най-интригуващата част от нашето обучение. Идеята е в университета да опитате да се проявите в избраната посока. Например, студенти от направленията Софтверно инженерство и Машинно обучение често правят научни изследвания в компании (предимно JetBrains или Яндекс, но не само).
В този пост ще разкажа за моя проект в областта на Компютърните науки. В рамките на работата изучих и реализирах на практика подходи за решаване на една от най-известните NP-трудни задачи: задача за покритие на върхове.
Сега много бързо се развива интересен подход към NP-трудните задачи — параметризирани алгоритми. Ще се опитам да ви въведа в състоянието на нещата, да разкажа за няколко прости параметризирани алгоритми и да опиша един мощен метод, който много ми помогна. Резултатите си представих на състезанието PACE Challenge: по резултатите от откритите тестове решението ми заема трето място, а окончателните резултати ще бъдат известни на 1 юли.
За мен
Казвам се Василий Алфьоров, в момента завършвам трета година в НИУ ВШЭ - Санкт Петербург. Интересувам се от алгоритми още от училище, когато учих в московското училище 179 и успявах да участвам в олимпиади по информатика.
Краен брой специалисти по параметризирани алгоритми влизат в бара…
Примерът е взет от книгата
Представете си, че сте охранител в бара в малък град. Всеки петък половината от града идва в бара, за да се отпусне, което ви създава много проблеми: трябва да изхвърляте буйни клиенти, за да предотвратите свади. В крайна сметка, това ви омръзва и решавате да предприемете превантивни мерки.
Тъй като градът ви е малък, точно знаете кои двойки посетители с голяма вероятност ще се сбият, ако попаднат в бара заедно. Имате списък от n човека, които ще дойдат тази вечер в бара. Решавате да не пуснете в бара определени граждани така, че да не се стигне до сбивания. В същото време, вашето началство не иска да губи печалба и ще бъде недоволно, ако не пуснете в бара повече от k човека.
За съжаление, задачата, с която сте изправени, е класическа NP-трудна задача. Може да я знаете като , или като задача за покритие на върхове. За такива задачи обикновено не са известни алгоритми, работещи за приемливо време. Ако бъдем точни, недоказаната и доста силна хипотеза ETH (Хипотеза за експоненциално време) предполага, че тази задача не може да бъде решена за време 
, тоест, че не може да бъде измислено нещо по-добро от пълното изброяване. Например, представете си, че в бара ви се канят да дойдат n = 1000 човека. Тогава пълното изброяване ще състави 
варианти, което е приблизително 
— безумно много. За щастие, вашето ръководство е наложило ограничение k = 10, така че броят на комбинациите, които трябва да проверите, е много по-малък: броят на подмножествата с десет елемента е равен на 
. Това е вече по-добре, но все пак не може да бъде преброено за един ден дори на мощен кластер.
За да се изключи вероятността от бой при такава конфигурация на напрегнатите отношения между клиентите на бара, трябва да не се допускат Боб, Даниел и Фьодор. Решение, при което ще останат извън борда само двама, не съществува.
Означава ли това, че е време да се предадем и да пуснем всички? Нека разгледаме други варианти. Например, можем да не допускаме само тези, които вероятно ще се сбият с много хора. Ако някой може да се бие поне с k + 1 друг човек, то него определено не трябва да го пускаме — иначе ще се наложи да не пуснем всички k + 1 граждани, с които може да се сбие, което вече определено ще разстрои ръководството.
Нека предположим, че сте изхвърлили всички, които можете, на това основание. Тогава всички останали могат да се сбият не повече от k хора. Изхвърляйки от тях k човека, можете да предотвратите не повече от 
конфликта. Следователно, ако повече от 
човека участват поне в един конфликт, то определено няма да можете да предотвратите всички тях. Тъй като, разбира се, съвсем неконфликтни хора ще ги пуснете, трябва да проверите всички подмножества с размер десет от двеста хора. Има приблизително 
, а такова количество операции вече може да бъде проверено на кластер.
Ако можем безопасно да поканим напълно неконфликтни личности, какво да кажем за тези, които участват само в един конфликт? Всъщност, можем и тях да пуснем, затваряйки вратата пред техния опонент. И наистина, ако Алис има конфликт само с Боб, то ако поканим Алис, няма да загубим: Боб може да има и други конфликти, а Алис със сигурност няма. Освен това няма смисъл да не пускаме и двамата. След такива операции остава не повече 
гости с нерешена съдба: общо имаме 
конфликта, във всеки от които има по двама участника и всеки участва поне в два. Следователно, остава да разгледаме само 
варианта, което спокойно може да се сметне за половин ден на лаптоп.
Всъщност, с прости разсъждения можем да постигнем дори още по-привлекателни условия. Нека забележим, че задължително трябва да решим всички спорове, т.е. от всяка конфликтна двойка да изберем поне един човек, когото няма да пуснем. Нека разгледаме такъв алгоритъм: ще вземем произволен конфликт, от който ще извадим един участник и рекурсивно ще продължим с остатъка, след това ще извадим и другия и също рекурсивно ще продължим. Тъй като на всяка стъпка изхвърляме някого, дървото на рекурсията на този алгоритъм е бинарно дърво с дълбочина k, следователно, сумарната работа на алгоритъма е 
, където n — брой върхове, а m — брой ребра. В нашия пример това е около десет милиона, което за части от секундата ще бъде изчислено не само на лаптоп, но дори на мобилен телефон.
Предоставеният по-горе пример е пример на параметризирани алгоритми. Параметризирани алгоритми са алгоритми, които работят за време f(k) poly(n), където p — полином, f — произволно изчислима функция, а k — някакъв параметър, който е напълно възможно да бъде много по-малък от размера на задачата.
Всички разсъждения до този алгоритъм довеждат до примера на кернелизацията — една от общите техники за създаване на параметрични алгоритми. Ядренето е намаляване на размера на задачата до стойност, ограничена от функцията на параметъра. Получената задача често се нарича ядро. Така, с прости разсъждения относно степените на върховете, получихме квадратично ядро за задачата Vertex Cover, параметризирана по размера на отговора. Съществуват и други параметри, които могат да се изберат за тази задача (например, Vertex Cover Above LP), но ние ще обсъждаме именно такъв параметър.
Pace Challenge
Соревнование (Предизвикателството за параметризирани алгоритми и изчислителни експерименти) започна през 2015 година, за да установи връзка между параметризираните алгоритми и подходите, използвани на практика за решаване на изчислителни задачи. Първите три състезания бяха посветени на намирането на дървесна ширина на графа (), търсенето на дърво на Штайнер () и търсенето на множество върхове, разрязващи цикли (). Тази година една от задачите, в които можеха да се пробват участниците, беше описаната по-горе задача за покритие на върховете.
Състезанието набира популярност с всяка година. Ако вярваме на предварителните данни, то тази година само в състезанието по решение на задачата за покритие на върховете взеха участие 24 отбора. Трябва да се отбележи, че състезанието не продължава няколко часа и дори не седмица, а няколко месеца. Отборите имат възможност да проучат литературата, да измислят своя оригинална идея и да се опитат да я реализират. По същество, това състезание представлява изследователска работа. Идеите за най-ефективните решения и награждаването на победителите ще се проведе заедно с конференцията (Международен симпозиум по параметризирано и точно изчисление) в рамките на най-голямото ежегодно алгоритмично събиране в Европа . По-подробна информация относно самото състезание можете да намерите на , а резултатите от предишни години са налични .
Схема решение
За да се справя със задачата за върховно покритие, опитах да приложа параметризирани алгоритми. Те обикновено се състоят от две части: правила за опростяване (които в идеалния случай водят до кернелизация) и правила за разделяне. Правилата за опростяване са предварителна обработка на входа за полиномно време. Целта на прилагането на такива правила е да сведе задачата до еквивалентна задача с по-малък размер. Правилата за опростяване са най-скъпата част от алгоритъма, и приложението именно на тази част води до общо времетраене 
вместо простото полиномно време. В нашия случай правилата за разделяне са базирани на факта, че за всяка върха трябва да вземем в отговор или нея, или нейния съсед.
Общата схема е следната: прилагаме правилата за опростяване, след това избираме някаква върха и правим два рекурсивни извиквания: в първото взимаме нея в отговор, а във второто взимаме всичките ѝ съседи. Това наричаме да се разделим (бранчваме) по тази върха.
В тази схема ще бъде внесено точно едно допълнение в следващия параграф.
Идеи за правила за разделяне (бранчинг)
Нека обсъдим как да изберем върха, по която ще се извърши разделяне.
Основната идея е много ненаситна в алгоритмичен смисъл: нека вземем върха с максимална степен и да се разделим точно по нея. Защо изглежда, че това е по-добре? Защото във втората клонка на рекурсивното извикване по този начин ще премахнем много върхове. Може да се очаква, че остава малък граф и на него ще работим бързо.
Този подход с вече обсъдените прости техники за кернелизация показва добри резултати, решавайки някои тестове с размер в няколко хиляди върхове. Но, например, работи слабо за кубични графи (тоест графи, за които степента на всяка върха е равна на три).
Има още една идея, основана на доста проста мисъл: ако графът е несвързан, задачата за неговите компоненти на свързаност може да бъде решавана независимо, обединявайки отговорите в края. Това, между другото, е малка обещана модификация в схемата, която значително ще ускори решението: преди в такъв случай работехме за произведение на времената за отчитане на отговорите на компонентите, а сега работим за сума. А за ускоряване на бранчинга трябва да се превърне свързаният граф в несвързан.
Как да го направим? Ако в графа има точка на съединение, трябва да се бранчи точно по нея. Точката на съединение е върхът, при премахването на който графът губи свързаност. Всички точки на съединение в графа могат да бъдат намерени с класически алгоритъм за линейно време. Този подход значително ускорява бранченето.
При премахването на която и да е от маркираните върхове, графът ще се разпадне на компоненти на свързаност.
Ще го направим, но искам повече. Например, да търсим в графа малки върхови разрези и да извършваме разцепления по върховете от тях. Най-ефективният известен на мен начин да намеря минимален глобален върхов разрез е да използвам дървото на Гомори-Ху, което се изгражда за кубично време. В предизвикателството PACE типичният размер на графа е няколко хиляди върха. При такава ситуация всяко ниво на рекурсивното дърво трябва да извърши милиарди операции. Излиза, че е просто невъзможно да се реши задачата в зададеното време.
Нека опитаме да оптимизираме решението. Минималният върхов разрез между двойка върхове може да бъде намерен с всеки алгоритъм, който построява максимален поток. Можем да използваме , на практика той работи много бързо. Имам подозрение, че теоретично може да се докаже оценка на времето за работа 
, което вече е напълно приемливо.
Опитвах се няколко пъти да търся разрези между двойки случайни върхове и да взема най-сбалансирания. За съжаление, на откритите тестове в PACE Challenge това даде лоши резултати. Сравнявах с алгоритъм, който се опитваше по върховете с максимална степен, стартирайки го с ограничение на дълбочината на спуска. След алгоритъма, който опитваше да намери разрез по този начин, оставаха графи с по-голям размер. Това е свързано с факта, че разрезите се получаваха много несбалансирани: премахвайки 5-10 върха, успявахме да отделим само 15-20.
Трябва да се отбележи, че в статиите за теоретично най-бързите алгоритми се използват значително по-напреднали техники за избор на върхове за разцепление. Такива техники имат много сложна реализация и често слаби оценки по време и памет. Не успях да изведа от тях напълно приемливи за практиката.
Как да прилагаме правилата за опростяване
Вече имаме идеи за ядрени
- . Напомням: ако има изолиран връх, да го премахнем.
- Ако има връх от степен 1, премахнете го и вземете неговия съсед в отговора.
- Ако има връх от степен поне k + 1, вземете го в отговора.
С първите две всичко е ясно, с третата има една хитрост. Ако в шеговитата задача за бара ни беше дадено ограничение отгоре на k, то в PACE Challenge просто трябва да намерим върхово покритие с минимален размер. Това е типично преобразуване на задачи за търсене (Search Problem) в задачи за решение (Decision Problem), често между двата вида задачи не правят разлика. На практика, ако пишем решавач за проблема с върховото покритие, разликата може да бъде. Например, както в третия пункт.
От гледна точка на реализиране, можем да се справим по два начина. Първият подход се нарича Итеративно дълбочинно търсене. Той се състои в следното: можем да започнем с някакво разумно ограничение отдолу на отговора и след това да стартираме нашия алгоритъм, използвайки това ограничение като ограничение отгоре на отговора, без да слизаме в рекурсии по-дълбоко, отколкото на това ограничение. Ако сме намерили някакъв отговор, той е гарантирано оптимален, иначе можем да увеличим това ограничение с едно и отново да започнем.
Другият подход е да се съхранява някакъв текущ оптимален отговор и да се търси отговор с по-малък размер, при намиране променяйки този параметър k за по-добро отсяване на излишните клонки в търсенето.
След няколко нощни експерименти, аз се спрях на комбинация от тези два начина: първо стартирам алгоритъма си с някакво ограничение на дълбочината на търсене (подбирайки я така, че това да отнеме незначително време в сравнение с основното решение) и използвам най-доброто намерено решение като ограничение отгоре на отговора — тоест на онова k.
Върхове от степен 2
С върховете от степен 0 и 1 се оправихме. Оказва се, че това може да се направи и с върховете от степен 2, но за целта от графа ще са необходими по-сложни операции.
За да обясня, трябва по някакъв начин да обозначим върховете. Нека наречем върха от степен 2 връх v, а съседите му — върхове x и y. След това имаме два случая.
- Когато x и y — съседите. Тогава можем да вземем в отговора x и y, а v да премахнем. И наистина, от този триъгълник поне две върха трябва да се вземат в отговора и ние определено няма да загубим, ако вземем x и y: вероятно имат още съседи, а v те нямат.
- Когато x и y — не съседи. Тогава се заявява, че всички три върха могат да бъдат слепени в един. Идеята е, че в такъв случай има оптимален отговор, в който ще вземем или v, или и двата върха x и y. В първия случай ще трябва да вземем в отговора всички съседи x и y, а във втория не е задължително. Това точно съответства на случаите, когато не вземаме слепения връх в отговора и когато вземаме. Остава само да се отбележи, че в двата случая отговорът от такава операция намалява с единица.
Трябва да се отбележи, че такъв подход е доста сложно да се реализира прецизно за честно линейно време. Слепването на върхове е сложна операция, нужно е да се копират списъците със съседи. Ако това не се направи внимателно, може да се получи асимптотично неоптимално време за работа (например, ако след всяко слепване копирате много ръбове). Спирането ми на търсене на цялостни пътеки от върхове със степен 2 и разглеждане на множеството частни случаи, като цикли от такива върхове или от всички такива върхове освен един, остава.
Освен това, трябва да е възможно тази операция да бъде обратима, за да възстановим графа в първоначалния му вид по време на връщането от рекурсията. За да го осигуря, не почиствах списъците с ръбове на слетите върхове, след което просто знаех къде трябва да насочат ръбовете. Такава реализация на графите също изисква внимание, но осигурява честно линейно време. А за графи с няколко десетки хиляди ръбове, това се побира удобно в кеша на процесора, което предоставя големи предимства в скоростта.
Линейно ядро
Накрая, най-интересната част от ядрото.
Първо, нека си припомним, че в двудолни графи минималното върхово покритие може да се търси за 
. За целта е необходимо да се използва алгоритъм за да намерим там максималното паросъчетание, а след това да се възползваме от теоремата .
Идеята на линейното ядро е следната: на първо място, разделяме графа, тоест вместо всеки връх v въвеждаме два върха 
и 
, а вместо всеки ръб u — v въвеждаме два ръба 
и 
. Полученият граф ще бъде двудолен. Нека намерим минимално връхно покритие в него. Някои връхчета от изходния граф ще попаднат там два пъти, някои само веднъж, а някои — нито веднъж. Теоремата на Нимхаузер-Тротер твърди, че в такъв случай можем да премахнем върховете, които не са попаднали нито веднъж, и да вземем в отговор тези, които са попаднали два пъти. Освен това, тя казва, че от останалите върхове (тези, които са попаднали веднъж) трябва да вземем в отговор поне половината.
Току-що научихме да оставяме в графа не повече от 2k върхове. И наистина, ако в остатъка отговорът е поне половината от всички върхове, тогава там няма да има повече от 2k.
Тук успях да направя малка крачка напред. Ясно е, че построеното по този начин ядро зависи от това, кое конкретно минимално връхно покритие в двудолния граф сме взели. Иска се да вземем такова, за да бъде броят на останалите върхове минимален. Преди това това можеше да се прави само за време 
. Аз обаче измислих реализация на този алгоритъм за време 
, така че това ядро може да се търси в графи с хиляди върхове на всяка стъпка на бранчинг.
Резултат
Практиката показва, че моето решение работи добре на тестове с няколко стотици върхове и няколко хиляди ребра. На такива тестове е напълно разумно да се очаква, че решението ще бъде намерено за половин час. Вероятността да се намери отговор в приемливо време в принцип се увеличава, ако в графа има достатъчно много върхове с голяма степен, например с степен 10 и нагоре.
За участие в състезанието решенията трябва да бъдат изпратени на . Съдя по представената там , моето решение за отворените тестове заема трето място от двадесет с голямо изоставане от второто. Ако бъдем напълно честни, не е съвсем ясно как ще се оценяват решенията на самото състезание: например, моето решение преминава по-малко тестове от решението на четвърто място, но на онези, които преминава, работи по-бързо.
Резултатите от затворените тестове ще станат известни на първи юли.
Източник: habr.com
