Како да се решат НП-тешки проблеми со параметриизирани алгоритми

Истражувачката работа е можеби најинтересниот дел од нашата обука. Идејата е да се обидете во вашата избрана насока додека сте на универзитет. На пример, студентите од областите на софтверско инженерство и машинско учење често одат да истражуваат во компании (главно JetBrains или Yandex, но не само).

Во овој пост ќе зборувам за мојот проект во компјутерски науки. Како дел од мојата работа, проучував и применував пристапи за решавање на еден од најпознатите НП-тешки проблеми: проблем со покривање на темето.

Во денешно време многу брзо се развива интересен пристап кон NP-тврдите проблеми - параметризирани алгоритми. Ќе се обидам да ве доведам до брзина, да ви кажам неколку едноставни параметриизирани алгоритми и да опишам еден моќен метод кој многу ми помогна. Моите резултати ги претставив на натпреварот PACE Challenge: според резултатите од отворените тестови, моето решение го зазема третото место, а конечните резултати ќе бидат познати на 1 јули.

Изјава

Јас се викам Василиј Алферов, сега ја завршувам третата година на високото економско училиште за Националниот истражувачки универзитет - Санкт Петербург. За алгоритмите ме интересираат уште од моите училишни денови, кога учев во московското училиште бр. 179 и успешно учествував на олимпијадите по информатика.

Конечен број специјалисти за параметриизирани алгоритми влегуваат во лентата...

Пример земен од книгата „Параметризирани алгоритми“

Замислете дека сте чувар во бар во мал град. Секој петок, половина град доаѓа во вашиот бар да се опушти, што ви создава многу проблеми: треба да ги исфрлите бурните клиенти од барот за да спречите тепачки. На крајот, се заситувате и одлучувате да преземете превентивни мерки.

Бидејќи вашиот град е мал, точно знаете кои парови патрони веројатно ќе се тепаат ако завршат заедно во кафеана. Дали имате листа на n луѓе кои ќе дојдат вечерва во кафеана. Решиш да држиш некои градски жители надвор од барот без никој да се кара. Во исто време, вашите шефови не сакаат да губат профит и ќе бидат несреќни ако не дозволите повеќе од k луѓе.

За жал, проблемот пред вас е класичен НП-тврд проблем. Можеби ја познавате како Теме Покривка, или како проблем што го покрива темето. За вакви проблеми, во општиот случај, нема алгоритми кои работат во прифатливо време. Да бидеме прецизни, недокажаната и прилично силна хипотеза ETH (Exponential Time Hypothesis) вели дека овој проблем не може да се реши навреме , односно, не можете да смислите ништо значително подобро од целосно пребарување. На пример, да речеме дека некој ќе дојде во вашиот бар n = 1000 Човечки. Тогаш ќе биде целосното пребарување опции што ги има приближно - луда количина. За среќа, вашето раководство ви даде ограничување k = 10, така што бројот на комбинации што треба да ги повторувате е многу помал: бројот на подмножества од десет елементи е . Ова е подобро, но сепак нема да се смета за еден ден дури и на моќен кластер.

За да ја елиминирате можноста за тепачка во оваа конфигурација на затегнати односи меѓу посетителите на барот, треба да ги држите Боб, Даниел и Федор надвор. Нема решение во кое само двајца ќе останат зад себе.

Дали ова значи дека е време да попуштите и да ги пуштиме сите да влезат? Ајде да разгледаме други опции. Па, на пример, не можете да ги пуштите само оние кои најверојатно ќе се борат со многу голем број луѓе. Ако некој може да се бори барем со к + 1 друго лице, тогаш дефинитивно не можете да го пуштите - во спротивно ќе мора да ги држите сите надвор к + 1 жители на градот, со кои може да се бори, што дефинитивно ќе го вознемири раководството.

Дозволете да ги исфрлите сите што можете според овој принцип. Тогаш сите други можат да се борат со не повеќе од k луѓе. Исфрлајќи ги надвор k човече, не можеш да спречиш ништо повеќе од конфликти. Тоа значи дека ако има повеќе од Ако некое лице е вклучено во барем еден конфликт, тогаш сигурно не можете да ги спречите сите. Бидејќи, се разбира, дефинитивно ќе пуштите целосно неконфликтни луѓе, треба да ги поминете сите подмножества со големина десет од двесте луѓе. Има приближно , и овој број на операции веќе може да се подреди на кластерот.

Ако можете безбедно да земете поединци кои воопшто немаат конфликт, тогаш што е со оние кои учествуваат само во еден конфликт? Всушност, тие можат да бидат пуштени и со затворање на вратата на противникот. Навистина, ако Алис е во конфликт само со Боб, тогаш ако ја пуштиме Алис од нив двајца, нема да изгубиме: Боб може да има други конфликти, но Алис сигурно ги нема. Згора на тоа, нема смисла да не дозволиме и двајцата да влеземе. По ваквите операции нема повеќе гости со нерешена судбина: имаме само конфликти, секој со двајца учесници и секој вклучен во најмалку двајца. Значи, останува само да се среди опции, кои лесно може да се сметаат за половина ден на лаптоп.

