Корҳои тадқиқотӣ шояд ҷолибтарин қисми омӯзиши мо бошад. Идеяи он аст, ки ҳангоми таҳсил дар донишгоҳ худро дар самти интихобкардаатон санҷед. Масалан, донишҷӯён аз соҳаҳои муҳандисии нармафзор ва омӯзиши мошинсозӣ аксар вақт барои тадқиқот ба ширкатҳо мераванд (асосан JetBrains ё Яндекс, аммо на танҳо).
В этом посте я расскажу о своём проекте по направлению Computer Science. В рамках работы я изучил и реализовал на практике подходы к решению одной из самых известных NP-трудных задач: мушкилоти фарогирии вертекс.
Дар айни замон, муносибати ҷолиб ба мушкилоти NP-мушкил хеле зуд инкишоф меёбад - алгоритмҳои параметрӣ. Ман кӯшиш мекунам, ки шуморо суръат бахшам, ба шумо якчанд алгоритмҳои оддии параметрҳоро нақл кунам ва як усули пурқувватеро тавсиф кунам, ки ба ман бисёр кӯмак кард. Ман натиҷаҳои худро дар озмуни PACE Challenge пешниҳод кардам: аз рӯи натиҷаҳои санҷишҳои кушод, ҳалли ман ҷои сеюмро ишғол мекунад ва натиҷаҳои ниҳоӣ 1 июл маълум хоҳанд шуд.
Дар бораи худам
Номи ман Василий Алферов, ҳоло ман соли сеюми Мактаби олии иқтисодии Донишгоҳи миллии тадқиқотӣ - Санкт-Петербургро хатм мекунам. Ман аз айёми мактабхонӣ, ки дар мактаби рақами 179-и Маскав таҳсил мекардам ва дар олимпиадаҳои информатика бомуваффақият иштирок мекардам, ба алгоритмҳо шавқу рағбат доштам.
Шумораи маҳдуди мутахассисон дар алгоритмҳои параметрӣ ба сатр ворид мешаванд...
Намуна аз китоб гирифта шудааст
Тасаввур кунед, ки шумо як посбони бар дар як шаҳраки хурд ҳастед. Ҳар рӯзи ҷумъа нисфи шаҳр барои истироҳат ба бари шумо меояд, ки ин ба шумо мушкилоти зиёд меорад: шумо бояд мизоҷони шӯришро аз бар партоед, то ки занозанӣ пешгирӣ карда шавад. Ниҳоят, шумо хаста мешавед ва қарор мекунед, ки чораҳои пешгирикунанда андешед.
Азбаски шаҳри шумо хурд аст, шумо аниқ медонед, ки кадом ҷуфти сарпарастон, агар онҳо якҷоя дар бар шаванд, ҷанг мекунанд. Шумо рӯйхати n одамоне, ки имшаб ба бар меоянд. Шумо қарор медиҳед, ки баъзе сокинони шаҳрро аз бар дур нигоҳ доред, бидуни он ки касе ба ҷанг наояд. Дар айни замон, роҳбарони шумо намехоҳанд фоидаро аз даст диҳанд ва бадбахт хоҳанд шуд, агар шумо ба зиёда аз он иҷозат надиҳед. k одамон.
Мутаассифона, мушкилоте, ки дар назди шумо қарор дорад, як мушкилоти классикии NP мебошад. Шумо шояд ӯро ҳамчун , ё ҳамчун мушкилоти фарогирии кулоҳ. Барои чунин мушкилот, дар ҳолати умумӣ, алгоритмҳое вуҷуд надоранд, ки дар вақти қобили қабул кор кунанд. Аниқтараш, гипотезаи исботнашуда ва хеле қавӣ ETH (Hipothesis Exponential Time) мегӯяд, ки ин мушкилотро сари вақт ҳал кардан мумкин нест. , яъне, шумо наметавонед чизе ба таври назаррас беҳтар аз ҷустуҷӯи пурра фикр кунед. Масалан, фарз мекунем, ки касе ба бари шумо меояд n = 1000 Инсон. Он гоҳ ҷустуҷӯи пурра хоҳад буд вариантҳое, ки тақрибан вуҷуд доранд - маблағи девона. Хушбахтона, роҳбарияти шумо ба шумо маҳдудият додааст к = 10, бинобар ин шумораи комбинатсияҳое, ки шумо бояд такрор кунед, хеле камтар аст: шумораи зермаҷмӯаҳои даҳ элемент . Ин беҳтар аст, аммо он дар як рӯз ҳатто дар кластери пурқувват ҳисоб карда намешавад.
Барои аз байн бурдани эҳтимолияти мубориза дар ин конфигуратсияи муносибатҳои муташанниҷ байни меҳмонони бар, шумо бояд Боб, Даниел ва Федорро дар канор нигоҳ доред. Ягон роҳи ҳал нест, ки дар он танҳо ду нафар паси сар шаванд.
Оё ин маънои онро дорад, ки вақти таслим шудан ва иҷозат додан ба ҳама расидааст? Биёед вариантҳои дигарро баррасӣ кунем. Хуб, масалан, шумо наметавонед танҳо онҳоеро, ки бо шумораи зиёди одамон мубориза мебаранд, иҷозат диҳед. Агар касе акаллан бо он мубориза бурда тавонад к + 1 шахси дигар, пас шумо бешубҳа ба ӯ иҷозат дода наметавонед - дар акси ҳол шумо бояд ҳамаро дар берун нигоҳ доред к + 1 шахрхо, ки бо онхо чанг карда метавонад, ки ин бешак рохбариятро хафа мекунад.
Бигзор шумо ҳамаро аз рӯи ин принсип берун кунед. Он гоҳ ҳар каси дигар метавонад бо на бештар аз ҷанг k одамон. Ба берун партофтани онҳо k одам, шумо метавонед чизе беш аз пешгирӣ низоъҳо. Ин маънои онро дорад, ки агар зиёда аз он вуҷуд дорад Агар шахс ақаллан дар як муноқиша ширкат дошта бошад, пас шумо бешубҳа ҳамаи онҳоро пешгирӣ карда наметавонед. Азбаски, албатта, шумо бешубҳа ба одамоне, ки комилан ҷанҷол надоранд, иҷозат медиҳед, шумо бояд ҳамаи зергурӯҳҳои андозаи даҳ аз дусад нафарро гузаред. Тақрибан вуҷуд доранд , ва ин шумораи амалиётҳоро аллакай дар кластер мураттаб кардан мумкин аст.
Агар шумо шахсонеро, ки умуман муноқиша надоранд, бехатар гирифта тавонед, пас дар бораи онҳое, ки танҳо дар як муноқиша иштирок мекунанд, чӣ гуфтан мумкин аст? Дарвоқеъ, онҳо метавонанд бо бастани дари рақиби худ ба дарун роҳ дода шаванд. Дарвоқеъ, агар Алис танҳо бо Боб ихтилоф дошта бошад, пас агар мо Алисаро аз ҳардуи онҳо берун кунем, мо аз даст намедиҳем: Боб метавонад дигар низоъҳо дошта бошад, аммо Алис албатта онҳоро надорад. Гузашта аз ин, барои мо ҳеҷ маъно надорад, ки ҳардуи моро ба хона роҳ надиҳем. Пас аз чунин амалиётҳо дигар боқӣ намемонад мехмонон бо такдири халнашуда: мо факат муноқишаҳо, ки ҳар яке ду иштирокчӣ доранд ва ҳар кадоме дар ҳадди аққал ду иштирок мекунанд. Ҳамин тавр, ҳама чизи боқимонда аст имконоти, ки мумкин аст ба осонӣ ним рӯз дар як ноутбук баррасӣ.
Дар асл, бо мулоҳизаҳои оддӣ шумо метавонед ба шароити боз ҳам ҷолибтар ноил шавед. Аҳамият диҳед, ки мо ҳатман бояд ҳамаи баҳсҳоро ҳал кунем, яъне аз ҳар як ҷуфти ихтилофӣ ақаллан як нафареро интихоб кунед, ки мо ба он роҳ намедиҳем. Биёед алгоритми зеринро дида бароем: ҳама гуна конфликтро гирем, ки аз он як иштирокчӣ хориҷ карда, ба таври рекурсивӣ аз боқимонда оғоз мекунем, баъд дигарро хориҷ мекунем ва инчунин рекурсивӣ оғоз мекунем. Азбаски мо дар ҳар қадам касеро мепартоем, дарахти рекурсии чунин алгоритм дарахти бинарии амиқ аст. k, бинобар ин дар маҷмӯъ алгоритм кор мекунад ки дар n шумораи қуллаҳо аст, ва m - шумораи қабурғаҳо. Дар мисоли мо, ин тақрибан даҳ миллион аст, ки онро дар як сония на танҳо дар ноутбук, балки ҳатто дар телефони мобилӣ ҳисоб кардан мумкин аст.
Мисоли боло мисол аст алгоритми параметрӣ. Алгоритмҳои параметрӣ алгоритмҳое мебошанд, ки дар вақташ кор мекунанд f(к) поли(н)ки дар p - полиномӣ, f вазифаи худсарона ҳисобшаванда аст, ва k - баъзе параметрҳо, ки эҳтимолан аз андозаи мушкилот хеле хурдтар бошанд.
Ҳама мулоҳизаҳо пеш аз ин алгоритм мисол меорад ядросозӣ яке аз усулҳои умумии эҷоди алгоритмҳои параметрӣ мебошад. Ядросозӣ ин кам кардани андозаи мушкилот ба арзишест, ки бо функсияи параметр маҳдуд аст. Мушкилоти натиҷавӣ аксар вақт ядро номида мешавад. Ҳамин тариқ, бо мулоҳизаҳои оддӣ дар бораи дараҷаҳои қуллаҳо, мо ядрои квадратиро барои масъалаи Vertex Cover гирифтем, ки аз рӯи андозаи ҷавоб параметр карда шудааст. Танзимоти дигаре ҳастанд, ки шумо метавонед барои ин вазифа интихоб кунед (ба монанди Vertex Cover Above LP), аммо ин танзимотест, ки мо муҳокима хоҳем кард.
Мушкилоти суръат
Competition (The Parameterized Algorithms and Computational Experiments Challenge) соли 2015 барои барқарор кардани робита байни алгоритмҳои параметршуда ва равишҳое, ки дар амалия барои ҳалли масъалаҳои ҳисоббарор истифода мешаванд, таваллуд шудааст. Се озмуни аввал ба дарёфти паҳнои дарахти график бахшида шуда буданд (), ҷустуҷӯи дарахти Штейнер () ва ҷустуҷӯи маҷмӯи қуллаҳое, ки давраҳоро буридаанд (). Дар ин сол, яке аз мушкилоте, ки шумо метавонед дар он кӯшиш кунед, мушкилоти фарогирии кулоҳ дар боло тавсиф шудааст.
Мусобика хар сол шухрат пайдо мекунад. Агар ба маълумоти пешакй бовар кунед, имсол дар мусобика 24 команда танхо барои халли масъалаи куллаи фарогиранда иштирок карданд. Бояд гуфт, ки озмун на чанд соат ва ҳатто як ҳафта, балки чанд моҳ давом мекунад. Коллективхо имконият доранд, ки адабиётро омузанд, идеяи оригиналии худро ба миён гузоранд ва барои амалй гардондани он кушиш кунанд. Аслан, ин озмун як лоиҳаи тадқиқотӣ мебошад. Идеяҳо барои ҳалли муассиртарин ва мукофотонидани ғолибон дар якҷоягӣ бо конфронс баргузор мешаванд. (Симпозиуми байналмилалӣ оид ба ҳисобкунии параметрҳо ва дақиқ) ҳамчун як қисми калонтарин ҷаласаи алгоритмии солона дар Аврупо . Маълумоти муфассалро дар бораи худи озмун метавонед дар ин саҳифа пайдо кунед , ва натичахои солхои гузашта дуруг аст .
Диаграммаи ҳалли
Барои ҳалли мушкилоти фарогирии қулла, ман кӯшиш кардам, ки алгоритмҳои параметриро истифода баранд. Онҳо маъмулан аз ду қисм иборатанд: қоидаҳои соддагардонӣ (ки ба таври идеалӣ ба ядросозӣ оварда мерасонад) ва қоидаҳои тақсимкунӣ. Қоидаҳои соддагардонӣ коркарди пешакии вуруд дар вақти полиномӣ мебошанд. Мақсади татбиқи чунин қоидаҳо коҳиш додани мушкилот ба як масъалаи хурдтар аст. Қоидаҳои соддагардонӣ қисми гаронтарини алгоритм мебошанд ва татбиқи ин қисм ба вақти умумии кор оварда мерасонад ба ҷои вақти полиномии оддӣ. Дар ҳолати мо, қоидаҳои тақсимкунӣ ба он асос ёфтааст, ки барои ҳар як қуллаи шумо бояд ё он ё ҳамсояи онро ҳамчун ҷавоб қабул кунед.
Схемаи умумй чунин аст: мо коидахои соддакуниро ба кор мебарем, баъд баъзе кулларо интихоб мекунем ва ду занги рекурсиви мекунем: дар аввал мо онро дар чавоб кабул мекунем ва дар дигараш хамаи хамсояхои онро мегирем. Ин чизест, ки мо тақсимшавӣ (шохаҳо) дар баробари ин қулла мегӯем.
Дар банди оянда ба ин схема маҳз як илова ворид карда мешавад.
Идеяҳо барои тақсим кардани қоидаҳо (бранчинг).
Биёед дида бароем, ки чӣ тавр интихоб кардани қуллае, ки дар он тақсимшавӣ рух медиҳад.
Идеяи асосӣ дар маънои алгоритмӣ хеле тамаъкор аст: биёед як қуллаи дараҷаи максималиро гирем ва дар баробари он тақсим кунем. Чаро он беҳтар ба назар мерасад? Зеро дар шохаи дуюми занги рекурсивӣ мо бо ин роҳ бисёр қуллаҳоро нест мекунем. Шумо метавонед ба графикаи хурди боқимонда умед бастан ва мо метавонем дар болои он зуд кор кунем.
Ин равиш, бо усулҳои оддии ядросозӣ, ки аллакай муҳокима карда шудааст, худро хуб нишон медиҳад ва баъзе санҷишҳои якчанд ҳазор қуллаҳои андозаро ҳал мекунад. Аммо, масалан, он барои графикҳои кубӣ (яъне графикҳое, ки дараҷаи ҳар як қуллаи онҳо се аст) хуб кор намекунад.
Идеяи дигаре вуҷуд дорад, ки ба як идеяи хеле содда асос ёфтааст: агар график ҷудо карда шавад, масъаларо дар ҷузъҳои пайвасти он мустақилона ҳал кардан мумкин аст, ки ҷавобҳоро дар охир муттаҳид мекунад. Дар омади гап, ин як тағироти хурди ваъдашуда дар схема мебошад, ки ҳалли онро ба таври назаррас суръат мебахшад: қаблан, дар ин ҳолат, мо барои ҳисоб кардани ҷавобҳои ҷузъҳо барои ҳосили замон кор мекардем, аммо ҳоло мо барои сум. Ва барои суръат бахшидан ба шоха, ба шумо лозим аст, ки графики пайвастшударо ба диаграммаи ҷудошуда табдил диҳед.
Чӣ тавр бояд кард? Агар дар график нуқтаи артикуляция мавҷуд бошад, шумо бояд бо он мубориза баред. Нуқтаи артикуляция як қуллаест, ки ҳангоми хориҷ шудан график пайвастагии худро гум мекунад. Ҳама нуқтаҳои пайвастшавиро дар график бо истифода аз алгоритми классикӣ дар вақти хатӣ пайдо кардан мумкин аст. Ин равиш шохаҳоро хеле суръат мебахшад.
Вақте ки яке аз қуллаҳои интихобшуда хориҷ карда мешавад, график ба ҷузъҳои пайвастшуда тақсим мешавад.
Мо ин корро мекунем, вале мо бештар мехоҳем. Масалан, дар график буришҳои хурди қуллаҳоро ҷустуҷӯ кунед ва ба қуллаҳои он тақсим кунед. Роҳи самараноктарине, ки ман медонам, барои ёфтани ҳадди ақали буриши глобалӣ ин истифодаи дарахти Гомори-Ху мебошад, ки дар вақти мукааб сохта шудааст. Дар PACE Challenge, андозаи маъмулии графикӣ якчанд ҳазор қуллаҳо мебошад. Дар ин вазъият бояд дар ҳар як қуллаи дарахти рекурсия миллиардҳо амалиёт анҷом дода шавад. Маълум мешавад, ки масъаларо дар вакти мукарраршуда хал кардан тамоман имконнопазир аст.
Биёед кӯшиш кунем, ки ҳалли онро оптимизатсия кунем. Ҳадди ақали қуллаи буридани байни як ҷуфт қуллаҳоро метавон тавассути ҳама алгоритме пайдо кард, ки ҷараёни максималиро месозад. Шумо метавонед онро ба чунин шабака иҷозат диҳед , дар амал хеле зуд кор мекунад. Ман гумон дорам, ки аз ҷиҳати назариявӣ исбот кардани тахмини вақти корӣ имконпазир аст , ки ин аллакай комилан қобили қабул аст.
Ман якчанд маротиба кӯшиш кардам, ки буридани байни ҷуфтҳои қуллаҳои тасодуфиро ҷустуҷӯ кунам ва яке аз ҳама мутавозинтаринро гирам. Мутаассифона, ин дар санҷиши кушодаи PACE Challenge натиҷаҳои ночиз овард. Ман онро бо алгоритме муқоиса кардам, ки қуллаҳои дараҷаи ҳадди аксарро тақсим карда, онҳоро бо маҳдудияти умқи фуруд меоранд. Алгоритм кӯшиши пайдо кардани буриш бо ин роҳ графикҳои калонтарро паси сар кард. Ин аз он сабаб аст, ки буришҳо хеле нобаробар баромаданд: 5-10 кунҷро нест карда, танҳо 15-20-ро ҷудо кардан мумкин буд.
Бояд қайд кард, ки мақолаҳо дар бораи алгоритмҳои аз ҷиҳати назариявӣ зудтарин усулҳои пешрафтаи интихоби қуллаҳо барои тақсимотро истифода мебаранд. Чунин техникаҳо татбиқи хеле мураккаб доранд ва аксар вақт аз ҷиҳати вақт ва хотира корашон паст аст. Ман онҳоеро, ки барои амалия комилан қобили қабуланд, муайян карда натавонистам.
Қоидаҳои соддагардониро чӣ гуна бояд татбиқ кард
Мо аллакай ғояҳои ядроиро дорем. Ба шумо хотиррасон кунам:
- Агар қуллаи ҷудошуда мавҷуд бошад, онро нест кунед.
- Агар қуллаи дараҷаи 1 мавҷуд бошад, онро хориҷ кунед ва дар ҷавоб ҳамсояи онро гиред.
- Агар ҳадди аққал як қуллаи дараҷа вуҷуд дошта бошад к + 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 ду кулларо илова мекунем и , ва ба ҷои ҳар як канори у - в ду кабурга илова мекунем и . Графикаи натиҷа дутарафа хоҳад буд. Биёед дар он сарпӯши ҳадди ақали қулларо пайдо кунем. Баъзе қуллаҳои диаграммаи аслӣ ду маротиба ба он ҷо меоянд, баъзеҳо танҳо як маротиба ва баъзеҳо ҳеҷ гоҳ. Теоремаи Немхаузер-Троттер мегӯяд, ки дар ин ҳолат метавон қуллаҳоеро, ки ҳатто як маротиба назадаанд, хориҷ карда ва онҳоеро, ки ду маротиба задаанд, баргардонанд. Гузашта аз ин, вай мегӯяд, ки аз қуллаҳои боқимонда (онҳое, ки як маротиба заданд) шумо бояд ҳадди аққал нисфи ҷавобро қабул кунед.
Мо навакак ёд гирифтем, ки на бештар аз 2k қуллаҳо Дарвоқеъ, агар ҷавоби боқимонда ҳадди ақалл нисфи ҳамаи қуллаҳо бошад, пас дар маҷмӯъ аз қуллаҳои зиёдтар нест. 2k.
Дар ин ҷо ман тавонистам як қадами хурде ба пеш гузорам. Равшан аст, ки ядрое, ки бо ин роҳ сохта шудааст, аз он вобаста аст, ки мо дар графикаи дутарафа чӣ гуна сарпӯши ҳадди ақаллро гирифтем. Мехостам яктоашро гирам, то шумораи қуллаҳои боқимонда кам бошад. Пеш онхо ин корро танхо дар вакташ ичро карда метавонистанд . Ман дар вақташ татбиқи ин алгоритмро таҳия кардам , ҳамин тавр, ин ядроро метавон дар графикҳои садҳо ҳазор қуллаҳо дар ҳар як марҳилаи шохаҳо ҷустуҷӯ кард.
Дар натиҷа
Амалия нишон медиҳад, ки ҳалли ман дар санҷишҳои якчанд сад қуллаҳо ва якчанд ҳазор кунҷҳо хуб кор мекунад. Дар ин гуна озмоишҳо интизор шудан мумкин аст, ки дар давоми ним соат ҳалли масъала пайдо мешавад. Эҳтимолияти дарёфти ҷавоб дар вақти қобили қабул, аслан, агар график шумораи кофӣ зиёди қуллаҳои дараҷаи баланд дошта бошад, масалан, дараҷаи 10 ва болотар.
Барои иштирок кардан дар озмун, қарорҳо бояд фиристода шаванд . Мувофики маълумоти дар он чо овардашуда , ҳалли ман дар санҷишҳои кушод дар байни бист ҷои сеюмро ишғол мекунад, бо фосилаи калон аз дуюм. Рости гап, комилан равшан нест, ки қарорҳо дар худи озмун чӣ гуна арзёбӣ мешаванд: масалан, ҳалли ман нисбат ба ҳалли дар ҷои чорум камтар аз санҷишҳо мегузарад, аммо дар онҳое, ки мегузаранд, он тезтар кор мекунад.
Натиҷаҳои санҷишҳои пӯшида XNUMX июл маълум хоҳанд шуд.
Манбаъ: will.com