Зерттеу жұмысы біздің тренингіміздің ең қызықты бөлігі болуы мүмкін. Идея – университет қабырғасында жүргенде өзіңізді таңдаған бағытта сынап көру. Мысалы, бағдарламалық жасақтама инженериясы және машиналық оқыту салаларындағы студенттер жиі компанияларға (негізінен JetBrains немесе Yandex, бірақ тек қана емес) зерттеу жұмыстарын жүргізуге барады.
Бұл постта мен информатикадағы жобам туралы айтатын боламын. Жұмысымның бір бөлігі ретінде мен ең танымал 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) поли(n)қайда p - көпмүшелік, f ерікті есептелетін функция болып табылады және k - кейбір параметр, ол мәселенің өлшемінен әлдеқайда аз болуы мүмкін.
Бұл алгоритмге дейінгі барлық пайымдаулар мысал келтіреді ядроландыру параметрленген алгоритмдерді құрудың жалпы әдістерінің бірі болып табылады. Ядролау – мәселе өлшемін параметр функциясымен шектелген мәнге дейін азайту. Нәтижедегі мәселе көбінесе ядро деп аталады. Осылайша, шыңдардың дәрежелері туралы қарапайым пайымдаулар арқылы біз Vertex Cover мәселесі үшін жауап өлшемімен параметрленген квадраттық ядро алдық. Бұл тапсырма үшін таңдауға болатын басқа опциялар бар (мысалы, Vertex Cover Above LP), бірақ бұл біз талқылайтын опция.
Pace Challenge
Конкурс (The Parameterized Algorithms and Computational Experiments Challenge) 2015 жылы параметрленген алгоритмдер мен есептеу есептерін шешу үшін тәжірибеде қолданылатын тәсілдер арасындағы байланысты орнату үшін дүниеге келген. Алғашқы үш жарыс графиктің ағаш енін табуға арналды (), Штайнер ағашын іздеу () және циклдарды қысқартатын шыңдар жинағын іздеу (). Биылғы жылы қолыңызды сынап көруге болатын мәселелердің бірі жоғарыда сипатталған шыңдарды жабу мәселесі болды.
Байқау жылдан жылға танымал болып келеді. Алдын ала мәліметке сенсеңіз, биылғы жылы тек шыңды жабу мәселесін шешуге арналған жарысқа 24 команда қатысты. Айта кетерлігі, байқау бірнеше сағатқа, тіпті бір аптаға емес, бірнеше айға созылады. Командалардың әдебиетті зерделеуге, өзіндік түпнұсқа идеясын шығаруға және оны жүзеге асыруға тырысуға мүмкіндігі бар. Негізінде бұл байқау ғылыми жоба болып табылады. Ең тиімді шешімдерге арналған идеялар және жеңімпаздарды марапаттау конференциямен бірге өткізіледі. (Параметрленген және дәл есептеу бойынша халықаралық симпозиум) Еуропадағы ең ірі жыл сайынғы алгоритмдік жиналыстың бөлігі ретінде . Байқаудың өзі туралы толығырақ ақпаратты мына жерден алуға болады , ал өткен жылдардың нәтижелері өтірік .
Шешу диаграммасы
Шыңды жабу мәселесін шешу үшін мен параметрленген алгоритмдерді қолдануға тырыстым. Олар әдетте екі бөліктен тұрады: жеңілдету ережелері (ол өз кезегінде ядроға айналуға әкеледі) және бөлу ережелері. Жеңілдету ережелері - көпмүшелік уақытта кірісті алдын ала өңдеу. Мұндай ережелерді қолданудың мақсаты - мәселені баламалы кішірек мәселеге дейін азайту. Жеңілдету ережелері алгоритмнің ең қымбат бөлігі болып табылады және бұл бөлікті қолдану жалпы жұмыс уақытына әкеледі. жай көпмүшелік уақыттың орнына. Біздің жағдайда бөлу ережелері әрбір шың үшін жауап ретінде оны немесе оның көршісін қабылдау керек екендігіне негізделген.
Жалпы схема мынадай: біз жеңілдету ережелерін қолданамыз, содан кейін біз кейбір шыңдарды таңдаймыз және екі рекурсивті шақырамыз: біріншісінде біз оны жауап ретінде қабылдаймыз, ал екіншісінде оның барлық көршілерін аламыз. Мұны біз осы шыңның бойымен бөліну (тармақталу) деп атаймыз.
Келесі абзацта осы схемаға дәл бір толықтыру енгізіледі.
Ережелерді бөлу (бранчинг) идеялары
Бөліну орын алатын шыңды қалай таңдау керектігін талқылайық.
Негізгі идея алгоритмдік мағынада өте ашкөз: максималды дәрежелі шыңды алып, оның бойымен бөлейік. Неліктен бұл жақсырақ болып көрінеді? Өйткені рекурсивті шақырудың екінші тармағында біз осылайша көптеген шыңдарды алып тастаймыз. Сіз қалған шағын графикке сене аласыз және біз онымен тез жұмыс істей аламыз.
Бұл тәсіл, қазірдің өзінде талқыланған қарапайым ядролау әдістерімен, өзін жақсы көрсетеді және өлшемі бірнеше мың шыңдардың кейбір сынақтарын шешеді. Бірақ, мысалы, ол текше графиктер үшін жақсы жұмыс істемейді (яғни, әрбір төбесінің дәрежесі үш болатын графиктер).
Жеткілікті қарапайым идеяға негізделген тағы бір идея бар: егер график ажыратылса, оның қосылған құрамдас бөліктері бойынша мәселені соңында жауаптарды біріктіре отырып, дербес шешуге болады. Айтпақшы, бұл шешімді айтарлықтай тездететін схемадағы кішкене уәде етілген модификация: бұрын, бұл жағдайда біз компоненттердің жауаптарын есептеу үшін уақыт өнімі үшін жұмыс істедік, бірақ қазір біз жұмыс істейміз. сомасы. Ал тармақталуды жылдамдату үшін қосылған графикті ажыратылғанға айналдыру керек.
Бұны қалай істейді? Графикте артикуляциялық нүкте болса, онымен күресу керек. Артикуляциялық нүкте деп алып тастаған кезде график өзінің байланысын жоғалтатын төбе болып табылады. Графиктегі барлық түйісу нүктелерін сызықтық уақытта классикалық алгоритм арқылы табуға болады. Бұл тәсіл тармақталуды айтарлықтай жылдамдатады.
Таңдалған шыңдардың кез келгені жойылғанда, график қосылған құрамдастарға бөлінеді.
Біз мұны істейміз, бірақ біз одан да көп нәрсені қалаймыз. Мысалы, графиктен шағын шыңдардың қиықтарын іздеңіз және одан шыңдар бойымен бөліңіз. Мен білетін ең аз жаһандық шыңның қиығын табудың ең тиімді жолы - текше уақытта салынған Гомори-Ху ағашын пайдалану. 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