Всушност, со едноставно расудување можете да постигнете уште поатрактивни услови. Забележете дека дефинитивно треба да ги решиме сите спорови, односно од секој конфликтен пар да избереме барем една личност која нема да ја пуштиме. Да го разгледаме следниов алгоритам: земеме каков било конфликт, од кој отстрануваме еден учесник и рекурзивно започнуваме од остатокот, потоа го отстрануваме другиот и исто така започнуваме рекурзивно. Бидејќи исфрламе некого на секој чекор, рекурзивното дрво на таков алгоритам е бинарно дрво на длабочина k, така што вкупно алгоритмот работи во каде n е бројот на темиња, и m - број на ребра. Во нашиот пример, ова е околу десет милиони, што може да се пресмета во дел од секунда не само на лаптоп, туку дури и на мобилен телефон.

Горенаведениот пример е пример параметризиран алгоритам. Параметризирани алгоритми се алгоритми кои работат во времето f(k) поли(n)каде p - полином, f е произволна пресметлива функција и k - некој параметар, кој, сосема веројатно, ќе биде многу помал од големината на проблемот.

Сите расудувања пред овој алгоритам даваат пример кернелизација е една од општите техники за креирање параметризирани алгоритми. Кернелизација е намалување на големината на проблемот до вредност ограничена со функција на параметар. Резултирачкиот проблем често се нарекува кернел. Така, со едноставно расудување за степените на темињата, добивме квадратно јадро за проблемот Vertex Cover, параметрирано според големината на одговорот. Постојат и други поставки што можете да ги изберете за оваа задача (како Vertex Cover Above LP), но ова е поставката за која ќе разговараме.

Темпото предизвик

Конкуренција PACE предизвик (The Parameterized Algorithms and Computational Experiments Challenge) е роден во 2015 година за да се воспостави врска помеѓу параметризираните алгоритми и пристапите кои се користат во пракса за решавање на пресметковните проблеми. Првите три натпревари беа посветени на наоѓање на ширината на дрвото на графиконот (Ширина на дрвото), во потрага по дрво Штајнер (Штајнер дрво) и пребарување на множество темиња што ги сечат циклусите (Повратни информации Теме Комплет). Оваа година, еден од проблемите во кои можевте да се обидете беше проблемот со покривање на темето опишан погоре.

Конкуренцијата добива популарност секоја година. Ако им верувате на прелиминарните податоци, оваа година 24 тима учествуваа во натпреварот само за решавање на проблемот со покривање на темето. Вреди да се напомене дека натпреварот не трае неколку часа, па дури и една недела, туку неколку месеци. Тимовите имаат можност да ја проучуваат литературата, да дојдат до своја оригинална идеја и да се обидат да ја имплементираат. Во суштина, овој натпревар е истражувачки проект. Заедно со конференцијата ќе се одржат идеи за најефикасни решенија и наградување на победниците ИПЕК (Меѓународен симпозиум за параметризирана и точна пресметка) како дел од најголемиот годишен алгоритамски состанок во Европа Algo. Подетални информации за самиот натпревар можете да најдете на Онлајн, а резултатите од претходните години лажат тука.

Дијаграм за решение

За да го решам проблемот со покривање на темето, се обидов да користам параметриизирани алгоритми. Тие обично се состојат од два дела: правила за поедноставување (кои идеално водат до кернелизација) и правила за разделување. Правилата за поедноставување се претходна обработка на влезот во полиномско време. Целта на примената на таквите правила е да се намали проблемот на еквивалентен помал проблем. Правилата за поедноставување се најскапиот дел од алгоритмот, а примената на овој дел води до вкупното време на работа наместо едноставно полиномско време. Во нашиот случај, правилата за разделување се засноваат на фактот дека за секое теме треба да го земете или него или неговиот сосед како одговор.

Општата шема е следна: ги применуваме правилата за поедноставување, потоа избираме некое теме и правиме два рекурзивни повици: во првиот го земаме како одговор, а во другиот ги земаме сите негови соседи. Ова е она што ние го нарекуваме разделување (разгранување) по ова теме.

Во следниот пасус ќе се направи точно едно дополнување на оваа шема.

Идеи за разделување (brunching) правила

Ајде да разговараме како да избереме теме по кое ќе се случи разделувањето.
Главната идеја е многу алчна во алгоритамска смисла: да земеме теме со максимален степен и да се поделиме по него. Зошто изгледа подобро? Бидејќи во втората гранка на рекурзивниот повик ќе отстраниме многу темиња на овој начин. Може да сметате на мал графикон што ќе остане и ние брзо ќе работиме на него.

