Науково-дослідницька робота, мабуть, найцікавіша частина нашого навчання. Ідея в тому, щоб ще в університеті спробувати себе у вибраному напрямі. Наприклад, студенти з напрямків Software Engineering та Machine Learning часто йдуть робити НДРи в компанії (в основному, JetBrains або Яндекс, але не тільки).
У цьому пості я розповім про свій проект у напрямку Computer Science. В рамках роботи я вивчив і реалізував на практиці підходи до вирішення одного з найвідоміших NP-важких завдань: задачі про вершинне покриття.
Наразі дуже швидко розвивається цікавий підхід до NP-важких завдань – параметризовані алгоритми. Я намагатимусь ввести вас у курс справи, розповісти кілька простих параметризованих алгоритмів та описати один потужний метод, який дуже мені допоміг. Свій результат я представив на змаганні PACE Challenge: за підсумками відкритих тестів, моє рішення посідає третє місце, а остаточні результати будуть відомі 1 липня.
Про себе
Мене звуть Василь Алферов, я зараз закінчую третій курс НДУ ВШЕ – Санкт-Петербург. Алгоритмами я захоплююся ще зі шкільних часів, коли навчався в московській школі і успішно брав участь в олімпіадах з інформатики.
Кінцева кількість фахівців за параметризованими алгоритмами заходять у барі.
Приклад взято з книги
Уявіть, що ви охоронець бару в невеликому місті. Щоп'ятниці половина міста приходить до вашого бару розслабитися, що завдає вам чимало турбот: потрібно викидати з бару буйних відвідувачів, щоб не допустити бійок. Зрештою, вам це набридає і ви вирішуєте вжити превентивних заходів.
Так як місто у вас маленьке, ви точно знаєте, які пари відвідувачів з великою ймовірністю переберуться, якщо потраплять у бар разом. У вас є список з n людина, які прийдуть сьогодні ввечері в барі. Ви вирішуєте не пустити в бар якихось городян таким чином, щоб ніхто не бився. У той же час, ваше начальство не хоче втрачати прибуток і буде невдоволено, якщо ви не пустите в бар більше ніж k чоловік.
На жаль, завдання, яке стоїть перед вами, — класичне NP-важке завдання. Ви могли знати її як , або як завдання про вершинне покриття. Для таких завдань у загальному випадку невідомі алгоритми, які працюють за прийнятний час. Якщо бути точним, то недоведена та досить сильна гіпотеза ETH (Exponential Time Hypothesis) каже, що це завдання не вирішується за час , тобто що помітно краще за повний перебір нічого не можна придумати. Наприклад, нехай до вас у бар збирається прийти 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
змагання (The Parameterized Algorithms and Computational Experiments Challenge) зародилося у 2015 році, щоб встановити зв'язок між параметризованими алгоритмами та підходами, які використовуються на практиці для вирішення обчислювальних завдань. Перші три змагання були присвячені пошуку деревної ширини графа (), пошуку дерева Штейнера () та пошуку безлічі вершин, що розрізає цикли (). Цього року одним із завдань, у яких можна було спробувати свої сили, було описане вище завдання про вершинне покриття.
Змагання з кожним роком набирає популярності. Якщо вірити попереднім даним, то цього року лише у змаганні з вирішення завдання вершинного покриття взяло участь 24 команди. Варто зазначити, що змагання триває не кілька годин і навіть не тиждень, а кілька місяців. У команд є можливість вивчити літературу, вигадати свою оригінальну ідею і спробувати її реалізувати. Насправді, це змагання являє собою дослідницьку роботу. Ідеї найефективніших рішень та нагородження переможців пройде спільно з конференцією (International Symposium on Parameterized and Exact Computation) у рамках найбільших щорічних алгоритмічних зборів у Європі . Більш детальну інформацію про саме змагання можна знайти на , а результати минулих років лежать .
Схема розв'язання
Щоб упоратися із завданням про вершинне покриття, я спробував застосувати параметризовані алгоритми. Вони, як правило, складаються з двох частин: правил спрощення (які в ідеалі призводять до керналізації) та правил розщеплення. Правила спрощення – це передобробка входу за поліноміальний час. Мета застосування таких правил - зведення завдання до еквівалентного завдання меншого розміру. Правила спрощення — це найбільш витратна частина алгоритму, і застосування цієї частини веде до загального часу роботи замість простого поліноміального часу У нашому випадку правила розщеплення засновані на тому, що для кожної вершини необхідно взяти у відповідь або її, або її сусіда.
Загальна схема така: застосовуємо правила спрощення, потім вибираємо якусь вершину, і робимо два рекурсивні виклики: у першому ми беремо її у відповідь, а в іншому ми беремо всіх її сусідів. Це ми називаємо розщепитися (бранчитися) по цій вершині.
У цю схему буде внесено одне доповнення в наступному параграфі.
Ідеї для правил розщеплення (бранчінг)
Давайте обговоримо, як вибрати вершину, за якою відбуватиметься розщеплення.
Основна ідея дуже жадібна в алгоритмічному сенсі: давайте візьмемо вершину максимального ступеня і розщепимося саме по ній. Чому здається, що так краще? Тому що у другій гілці рекурсивного виклику ми таким чином заберемо дуже багато вершин. Можна розраховувати, що залишиться маленький граф і ми відпрацюємо швидко.
Цей підхід із вже обговореними простими техніками керналізації показує себе непогано, вирішує якісь тести розміром кілька тисяч вершин. Але, наприклад, погано працює для кубічних графів (тобто графів, ступінь кожної вершини яких дорівнює трьом).
Є ще одна ідея, заснована на досить простій думці: якщо граф нескладний, завдання на його компонентах зв'язності можна вирішувати незалежно, об'єднавши відповіді наприкінці. Це, до речі, і є невелика обіцяна модифікація у схемі, яка суттєво прискорить рішення: раніше у такому разі ми працювали за добуток часів підрахунку відповідей компонент, а тепер працюємо за суму. А для прискорення бранчінга потрібно перетворити зв'язковий граф на незв'язний.
Як це зробити? Якщо в графі є точка зчленування, потрібно побратися саме за нею. Точка зчленування - це така вершина, при видаленні якої граф втрачає зв'язність. Знайти у графі всі точки зчленування можна класичним алгоритмом за лінійний час. Такий підхід помітно прискорює бранчінг.
При видаленні будь-якої з виділених вершин граф розпадеться на компоненти зв'язності.
Це ми зробимо, але хочеться більшого. Наприклад, шукати у графі невеликі вершинні розрізи та проводити розщеплення по вершинах з нього. Найефективніший мені відомий спосіб знайти мінімальний глобальний вершинний розріз — скористатися деревом Гоморі-Ху, яке будується за кубічний час. У PACE Challenge типовий розмір графа – кілька тисяч вершин. За такого розкладу в кожній вершині дерева рекурсії потрібно виконати мільярди операцій. Виходить, що розв'язати завдання за відведений час просто неможливо.
Спробуємо оптимізувати рішення. Мінімальний вершинний розріз між парою вершин можна знайти будь-яким алгоритмом, який будує максимальний потік. Можна напустити на таку мережу , На практиці він працює дуже швидко. У мене є підозра, що теоретично можна довести оцінку на час роботи що вже цілком прийнятно.
Я пробував кілька разів шукати розрізи між парами випадкових вершин та брати з них найзбалансованіший. На жаль, на відкритих тестах PACE Challenge це дало погані результати. Я порівнював з алгоритмом, що прививався по вершинах максимального ступеня, запускаючи їх з обмеженням на глибину спуску. Після алгоритму, який намагається знайти розріз таким чином, залишалися графи більшого розміру. Це пов'язано з тим, що розрізи виходили дуже незбалансованими: видаливши 5-10 вершин, вдавалося відщеплювати лише 15-20.
Варто зауважити, що у статтях про теоретично найшвидші алгоритми використовуються набагато більш просунуті техніки вибору вершин для розщеплення. Такі техніки мають дуже складну реалізацію і найчастіше погані оцінки за часом та пам'яттю. Мені не вдалося виділити з них цілком прийнятні для практики.
Як застосовувати правила спрощення
У нас вже є ідеї керналізації. Нагадаю:
- Якщо є ізольована вершина видалити її.
- Якщо є вершина ступеня 1, видалити її та взяти її сусіда у відповідь.
- Якщо є вершина ступеня хоча б k+1взяти її у відповідь.
З першими двома все зрозуміло, з третьої є одна хитрість. Якщо в жартівливому завданні про бар нам було дано обмеження зверху на k, то PACE Challenge треба просто знайти вершинне покриття мінімального розміру. Це типове перетворення завдань пошуку (Search Problem) на завдання розв'язання (Decision Problem), часто між двома видами задач не роблять різниці. На практиці, якщо ми пишемо вирішувач завдання про вершинне покриття, різниця може бути. Наприклад, як у третьому пункті.
З погляду реалізації, можна надійти двома способами. Перший підхід називається Iterative Deepening. Він полягає в наступному: ми можемо почати з якогось розумного обмеження знизу на відповідь, і далі запускати наш алгоритм, використовуючи це обмеження як обмеження відповіді зверху, не спускаючись у рекурсії нижче, ніж це обмеження. Якщо ми знайшли якусь відповідь, вона гарантовано оптимальна, інакше ж можна збільшити це обмеження на одиницю і знову запуститися.
Інший підхід - зберігати якусь поточну оптимальну відповідь і шукати відповідь меншого розміру, знаходячи змінюючи цей параметр 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