Изилдөө иштери, балким, биздин тренингдин эң кызыктуу бөлүгү. Идея университетте окуп жүргөндө эле өзүңдү тандаган багытта сынап көрүү. Мисалы, программалык камсыздоо инженериясы жана машина үйрөнүү багытындагы студенттер көбүнчө компанияларга изилдөө жүргүзүү үчүн барышат (негизинен JetBrains же Yandex, бирок бир гана эмес).
Бул постто мен Информатика боюнча өзүмдүн долбоорум жөнүндө сүйлөшөм. Жумушумдун бир бөлүгү катары мен эң белгилүү NP-кыйын маселелердин бирин чечүүнүн ыкмаларын изилдеп, практикада ишке ашырдым: чокусун жабуу маселеси.
Бүгүнкү күндө NP-кыйын маселелерге кызыктуу мамиле абдан тез өнүгүп жатат - параметрленген алгоритмдер. Мен сени ылдамдатууга аракет кылам, бир нече жөнөкөй параметрленген алгоритмдерди айтып берем жана мага көп жардам берген бир күчтүү ыкманы сүрөттөп берем. Мен PACE Challenge сынагында өзүмдүн жыйынтыгымды көрсөттүм: ачык тесттердин жыйынтыгы боюнча менин чечимим үчүнчү орунду ээлейт жана акыркы жыйынтык 1-июлда белгилүү болот.
Өзү жөнүндө
Менин атым Василий Алферов, мен азыр Улуттук изилдөө университетинин Экономикалык жогорку мектебинин үчүнчү курсун аяктап жатам - Санкт-Петербург. Мен Москвадагы №179 мектепте окуп, информатика боюнча олимпиадаларга ийгиликтүү катышып жүргөн кезимден эле алгоритмдерге кызыгып келем.
Параметрленген алгоритмдер боюнча чектүү сандагы адистер тилкеге киришет...
Китептен алынган мисал
Кичинекей шаарчада бардын күзөтчүсү экениңизди элестетиңиз. Ар жума күнү шаардын жарымы эс алуу үчүн барыңызга келет, бул сизге көп кыйынчылыктарды жаратат: мушташуунун алдын алуу үчүн ызы-чуу кардарларды бардан кууп чыгышыңыз керек. Акыры тажап, алдын алуу чараларын көрүүнү чечесиң.
Сиздин шаар кичинекей болгондуктан, сиз кайсы жуп меценаттар чогуу барда уруша кетээрин так билесиз. тизмеси барбы n бүгүн кечинде барга келе турган адамдар. Эч ким урушпай, кээ бир шаардыктарды тилкеге киргизбей коюуну чечтиңиз. Ошол эле учурда, сиздин жетекчилер кирешеңизди жоготкусу келбейт жана эгер сиз андан ашыкча жол бербесеңиз, бактысыз болушат. k эл.
Тилекке каршы, сиздин алдыңызда турган маселе классикалык NP кыйын маселе. Сен аны таанып калышың мүмкүн , же чокусун камтыган көйгөй катары. Мындай көйгөйлөр үчүн, жалпы учурда, алгылыктуу убакытта иштей турган алгоритмдер жок. Тактап айтканда, далилденбеген жана абдан күчтүү гипотеза ETH (Экспоненциалдык Убакыт Гипотезасы) бул көйгөйдү өз убагында чечүү мүмкүн эмес экенин айтат. , башкача айтканда, сиз толук издөөгө караганда байкаларлык жакшы нерсени ойлоно албайсыз. Мисалы, сиздин барыңызга бирөө келет дейли н = 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-июлда белгилүү болот.
Source: www.habr.com