Հետազոտական աշխատանքը մեր վերապատրաստման ամենահետաքրքիր մասն է: Գաղափարն այն է, որ դու փորձես քեզ քո ընտրած ուղղությամբ դեռ համալսարանում: Օրինակ, ծրագրային ապահովման ճարտարագիտության և մեքենայական ուսուցման ոլորտների ուսանողները հաճախ գնում են հետազոտություններ անելու ընկերություններում (հիմնականում JetBrains կամ Yandex, բայց ոչ միայն):
Այս գրառման մեջ ես կխոսեմ համակարգչային գիտության իմ նախագծի մասին: Որպես իմ աշխատանքի մի մաս, ես ուսումնասիրեցի և գործնականում կիրառեցի մոտեցումներ՝ լուծելու ամենահայտնի NP-ծանր խնդիրներից մեկը. գագաթային ծածկույթի խնդիր.
Մեր օրերում շատ արագ է զարգանում NP-կոշտ խնդիրների նկատմամբ հետաքրքիր մոտեցում՝ պարամետրացված ալգորիթմներ։ Ես կփորձեմ ձեզ արագացնել, պատմել ձեզ մի քանի պարզ պարամետրացված ալգորիթմներ և նկարագրել մեկ հզոր մեթոդ, որն ինձ շատ օգնեց: ԵԽԽՎ Challenge մրցույթում ես ներկայացրել եմ իմ արդյունքները՝ բաց թեստերի արդյունքներով իմ լուծումը զբաղեցնում է երրորդ տեղը, իսկ վերջնական արդյունքները հայտնի կլինեն հուլիսի 1-ին։
About Me
Ես Վասիլի Ալֆերովն եմ, այժմ ավարտում եմ Ազգային գիտահետազոտական համալսարանի Տնտեսագիտության բարձրագույն դպրոցում՝ Սանկտ Պետերբուրգի երրորդ կուրսը: Ալգորիթմներով հետաքրքրվել եմ դպրոցական տարիներից, երբ սովորել եմ Մոսկվայի թիվ 179 դպրոցում և հաջողությամբ մասնակցել համակարգչային գիտության օլիմպիադաներին։
Պարամետրացված ալգորիթմների սահմանափակ թվով մասնագետներ մտնում են բար...
Գրքից վերցված օրինակ
Պատկերացրեք, որ դուք բարի անվտանգության աշխատակից եք փոքր քաղաքում: Ամեն ուրբաթ քաղաքի կեսը գալիս է ձեր բար՝ հանգստանալու, ինչը ձեզ շատ դժվարություններ է պատճառում. կռիվները կանխելու համար պետք է բարից դուրս շպրտել կռվարար հաճախորդներին: Ի վերջո, դուք կշտանում եք և որոշում եք կանխարգելիչ միջոցներ ձեռնարկել։
Քանի որ ձեր քաղաքը փոքր է, դուք հստակ գիտեք, թե որ զույգ հովանավորները կարող են կռվել, եթե նրանք միասին հայտնվեն բարում: Ունեք ցուցակ n մարդիկ, ովքեր այս գիշեր կգան բար: Դուք որոշում եք որոշ քաղաքաբնակների հետ պահել բարից, առանց որևէ մեկի կռվի մեջ մտնելու: Միևնույն ժամանակ, ձեր ղեկավարները չեն ցանկանում կորցնել շահույթը և դժգոհ կլինեն, եթե թույլ չտաք ավելին. k մարդ:
Ցավոք սրտի, ձեր առջեւ դրված խնդիրը դասական NP-կոշտ խնդիր է: Դուք կարող եք ճանաչել նրան որպես , կամ որպես գագաթ ծածկող խնդիր։ Նման խնդիրների դեպքում, ընդհանուր դեպքում, չկան ալգորիթմներ, որոնք գործում են ընդունելի ժամանակում։ Ճիշտ է, չապացուցված և բավականին ուժեղ վարկածը ETH (Exponential Time Hypothesis) ասում է, որ այս խնդիրը ժամանակին չի կարող լուծվել. , այսինքն, դուք չեք կարող ավելի լավ բան մտածել, քան ամբողջական որոնումը: Օրինակ, ասենք, ինչ-որ մեկը պատրաստվում է գալ ձեր բար n = 1000 Մարդ. Այնուհետև կլինի ամբողջական որոնումը տարբերակներ, որոնք մոտավորապես կան - խենթ գումար: Բարեբախտաբար, ձեր ղեկավարությունը ձեզ սահման է տվել կ = 10, այնպես որ համակցությունների թիվը, որոնք դուք պետք է կրկնեք, շատ ավելի փոքր է. տասը տարրերի ենթաբազմությունների թիվը կազմում է. . Սա ավելի լավ է, բայց այն դեռևս մեկ օրում չի հաշվարկվի նույնիսկ հզոր կլաստերի վրա:
Բարի այցելուների միջև լարված հարաբերությունների այս կոնֆիգուրացիայից կռվի հնարավորությունը վերացնելու համար հարկավոր է դուրս պահել Բոբին, Դանիելին և Ֆեդորին: Չկա այնպիսի լուծում, որում միայն երկուսը մնան։
Արդյո՞ք սա նշանակում է, որ ժամանակն է զիջելու և բոլորին ներս թողնելու: Դիտարկենք այլ տարբերակներ: Դե, օրինակ, դուք չեք կարող ներս թողնել միայն նրանց, ովքեր ամենայն հավանականությամբ կռվում են շատ մեծ թվով մարդկանց հետ: Եթե ինչ-որ մեկը կարող է պայքարել գոնե հետ կ + 1 մեկ այլ անձի, ապա դուք հաստատ չեք կարող նրան ներս թողնել, այլապես ստիպված կլինեք բոլորին դուրս պահել կ + 1 քաղաքաբնակներին, որոնց հետ նա կարող է կռվել, ինչը հաստատ կնեղացնի ղեկավարությանը:
Թույլ տվեք դուրս նետել բոլորին, ում կարող էիք այս սկզբունքով: Այդ դեպքում մնացած բոլորը կարող են պայքարել ոչ ավելի, քան k Ժողովուրդ. Նրանց դուրս շպրտելը k մարդ, դու չես կարող կանխել այլ բան, քան հակամարտություններ. Սա նշանակում է, որ եթե կա ավելի քան Եթե մարդը ներքաշված է գոնե մեկ կոնֆլիկտի մեջ, ապա, իհարկե, չես կարող բոլորին կանխել։ Քանի որ, իհարկե, դուք անպայման բաց կթողնեք բոլորովին ոչ կոնֆլիկտային մարդկանց, դուք պետք է անցնեք երկու հարյուր մարդուց տասը չափի բոլոր ենթախմբերը: Կան մոտավորապես , և այս թվով գործողություններ արդեն կարելի է տեսակավորել կլաստերի վրա:
Եթե դուք կարող եք ապահով կերպով վերցնել մարդկանց, ովքեր ընդհանրապես կոնֆլիկտ չունեն, ապա ի՞նչ կասեք նրանց մասին, ովքեր մասնակցում են միայն մեկ կոնֆլիկտի: Իրականում նրանց կարելի է ներս թողնել նաև հակառակորդի դուռը փակելով: Իսկապես, եթե Ալիսը կոնֆլիկտի մեջ է միայն Բոբի հետ, ապա եթե Ալիսին բաց թողնենք նրանցից երկուսից, մենք չենք պարտվի. Բոբը կարող է այլ կոնֆլիկտներ ունենալ, բայց Ալիսը, իհարկե, չունի: Ավելին, երկուսիս էլ ներս չթողնելն անիմաստ է։ Նման գործողություններից հետո այլևս չի մնում հյուրեր՝ չլուծված ճակատագրով. ունենք միայն հակամարտություններ, որոնցից յուրաքանչյուրը ունի երկու մասնակից և յուրաքանչյուրը ներգրավված է առնվազն երկուսի մեջ: Այսպիսով, մնում է միայն դասավորել տարբերակներ, որոնք հեշտությամբ կարելի է համարել կես օր նոութբուքի վրա:
Իրականում, պարզ պատճառաբանությամբ դուք կարող եք հասնել էլ ավելի գրավիչ պայմանների։ Նկատի ունեցեք, որ մենք անպայման պետք է լուծենք բոլոր վեճերը, այսինքն՝ յուրաքանչյուր հակամարտող զույգից ընտրենք գոնե մեկ մարդու, ում թույլ չենք տա ներս մտնել։ Դիտարկենք հետևյալ ալգորիթմը՝ վերցնել ցանկացած կոնֆլիկտ, որից հեռացնում ենք մեկ մասնակցին և ռեկուրսիվ կերպով սկսում մնացածից, ապա հանում մյուսին և սկսում ենք նաև ռեկուրսիվ։ Քանի որ մենք ամեն քայլափոխի ինչ-որ մեկին դուրս ենք նետում, նման ալգորիթմի ռեկուրսիոն ծառը խորության երկուական ծառ է: kԱյսպիսով, ընդհանուր առմամբ ալգորիթմն աշխատում է Որտեղ n գագաթների թիվն է, և m - կողերի քանակը. Մեր օրինակում սա մոտ տասը միլիոն է, որը կարելի է հաշվել վայրկյանում ոչ միայն նոութբուքի, այլ նույնիսկ բջջային հեռախոսի վրա։
Վերոնշյալ օրինակը օրինակ է պարամետրացված ալգորիթմ. Պարամետրացված ալգորիթմներն այն ալգորիթմներն են, որոնք գործում են ժամանակի ընթացքում f(k) poly(n)Որտեղ p - բազմանդամ, f կամայական հաշվարկելի ֆունկցիա է, և k - ինչ-որ պարամետր, որը, միանգամայն հնարավոր է, շատ ավելի փոքր լինի, քան խնդրի չափը:
Այս ալգորիթմից առաջ բոլոր պատճառաբանությունները տալիս են օրինակ միջուկացում պարամետրացված ալգորիթմների ստեղծման ընդհանուր տեխնիկաներից մեկն է։ Kernelization-ը խնդրի չափի կրճատումն է մի արժեքի, որը սահմանափակվում է պարամետրի ֆունկցիայով: Արդյունքում առաջացած խնդիրը հաճախ կոչվում է միջուկ: Այսպիսով, գագաթների աստիճանների մասին պարզ պատճառաբանելով, մենք ստացանք քառակուսի միջուկ Vertex Cover խնդրի համար, որը պարամետրացված է պատասխանի չափով: Կան այլ կարգավորումներ, որոնք կարող եք ընտրել այս առաջադրանքի համար (օրինակ՝ Vertex Cover Above LP), բայց սա այն պարամետրն է, որը մենք կքննարկենք:
Տեմպի մարտահրավեր
Մրցակցություն (The Parameterized Algorithms and Computational Experiments Challenge) ծնվել է 2015 թվականին՝ հաշվողական խնդիրներ լուծելու համար պրակտիկայում օգտագործվող պարամետրացված ալգորիթմների և մոտեցումների միջև կապ հաստատելու համար: Առաջին երեք մրցույթները նվիրված էին գրաֆիկի ծառի լայնությունը գտնելուն (), Շտայների ծառի որոնում () և որոնել մի շարք գագաթներ, որոնք կտրում են ցիկլերը () Այս տարի խնդիրներից մեկը, որում դուք կարող եք փորձել, վերը նկարագրված գագաթային ծածկույթի խնդիրն էր:
Մրցույթը տարեցտարի մեծ ժողովրդականություն է վայելում: Եթե հավատաք նախնական տվյալներին, ապա այս տարի միայն գագաթային ծածկույթի խնդիրը լուծելու համար մրցույթին մասնակցել է 24 թիմ։ Հարկ է նշել, որ մրցույթը տեւում է ոչ թե մի քանի ժամ կամ նույնիսկ մեկ շաբաթ, այլ մի քանի ամիս։ Թիմերը հնարավորություն ունեն ուսումնասիրել գրականությունը, հանդես գալ սեփական օրիգինալ գաղափարով և փորձել իրականացնել այն։ Ըստ էության, այս մրցույթը հետազոտական ծրագիր է։ Համաժողովի հետ համատեղ կանցկացվեն ամենաարդյունավետ լուծումների գաղափարները և հաղթողներին պարգևատրելը. (International Symposium on Parameterized and Exact Computation) որպես Եվրոպայի ամենամեծ տարեկան ալգորիթմական հանդիպման մաս . Մրցույթի մասին ավելի մանրամասն տեղեկություններ կարելի է գտնել այստեղ , իսկ նախորդ տարիների արդյունքները ստում են .
Լուծման դիագրամ
Գագաթային ծածկույթի խնդիրը լուծելու համար ես փորձեցի օգտագործել պարամետրացված ալգորիթմներ: Դրանք սովորաբար բաղկացած են երկու մասից՝ պարզեցման կանոններ (որոնք իդեալականորեն հանգեցնում են միջուկի) և բաժանման կանոններին: Պարզեցման կանոնները մուտքի նախնական մշակումն են բազմանդամ ժամանակում: Նման կանոնների կիրառման նպատակն է խնդիրը նվազեցնել համարժեք ավելի փոքր խնդրի: Պարզեցման կանոնները ալգորիթմի ամենաթանկ մասն են, և այս մասի կիրառումը հանգեցնում է գործարկման ընդհանուր ժամանակի պարզ բազմանդամ ժամանակի փոխարեն: Մեր դեպքում բաժանման կանոնները հիմնված են այն փաստի վրա, որ յուրաքանչյուր գագաթի համար պետք է որպես պատասխան վերցնել կամ այն, կամ նրա հարևանը:
Ընդհանուր սխեման այսպիսին է՝ մենք կիրառում ենք պարզեցման կանոնները, այնուհետև ընտրում ենք ինչ-որ գագաթ և կատարում երկու ռեկուրսիվ կանչ՝ առաջինում ընդունում ենք այն որպես պատասխան, իսկ մյուսում՝ վերցնում ենք դրա բոլոր հարևանները։ Սա այն է, ինչ մենք անվանում ենք պառակտում (ճյուղավորում) այս գագաթի երկայնքով:
Հաջորդ պարբերությունում այս սխեմային կկատարվի ուղիղ մեկ լրացում:
Գաղափարներ պառակտման (brunching) կանոնների համար
Եկեք քննարկենք, թե ինչպես ընտրել գագաթ, որի երկայնքով տեղի կունենա պառակտումը:
Հիմնական գաղափարը ալգորիթմական իմաստով շատ ագահ է. եկեք վերցնենք առավելագույն աստիճանի գագաթը և բաժանենք դրա երկայնքով: Ինչու է դա ավելի լավ է թվում: Քանի որ ռեկուրսիվ կանչի երկրորդ ճյուղում մենք այս կերպ կհեռացնենք շատ գագաթներ։ Դուք կարող եք հույս դնել փոքր գրաֆիկի վրա, և մենք կարող ենք արագ աշխատել դրա վրա:
Այս մոտեցումը, արդեն քննարկված պարզ միջուկային տեխնիկայով, իրեն լավ է ցույց տալիս և լուծում է մի քանի հազար գագաթների չափի որոշ թեստեր: Բայց, օրինակ, այն լավ չի աշխատում խորանարդ գրաֆիկների համար (այսինքն՝ այն գրաֆիկների, որոնց յուրաքանչյուր գագաթի աստիճանը երեքն է):
Կա ևս մեկ գաղափար, որը հիմնված է բավականին պարզ գաղափարի վրա՝ եթե գրաֆիկն անջատված է, ապա դրա միացված բաղադրիչների խնդիրը կարող է ինքնուրույն լուծվել՝ վերջում համադրելով պատասխանները։ Սա, ի դեպ, սխեմայի մի փոքրիկ խոստացված փոփոխություն է, որը զգալիորեն կարագացնի լուծումը. նախկինում, այս դեպքում, մենք աշխատում էինք բաղադրիչների պատասխանները հաշվարկելու ժամանակների արտադրյալի համար, բայց հիմա աշխատում ենք գումարը։ Իսկ ճյուղավորումն արագացնելու համար պետք է միացված գրաֆիկը վերածել անջատվածի:
Ինչպե՞ս դա անել: Եթե գրաֆիկում կա հոդակապման կետ, ապա պետք է պայքարել դրա վրա: Հոդակապման կետը այնպիսի գագաթ է, որ երբ հանվում է, գրաֆիկը կորցնում է իր կապը: Գրաֆիկի բոլոր միացման կետերը կարելի է գտնել գծային ժամանակի դասական ալգորիթմի միջոցով: Այս մոտեցումը զգալիորեն արագացնում է ճյուղավորումը:
Երբ ընտրված գագաթներից որևէ մեկը հեռացվի, գրաֆիկը կբաժանվի միացված բաղադրիչների:
Մենք դա կանենք, բայց ավելին ենք ուզում։ Օրինակ, գծապատկերում փնտրեք փոքր գագաթային կտրվածքներ և բաժանեք դրանից գագաթների երկայնքով: Ամենաարդյունավետ միջոցը, որը ես գիտեմ՝ գտնելու նվազագույն գլոբալ գագաթային կտրվածքը, Գոմորի-Հու ծառի օգտագործումն է, որը կառուցված է խորանարդ ժամանակում: ԵԽԽՎ մարտահրավերում գրաֆիկի տիպիկ չափը մի քանի հազար գագաթ է: Այս իրավիճակում ռեկուրսիոն ծառի յուրաքանչյուր գագաթում պետք է կատարվեն միլիարդավոր գործողություններ: Ստացվում է, որ հատկացված ժամկետում խնդիրը լուծելն ուղղակի անհնար է։
Փորձենք օպտիմալացնել լուծումը։ Մի զույգ գագաթների միջև կտրված նվազագույն գագաթը կարելի է գտնել ցանկացած ալգորիթմի միջոցով, որը կառուցում է առավելագույն հոսք: Դուք կարող եք թույլ տալ այն նման ցանցի վրա , գործնականում այն շատ արագ է աշխատում։ Ես կասկած ունեմ, որ տեսականորեն հնարավոր է գործառնական ժամանակի նախահաշիվը ապացուցել , ինչն արդեն միանգամայն ընդունելի է։
Ես մի քանի անգամ փորձեցի որոնել կտրվածքներ զույգ պատահական գագաթների միջև և վերցնել ամենահավասարակշռվածը: Ցավոք, դա վատ արդյունքներ տվեց ԵԽԽՎ մարտահրավերների բաց թեստավորման ժամանակ: Ես այն համեմատեցի մի ալգորիթմի հետ, որը բաժանում է առավելագույն աստիճանի գագաթները՝ գործարկելով դրանք իջնելու խորության սահմանափակմամբ: Այս կերպ կտրվածք գտնելու փորձ կատարող ալգորիթմը թողեց ավելի մեծ գրաֆիկներ: Դա պայմանավորված է նրանով, որ կտրվածքները շատ անհավասարակշիռ են ստացվել. հեռացնելով 5-10 գագաթներ, հնարավոր եղավ բաժանել միայն 15-20-ը:
Հարկ է նշել, որ տեսականորեն ամենաարագ ալգորիթմների մասին հոդվածները օգտագործում են շատ ավելի առաջադեմ տեխնիկա՝ բաժանման համար գագաթներ ընտրելու համար։ Նման տեխնիկան ունեն շատ բարդ իրականացում և հաճախ վատ կատարում ժամանակի և հիշողության առումով: Ես չկարողացա բացահայտել նրանց, որոնք բավականին ընդունելի են պրակտիկայի համար:
Ինչպես կիրառել պարզեցման կանոնները
Մենք արդեն ունենք միջուկացման գաղափարներ։ Թույլ տվեք հիշեցնել ձեզ.
- Եթե կա մեկուսացված գագաթ, ջնջեք այն:
- Եթե կա 1 աստիճանի գագաթ, հեռացրեք այն և ի պատասխան վերցրեք դրա հարևանին:
- Եթե կա առնվազն աստիճանի գագաթ կ + 1, վերցնել այն ետ.
Առաջին երկուսի հետ ամեն ինչ պարզ է, երրորդի մոտ կա մեկ հնարք. Եթե բարի մասին կատակերգական խնդրի դեպքում մեզ վերին սահման տրվեր k, ապա ԵԽԽՎ մարտահրավերում պարզապես անհրաժեշտ է գտնել նվազագույն չափի գագաթային ծածկույթ։ Սա որոնման խնդիրների բնորոշ փոխակերպումն է որոշման խնդիրների, հաճախ տարբերություն չկա երկու տեսակի խնդիրների միջև: Գործնականում, եթե մենք լուծում ենք գրում գագաթային ծածկույթի խնդրի համար, կարող է տարբերություն լինել: Օրինակ, ինչպես երրորդ կետում.
Իրականացման տեսանկյունից կարելի է շարունակել երկու ճանապարհ. Առաջին մոտեցումը կոչվում է կրկնվող խորացում: Դա հետևյալն է. մենք կարող ենք սկսել պատասխանի վրա ներքևից ինչ-որ ողջամիտ սահմանափակումով, այնուհետև գործարկել մեր ալգորիթմը՝ օգտագործելով այս սահմանափակումը՝ որպես վերևից պատասխանի սահմանափակում, առանց այս սահմանափակումից ավելի ցածր ռեկուրսիայով գնալու: Եթե գտել ենք ինչ-որ պատասխան, ապա այն երաշխավորված է օպտիմալ, հակառակ դեպքում կարող ենք մեկով ավելացնել այս սահմանը և նորից սկսել:
Մեկ այլ մոտեցում է պահպանել որոշ ընթացիկ օպտիմալ պատասխան և փնտրել ավելի փոքր պատասխան՝ փոխելով այս պարամետրը, երբ գտնվի 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