Овој пристап, со веќе дискутираните едноставни техники за кернелизација, добро се покажува и решава некои тестови со големина од неколку илјади темиња. Но, на пример, не работи добро за кубни графикони (т.е. графикони чиј степен на секое теме е три).
Постои уште една идеја заснована на прилично едноставна идеја: ако графикот е исклучен, проблемот на неговите поврзани компоненти може да се реши независно, комбинирајќи ги одговорите на крајот. Ова, инаку, е мала ветена модификација во шемата, која значително ќе го забрза решението: претходно, во овој случај, работевме за производот на времињата за пресметување на одговорите на компонентите, но сега работиме за збирот. И за да го забрзате разгранувањето, треба да претворите поврзан график во исклучен.

Како да се направи тоа? Ако има точка на артикулација на графиконот, треба да се борите за тоа. Точката на артикулација е теме такво што кога ќе се отстрани, графикот ја губи својата поврзаност. Сите точки на спојување во графикот може да се најдат со користење на класичен алгоритам во линеарно време. Овој пристап значително го забрзува разгранувањето.

Кога ќе се отстрани кое било од избраните темиња, графикот ќе се подели на поврзани компоненти.

Ќе го направиме ова, но сакаме повеќе. На пример, побарајте мали исечоци на темето во графикот и поделете по темињата од него. Најефикасниот начин на кој знам да го најдам минималното глобално теме е да користам дрво Gomori-Hu, кое е изградено во кубно време. Во предизвикот PACE, типичната големина на графикот е неколку илјади темиња. Во оваа ситуација, треба да се извршат милијарди операции на секое теме на рекурзивното дрво. Излегува дека е едноставно невозможно да се реши проблемот во даденото време.

Ајде да се обидеме да го оптимизираме решението. Минималниот пресек на теме помеѓу пар темиња може да се најде со кој било алгоритам што конструира максимален проток. Можете да го пуштите на таква мрежа Диниц алгоритам, во пракса делува многу брзо. Имам сомневање дека теоретски е можно да се докаже проценка за времето на работа , што е веќе сосема прифатливо.

Се обидов неколку пати да барам пресеци помеѓу парови случајни темиња и да го земам најбалансираното. За жал, ова даде лоши резултати во отвореното тестирање на PACE Challenge. Го споредив со алгоритам кој ги дели темињата со максимален степен, извршувајќи ги со ограничување на длабочината на спуштањето. Алгоритам кој се обидува да најде рез на овој начин остави зад себе поголеми графикони. Ова се должи на фактот дека исечоците се покажаа како многу неурамнотежени: откако беа отстранети 5-10 темиња, беше можно да се поделат само 15-20.

Вреди да се напомене дека статиите за теоретски најбрзите алгоритми користат многу понапредни техники за избор на темиња за разделување. Ваквите техники имаат многу сложена имплементација и често слаби перформанси во однос на времето и меморијата. Не можев да ги идентификувам оние кои се сосема прифатливи за пракса.

Како да се применат правилата за поедноставување

Веќе имаме идеи за кернелизација. Да те потсетам:

1. Ако има изолирано теме, избришете го.
2. Ако има теме од степен 1, отстранете го и земете го неговиот сосед како одговор.
3. Ако има теме од степен барем к + 1, земи го назад.

Со првите две се е јасно, со третиот има една финта. Ако во комичен проблем за кафеана ни беше дадена горна граница на k, тогаш во PACE Challenge треба само да најдете теме капак со минимална големина. Ова е типична трансформација на проблемите за пребарување во проблеми со одлучување; честопати нема разлика помеѓу двата типа проблеми. Во пракса, ако пишуваме решавач за проблемот со покривање на темето, може да има разлика. На пример, како во третата точка.

Од гледна точка на имплементација, постојат два начина да се продолжи. Првиот пристап се нарекува Итеративно продлабочување. Тоа е како што следува: можеме да започнеме со некое разумно ограничување од долу за одговорот, а потоа да го извршиме нашиот алгоритам користејќи го ова ограничување како ограничување на одговорот одозгора, без да одиме пониско во рекурзија од ова ограничување. Ако најдовме некој одговор, гарантирано е дека ќе биде оптимален, во спротивно можеме да ја зголемиме оваа граница за еден и да започнеме повторно.

Друг пристап е да се складира некој моментален оптимален одговор и да се бара помал одговор, менувајќи го овој параметар кога ќе се најде k за поголемо отсекување на непотребните гранки при пребарувањето.

Откако спроведов неколку ноќни експерименти, се решив на комбинација од овие два методи: прво, го извршувам мојот алгоритам со некаков вид ограничување на длабочината на пребарувањето (избирајќи го така што ќе одземе занемарливо време во споредба со главното решение) и го користам најдоброто. решение најдено како горна граница на одговорот - односно на истото k.

