Изследователската работа е може би най-интересната част от нашето обучение. Идеята е още докато сте в университета да се пробвате в избраната от вас посока. Например, студенти от областите на софтуерното инженерство и машинното обучение често отиват да правят проучвания в компании (основно JetBrains или Yandex, но не само).
В тази публикация ще говоря за моя проект по компютърни науки. Като част от работата си изучавах и приложих на практика подходи за решаване на един от най-известните NP-трудни проблеми: проблем с покриване на върхове.
В днешно време много бързо се развива интересен подход към NP-трудни проблеми - параметризирани алгоритми. Ще се опитам да ви ускоря, ще ви кажа някои прости параметризирани алгоритми и ще опиша един мощен метод, който ми помогна много. Представих резултатите си на състезанието PACE Challenge: според резултатите от откритите тестове моето решение заема трето място, а окончателните резултати ще бъдат известни на 1 юли.
За мен
Казвам се Василий Алферов, сега завършвам трета година в Националния изследователски университет Висше училище по икономика - Санкт Петербург. Интересувах се от алгоритми от ученическите си години, когато учих в московско училище № 179 и успешно участвах в олимпиади по информатика.
Краен брой специалисти по параметризирани алгоритми влизат в лентата...
Пример взет от книгата
Представете си, че сте охранител на бар в малък град. Всеки петък половината град идва във вашия бар, за да се отпусне, което ви създава много проблеми: трябва да изгоните буйните клиенти от бара, за да предотвратите битки. В крайна сметка ви писва и решавате да вземете превантивни мерки.
Тъй като вашият град е малък, вие знаете точно кои двойки посетители вероятно ще се сбият, ако се озоват заедно в бар. Имате ли списък с n хора, които ще дойдат в бара тази вечер. Решавате да държите някои жители на града извън бара, без никой да се бие. В същото време вашите шефове не искат да губят печалба и ще бъдат недоволни, ако не позволите повече от k хора.
За съжаление проблемът пред вас е класически NP-труден проблем. Може би я познавате като , или като проблем с покриване на връх. За такива проблеми в общия случай няма алгоритми, които да работят в приемливо време. За да бъдем точни, недоказаната и доста силна хипотеза ETH (Exponential Time Hypothesis) казва, че този проблем не може да бъде решен във времето , тоест не можете да измислите нищо забележимо по-добро от пълно търсене. Например, да приемем, че някой ще дойде във вашия бар п = 1000 Човек. Тогава ще бъде пълното търсене опции, които има приблизително - луда сума. За щастие вашето ръководство ви е дало лимит k = 10, така че броят на комбинациите, които трябва да повторите, е много по-малък: броят на подгрупите от десет елемента е . Това е по-добре, но все пак няма да се отчете за един ден дори на мощен клъстер.
За да елиминирате възможността за битка в тази конфигурация на обтегнати отношения между посетителите на бара, трябва да не допускате Боб, Даниел и Федор. Няма решение, при което да останат само двама.
Това означава ли, че е време да се предадете и да позволите на всички? Нека разгледаме други опции. Е, например, не можете да пуснете само онези, които има вероятност да се бият с много голям брой хора. Ако може някой да се бори поне със k+1 друг човек, тогава определено не можете да го пуснете вътре - в противен случай ще трябва да държите всички навън k+1 граждани, с които може да се бие, което определено ще разстрои ръководството.
Нека изхвърлите всички, които можете според този принцип. Тогава всички останали могат да се бият с не повече от k хората. Изхвърлянето им k човече, не можеш да предотвратиш нищо повече от конфликти. Това означава, че ако има повече от Ако човек участва в поне един конфликт, тогава със сигурност не можете да предотвратите всички. Тъй като, разбира се, определено ще допуснете напълно неконфликтни хора, трябва да преминете през всички подгрупи от размер десет от двеста души. Има приблизително и този брой операции вече могат да бъдат сортирани в клъстера.
Ако можете спокойно да вземете индивиди, които изобщо нямат конфликт, тогава какво ще кажете за тези, които участват само в един конфликт? Всъщност те също могат да бъдат пуснати, като затворят вратата пред опонента си. Всъщност, ако Алис е в конфликт само с Боб, тогава ако оставим Алис от тях двамата, няма да загубим: Боб може да има други конфликти, но Алис със сигурност няма такива. Освен това няма смисъл да не допускаме и двамата. След такива операции не остава нищо повече гости с неразрешена съдба: имаме само конфликти, всеки с по двама участници и всеки въвлечен в поне два. Така че всичко, което остава, е да сортирате опции, които лесно могат да бъдат разгледани половин ден на лаптоп.
Всъщност с прости разсъждения можете да постигнете още по-привлекателни условия. Имайте предвид, че определено трябва да разрешим всички спорове, тоест от всяка конфликтна двойка да изберете поне един човек, когото няма да допуснем. Нека разгледаме следния алгоритъм: вземем всеки конфликт, от който премахваме един участник и рекурсивно започваме от остатъка, след това премахваме другия и също започваме рекурсивно. Тъй като изхвърляме някого на всяка стъпка, рекурсивното дърво на такъв алгоритъм е двоично дърво на дълбочина k, така че като цяло алгоритъмът работи в Където n е броят на върховете и m - брой ребра. В нашия пример това са около десет милиона, които могат да бъдат изчислени за част от секундата не само на лаптоп, но дори и на мобилен телефон.
Горният пример е примерен параметризиран алгоритъм. Параметризираните алгоритми са алгоритми, които се изпълняват във времето f(k) поли(n)Където p - полином, f е произволна изчислима функция и k - някакъв параметър, който е много вероятно да бъде много по-малък от размера на проблема.
Всички разсъждения преди този алгоритъм дават пример ядреност е една от основните техники за създаване на параметризирани алгоритми. Кернализацията е намаляването на размера на проблема до стойност, ограничена от функция на параметър. Полученият проблем често се нарича ядро. По този начин, чрез просто разсъждение относно степените на върховете, получихме квадратично ядро за проблема с покритието на върховете, параметризирано от размера на отговора. Има други настройки, които можете да изберете за тази задача (като Vertex Cover Above LP), но това е настройката, която ще обсъдим.
Пейс предизвикателство
конкуренция (The Parameterized Algorithms and Computational Experiments Challenge) се роди през 2015 г., за да установи връзка между параметризирани алгоритми и подходи, използвани в практиката за решаване на изчислителни проблеми. Първите три състезания бяха посветени на намирането на дървовидната ширина на графика (), търсене на дърво на Щайнер () и търсене на набор от върхове, които изрязват цикли (). Тази година една от задачите, в които можехте да опитате ръката си, беше задачата за покриване на върха, описана по-горе.
Конкурсът набира популярност всяка година. Ако вярвате на предварителните данни, тази година 24 отбора участваха в състезанието за решаване на задачата за покриване на върха. Заслужава да се отбележи, че състезанието не продължава няколко часа или дори седмица, а няколко месеца. Екипите имат възможност да проучат литературата, да измислят своя оригинална идея и да се опитат да я реализират. По същество това състезание е изследователски проект. Успоредно с конференцията ще се проведат идеи за най-ефективни решения и награждаване на победителите (International Symposium on Parameterized and Exact Computation) като част от най-голямата годишна алгоритмична среща в Европа . По-подробна информация за самото състезание можете да намерите на , а резултатите от минали години лъжат .
Диаграма на решението
За да разреша проблема с покриването на върхове, опитах да използвам параметризирани алгоритми. Те обикновено се състоят от две части: правила за опростяване (които в идеалния случай водят до ядреност) и правила за разделяне. Правилата за опростяване са предварителна обработка на входа в полиномиално време. Целта на прилагането на такива правила е да се намали проблемът до еквивалентен по-малък проблем. Правилата за опростяване са най-скъпата част от алгоритъма и прилагането на тази част води до общото време за работа вместо просто полиномно време. В нашия случай правилата за разделяне се основават на факта, че за всеки връх трябва да вземете или него, или неговия съсед като отговор.
Общата схема е следната: прилагаме правилата за опростяване, след това избираме някакъв връх и правим две рекурсивни извиквания: в първото го вземаме в отговор, а в другото вземаме всичките му съседи. Това наричаме разделяне (разклоняване) по този връх.
Точно едно допълнение ще бъде направено към тази схема в следващия параграф.
Идеи за правила за разделяне (бранчиране).
Нека обсъдим как да изберем връх, по който ще се извърши разделянето.
Основната идея е много алчна в алгоритмичен смисъл: нека вземем връх с максимална степен и да го разделим. Защо изглежда по-добре? Тъй като във втория клон на рекурсивното извикване ще премахнем много върхове по този начин. Можете да разчитате, че остава малка графика и ние можем да работим по нея бързо.
Този подход, с вече обсъдените прости техники за кернелизация, се показва добре и решава някои тестове с размер от няколко хиляди върха. Но, например, не работи добре за кубични графи (т.е. графики, чиято степен на всеки връх е три).
Има друга идея, базирана на доста проста идея: ако графиката е несвързана, проблемът върху свързаните компоненти може да бъде решен независимо, комбинирайки отговорите в края. Това, между другото, е малка обещана модификация в схемата, която значително ще ускори решението: преди това, в този случай, работихме за произведението на времето за изчисляване на отговорите на компонентите, но сега работим за сумата. И за да ускорите разклоняването, трябва да превърнете свързан граф в несвързан.
Как да го направим? Ако има артикулационна точка в графиката, трябва да се биете за нея. Точката на артикулация е такъв връх, че когато се премахне, графиката губи своята свързаност. Всички точки на свързване в графика могат да бъдат намерени с помощта на класически алгоритъм в линейно време. Този подход значително ускорява разклоняването.
Когато някой от избраните върхове бъде премахнат, графиката ще се раздели на свързани компоненти.
Ще направим това, но искаме повече. Например, потърсете малки разфасовки на върхове в графиката и разделете върховете от нея. Най-ефективният начин, който познавам, за намиране на минималното глобално изрязване на върха е да се използва дърво Gomori-Hu, което е изградено в кубично време. В PACE Challenge типичният размер на графиката е няколко хиляди върха. В тази ситуация трябва да се извършат милиарди операции във всеки връх на рекурсивното дърво. Оказва се, че е просто невъзможно да се реши проблемът в определеното време.
Нека се опитаме да оптимизираме решението. Минималният върхов разрез между двойка върхове може да бъде намерен от всеки алгоритъм, който конструира максимален поток. Можете да го пуснете в такава мрежа , на практика работи много бързо. Имам подозрение, че теоретично е възможно да се докаже оценка за времето на работа , което вече е съвсем приемливо.
Опитах няколко пъти да търся срезове между двойки произволни върхове и да взема най-балансирания. За съжаление това доведе до лоши резултати при отвореното тестване на PACE Challenge. Сравних го с алгоритъм, който разделя върховете на максимална степен, като ги изпълнява с ограничение на дълбочината на спускане. Алгоритъм, опитващ се да намери разрез по този начин, остави след себе си по-големи графики. Това се дължи на факта, че разфасовките се оказаха много небалансирани: след като бяха премахнати 5-10 върха, беше възможно да се отцепят само 15-20.
Струва си да се отбележи, че статиите за теоретично най-бързите алгоритми използват много по-напреднали техники за избор на върхове за разделяне. Такива техники имат много сложно изпълнение и често лошо представяне по отношение на времето и паметта. Не успях да идентифицирам тези, които са напълно приемливи за практиката.
Как да прилагаме правилата за опростяване
Вече имаме идеи за кернализация. Нека ви напомня:
- Ако има изолиран връх, изтрийте го.
- Ако има връх от степен 1, премахнете го и вземете неговия съсед в отговор.
- Ако има поне връх на степен k+1, Вземи го обратно.
С първите две всичко е ясно, с третата има един трик. Ако в комичен проблем за бар ни беше дадена горна граница от k, тогава в PACE Challenge просто трябва да намерите покритие на върха с минимален размер. Това е типична трансформация на проблемите с търсенето в проблеми с вземането на решения; често няма разлика между двата вида проблеми. На практика, ако пишем решаващ проблем за покриване на върхове, може да има разлика. Например, както в трета точка.
От гледна точка на изпълнението има два начина да се продължи. Първият подход се нарича Итеративно задълбочаване. Това е както следва: можем да започнем с някакво разумно ограничение отдолу на отговора и след това да изпълним нашия алгоритъм, използвайки това ограничение като ограничение на отговора отгоре, без да слизаме по-ниско в рекурсията от това ограничение. Ако сме намерили някакъв отговор, той гарантирано е оптимален, в противен случай можем да увеличим тази граница с единица и да започнем отначало.
Друг подход е да съхраните някакъв текущ оптимален отговор и да потърсите по-малък отговор, променяйки този параметър, когато бъде намерен 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 и по-висока.
За участие в състезанието трябваше да се изпратят решения на . Съдейки по представената там информация , моето решение в отворени тестове се класира на трето място от двадесет, с голяма разлика от второто. Честно казано, не е съвсем ясно как ще се оценяват решенията на самото състезание: например моето решение преминава по-малко тестове от решението на четвърто място, но на тези, които преминават, работи по-бързо.
Резултатите от затворените тестове ще станат известни на XNUMX юли.
Източник: www.habr.com