Навукова-даследчая праца, бадай, самая цікавая частка нашага навучання. Ідэя ў тым, каб яшчэ ва ўніверсітэце паспрабаваць сябе ў абраным напрамку. Напрыклад, студэнты з напрамкаў Software Engineering і Machine Learning часта ідуць рабіць НДР ў кампаніі (у асноўным, JetBrains або Яндэкс, але не толькі).
У гэтым пасце я распавяду аб сваім праекце па кірунку Computer Science. У рамках працы я вывучыў і рэалізаваў на практыцы падыходы да рашэння адной з самых вядомых NP-цяжкіх задач: задачы аб вяршынным пакрыцці.
Цяпер вельмі хутка развіваецца цікавы падыход да NP-цяжкім задачам - параметрызаваныя алгарытмы. Я пастараюся ўвесці вас у курс справы, расказаць некалькі простых параметрызаваных алгарытмаў і апісаць адзін магутны метад, які вельмі мне дапамог. Свой вынікі я прадставіў на спаборніцтве PACE Challenge: па выніках адчыненых тэстаў маё рашэнне займае трэцяе месца, а канчатковыя вынікі будуць вядомыя 1 ліпеня.
Пра сябе
Мяне клічуць Васіль Алфёраў, я зараз заканчваю трэці курс НДУ УШЭ – Санкт-Пецярбург. Алгарытмамі я захапляюся яшчэ са школьных часоў, калі вучыўся ў маскоўскай 179 школе і паспяхова ўдзельнічаў у алімпіядах па інфарматыцы.
Канчатковая колькасць спецыялістаў па параметрызаваных алгарытмах заходзяць у бар…
Прыклад узяты з кнігі
Уявіце, што вы - ахоўнік бара ў невялікім горадзе. Кожную пятніцу палова горада прыходзіць у ваш бар паслабіцца, што дастаўляе вам нямала клопатаў: трэба выкідваць з бара буйных наведвальнікаў, каб не дапусціць боек. У рэшце рэшт, вам гэта надакучае і вы вырашаеце прыняць прэвентыўныя меры.
Бо горад у вас маленькі, вы сапраўды ведаеце, якія пары наведвальнікаў з вялікай верагоднасцю перабяруцца, калі патрапяць у бар разам. У вас ёсць спіс з n чалавек, якія прыйдуць сёння ўвечары ў бар. Вы вырашаеце не пусціць у бар якіх-небудзь гараджан такім чынам, каб ніхто не пабіўся. У той жа час ваша начальства не хоча губляць прыбытак і будзе незадаволена, калі вы не пусціце ў бар больш, чым k чалавек.
Нажаль, задача, стаялая перад вамі - класічная NP-цяжкая задача. Вы маглі ведаць яе як , або як задачу аб вяршыні пакрыцці. Для такіх задач у агульным выпадку невядомыя алгарытмы, якія працуюць за прымальны час. Калі быць дакладным, то недаказаная і даволі моцная гіпотэза ETH (Exponential Time Hypothesis) кажа, што гэтая задача не вырашаецца за час. , гэта значыць што прыкметна лепш поўнага перабору нічога нельга прыдумаць. Напрыклад, няхай да вас у бар збіраецца прыйсці N = 1000 чалавек. Тады поўны перабор складзе варыянтаў, што ёсць прыкладна - вар'яцка многа. На шчасце, ваша кіраўніцтва паставіла вам абмежаванне k = 10, так што колькасць камбінацый, якія вам трэба перабраць, значна менш: колькасць падмноства з дзесяці элементаў роўна . Гэта ўжо лепш, але ўсё роўна не далічыцца за дзень нават на магутным кластары.
Каб выключыць верагоднасць бойкі пры такой канфігурацыі нацягнутых адносін паміж наведвальнікамі бара, трэба не ўпускаць Боба, Дэніэла і Фёдара. Рашэння, пры якім за бортам застануцца ўсяго двое, не існуе.
Ці значыць гэта, што час здацца і ўпусціць усіх? Разгледзім іншыя варыянты. Ну, напрыклад, можна не ўпусціць толькі тых, хто верагодна паб'ецца з вельмі вялікай колькасцю народа. Калі хтосьці можа пабіцца хаця б з да + 1 іншым чалавекам, то яго сапраўды пускаць нельга - інакш прыйдзецца не пусціць усіх да + 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, выдаліць яе і ўзяць яе суседа ў адказ.
- Калі ёсць вяршыня ступені хаця б да + 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