Темиња од степен 2

Се занимававме со темиња од степен 0 и 1. Излегува дека тоа може да се направи со темиња од степен 2, но за тоа ќе бидат потребни посложени операции од графикот.

За да го објасниме ова, треба некако да ги означиме темињата. Темето од степен 2 да го наречеме теме v, и неговите соседи - темиња x и y. Следно ќе имаме два случаи.

1. Кога x и y - соседи. Потоа можете да одговорите x и yИ v избриши. Навистина, од овој триаголник треба да се земат најмалку две темиња за возврат и дефинитивно нема да изгубиме ако земеме x и y: веројатно имаат и други соседи, и v Тие не се тука.
2. Кога x и y - не соседи. Потоа се наведува дека сите три темиња можат да се залепат во едно. Идејата е дека во овој случај постои оптимален одговор, во кој земаме или v, или двете темиња x и y. Покрај тоа, во првиот случај ќе треба да ги земеме сите соседи како одговор x и y, но во втората не е потребно. Ова точно одговара на случаите кога не го земаме залепениот теме како одговор и кога го правиме тоа. Останува само да се забележи дека и во двата случаи одговорот од таквата операција се намалува за еден.

Вреди да се напомене дека овој пристап е доста тешко прецизно да се имплементира во фер линеарно време. Лепењето темиња е сложена операција; треба да копирате списоци на соседи. Ако ова е направено безгрижно, може да завршите со асимптотично неоптимално време на работа (на пример, ако копирате многу рабови по секое лепење). Се решив да најдам цели патеки од темиња од степен 2 и да анализирам еден куп посебни случаи, како што се циклуси од такви темиња или од сите такви темиња освен едно.

Дополнително, неопходно е оваа операција да биде реверзибилна, така што при враќање од рекурзија го враќаме графикот во првобитната форма. За да го осигурам ова, не ги исчистив листите на рабовите од споените темиња, а потоа само знаев кои рабови треба да одат каде. Оваа имплементација на графикони бара и точност, но обезбедува прилично линеарно време. И за графикони од неколку десетици илјади рабови, се вклопува во кешот на процесорот, што дава големи предности во брзината.

Линеарно јадро

Конечно, најинтересниот дел од кернелот.

За почеток, потсетете се дека во бипартитните графикони минималната покривка на темето може да се најде со користење . За да го направите ова, треба да го користите алгоритмот Хопкрофт-Карп со цел да се најде максималното совпаѓање таму, а потоа да се користи теоремата Кениг-Егервари.

Идејата за линеарно јадро е оваа: прво го бифурцираме графикот, односно наместо секое теме v да додадеме два врва и , и наместо секој раб u - v да додадеме две ребра и . Резултирачкиот графикон ќе биде бипартитен. Дозволете ни да ја најдеме минималната покривка на темето во неа. Некои темиња на оригиналниот график ќе стигнат таму двапати, некои само еднаш, а некои никогаш. Теоремата Немхаузер-Тротер вели дека во овој случај може да се отстранат темињата што не погодиле ниту еднаш и да се вратат оние што удриле двапати. Згора на тоа, таа вели дека од преостанатите темиња (оние што удираат еднаш) треба да земете барем половина како одговор.

Штотуку научивме да оставиме не повеќе од 2k врвови Навистина, ако преостанатиот одговор е барем половина од сите темиња, тогаш нема вкупно повеќе темиња од 2k.

Тука можев да направам мал чекор напред. Јасно е дека јадрото конструирано на овој начин зависи од тоа каков вид на минимално теме покривање сме го земале во бипартитниот график. Би сакал да земам едно, така што бројот на преостанатите темиња е минимален. Претходно, тие можеа да го направат тоа само на време . Во тоа време смислив имплементација на овој алгоритам , на тој начин, ова јадро може да се бара во графикони од стотици илјади темиња во секоја фаза на разгранување.

Резултира

Практиката покажува дека моето решение работи добро на тестови од неколку стотици темиња и неколку илјади рабови. Во ваквите тестови сосема е можно да се очекува дека решението ќе се најде за половина час. Веројатноста да се најде одговор во прифатливо време, во принцип, се зголемува ако графикот има доволно голем број темиња со висок степен, на пример, степен 10 и повисок.

За учество на натпреварот требаше да се испратат решенија до optil.io. Судејќи според информациите презентирани таму знак, моето решение во отворените тестови е на третото место од дваесет, со голема разлика од второто. Да бидам целосно искрен, не е сосема јасно како ќе се оценуваат решенијата на самиот натпревар: на пример, моето решение поминува помалку тестови од решението на четвртото место, но на оние што поминуваат, тоа функционира побрзо.

Резултатите од затворените тестови ќе бидат познати на XNUMX јули.

Извор: www.habr.com