Kev tshawb fawb ua haujlwm yog kab tias qhov nthuav tshaj plaws ntawm peb qhov kev cob qhia. Lub tswv yim yog sim koj tus kheej hauv koj txoj kev xaiv thaum tseem nyob hauv tsev kawm qib siab. Piv txwv li, cov tub ntxhais kawm los ntawm thaj chaw ntawm Software Engineering thiab Machine Learning feem ntau mus ua kev tshawb fawb hauv cov tuam txhab (feem ntau yog JetBrains lossis Yandex, tab sis tsis yog xwb).
Hauv tsab ntawv no kuv yuav tham txog kuv qhov project hauv Computer Science. Raws li ib feem ntawm kuv txoj hauj lwm, kuv tau kawm thiab muab tso rau hauv kev xyaum los daws ib qho ntawm cov teeb meem nto moo tshaj plaws NP- nyuaj: vertex npog teeb meem.
Niaj hnub no, ib qho kev nthuav qhia rau NP-cov teeb meem nyuaj yog tsim sai heev - parameterized algorithms. Kuv yuav sim ua kom koj nce nrawm, qhia koj qee qhov yooj yim parameterized algorithms thiab piav qhia txog ib txoj kev muaj zog uas tau pab kuv ntau heev. Kuv tau nthuav tawm kuv cov txiaj ntsig ntawm kev sib tw PACE Challenge: raws li cov txiaj ntsig ntawm kev sim qhib, kuv qhov kev daws teeb meem yog qhov thib peb, thiab cov txiaj ntsig kawg yuav raug paub thaum Lub Xya Hli 1.
Txog kuv tus kheej
Kuv lub npe yog Vasily Alferov, tam sim no kuv kawm tiav kuv xyoo peb ntawm National Research University Higher School of Economics - St. Kuv tau txaus siab rau algorithms txij li kuv hnub kawm ntawv, thaum kuv kawm hauv Moscow tsev kawm ntawv No. 179 thiab tau koom nrog hauv computer science Olympiads.
Ntau tus kws kho mob tshwj xeeb hauv parameterized algorithms nkag mus rau qhov bar ...
Piv txwv muab los ntawm phau ntawv
Xav txog tias koj yog ib tus neeg saib xyuas kev ruaj ntseg hauv ib lub nroog me. Txhua hnub Friday, ib nrab ntawm lub nroog tuaj rau koj lub bar kom so, uas ua rau koj muaj teeb meem ntau: koj yuav tsum pov cov neeg siv khoom tsis txaus siab tawm ntawm qhov bar kom tiv thaiv kev sib ntaus. Thaum kawg, koj tau tshaib plab thiab txiav txim siab los ntsuas kev tiv thaiv.
Txij li thaum koj lub nroog me me, koj paub tseeb tias ob khub ntawm patrons yuav tawm tsam yog tias lawv xaus rau hauv ib qho bar ua ke. Koj puas muaj daim ntawv teev npe n cov neeg uas yuav tuaj rau lub bar hmo no. Koj txiav txim siab kom qee cov neeg hauv nroog tawm ntawm qhov bar tsis muaj leej twg nkag mus rau hauv kev sib ntaus. Nyob rau tib lub sijhawm, koj cov thawj coj tsis xav poob cov txiaj ntsig thiab yuav tsis zoo siab yog tias koj tsis tso ntau dua k Tib neeg.
Hmoov tsis zoo, qhov teeb meem ua ntej koj yog qhov teeb meem classic NP- nyuaj. Tej zaum koj yuav paub nws li , los yog raws li vertex npog teeb meem. Rau cov teeb meem zoo li no, nyob rau hauv cov ntaub ntawv dav dav, tsis muaj algorithms uas ua haujlwm nyob rau lub sijhawm tsim nyog. Kom meej meej, qhov tsis muaj pov thawj thiab muaj kev ntseeg siab heev ETH (Exponential Time Hypothesis) hais tias qhov teeb meem no tsis tuaj yeem daws tau raws sijhawm. , uas yog, koj tsis tuaj yeem xav txog ib yam dab tsi zoo dua li kev tshawb nrhiav tiav. Piv txwv li, cia peb hais tias ib tug neeg yuav tuaj rau koj lub bar n = 1000 Tib neeg. Tom qab ntawd qhov kev tshawb nrhiav tiav yuav yog kev xaiv uas muaj kwv yees li - vwm npaum li cas. Hmoov zoo, koj qhov kev tswj hwm tau muab rau koj txwv k = 10 hli, yog li tus naj npawb ntawm cov kev sib txuas uas koj yuav tsum tau rov hais dua yog tsawg dua: tus naj npawb ntawm cov subsets ntawm kaum lub ntsiab lus yog . Qhov no zoo dua, tab sis nws tseem yuav tsis suav nyob rau hauv ib hnub txawm nyob rau hauv pawg muaj zog.
Txhawm rau tshem tawm qhov muaj peev xwm ntawm kev sib ntaus hauv qhov kev teeb tsa ntawm kev sib raug zoo ntawm cov neeg tuaj xyuas bar, koj yuav tsum khaws Bob, Daniel thiab Fedor tawm. Tsis muaj kev daws teeb meem uas tsuas yog ob leeg yuav raug tso tseg.
Puas yog qhov no txhais tau tias nws yog lub sijhawm los muab rau hauv thiab cia txhua tus neeg nyob hauv? Cia peb xav txog lwm yam kev xaiv. Zoo, piv txwv li, koj tsis tuaj yeem tso rau hauv tsuas yog cov neeg uas yuav tawm tsam nrog coob tus neeg. Yog tias ib tug neeg tuaj yeem sib ntaus tsawg kawg nrog k+ 1 Lwm tus neeg, ces koj yeej tsis tuaj yeem tso nws rau hauv - txwv tsis pub koj yuav tsum khaws txhua tus tawm k+ 1 cov neeg hauv nroog, nrog rau leej twg nws tuaj yeem sib ntaus, uas yuav ua rau npau taws rau kev coj noj coj ua.
Cia koj pov tseg txhua tus uas koj ua tau raws li txoj cai no. Ces txhua leej txhua tus tuaj yeem sib ntaus nrog tsis muaj ntau tshaj k neeg. Muab pov tseg k txiv neej, koj yuav tiv thaiv tsis muaj dab tsi ntau tshaj li kev tsis sib haum xeeb. Qhov no txhais tau tias yog muaj ntau tshaj Yog tias ib tus neeg koom nrog tsawg kawg ib qho kev tsis sib haum xeeb, ces koj yeej tsis tuaj yeem tiv thaiv lawv txhua tus. Txij li thaum, ntawm chav kawm, koj yuav twv yuav raug hu cia nyob rau hauv tag nrho cov neeg tsis sib haum xeeb, koj yuav tsum mus los ntawm tag nrho cov subsets ntawm loj kaum tawm ntawm ob puas tus neeg. Muaj kwv yees li , thiab tus naj npawb ntawm cov haujlwm no tuaj yeem txheeb tawm ntawm pawg.
Yog tias koj tuaj yeem coj tau cov tib neeg uas tsis muaj kev sib cav tsis sib haum xeeb, ces cov uas koom nrog ib qho kev tsis sib haum xeeb li cas? Qhov tseeb, lawv tseem tuaj yeem tso rau hauv los ntawm kev kaw qhov rooj ntawm lawv tus nrog sib tw. Tseeb tiag, yog tias Alice muaj teeb meem nrog Bob nkaus xwb, yog tias peb tso Alice tawm ntawm ob ntawm lawv, peb yuav tsis poob: Bob yuav muaj lwm yam kev tsis sib haum xeeb, tab sis Alice yeej tsis muaj lawv. Tsis tas li ntawd, nws tsis muaj txiaj ntsig rau peb tsis cia peb ob leeg nyob hauv. Tom qab cov haujlwm zoo li no tseem tsis muaj ntxiv lawm cov qhua nrog txoj hmoo tsis tau daws: peb tsuas muaj kev tsis sib haum xeeb, txhua tus muaj ob tus neeg koom thiab txhua tus koom nrog tsawg kawg yog ob. Yog li txhua yam uas tseem tshuav yog los txheeb xyuas kev xaiv, uas tuaj yeem yooj yim txiav txim siab ib nrab hnub ntawm lub laptop.
Qhov tseeb, nrog kev xav yooj yim koj tuaj yeem ua tiav cov xwm txheej zoo nkauj dua. Nco ntsoov tias peb yuav tsum daws txhua qhov kev tsis sib haum xeeb, uas yog, los ntawm txhua tus khub tsis sib haum xeeb, xaiv tsawg kawg ib tus neeg uas peb yuav tsis tso rau hauv. Cia peb xav txog cov hauv qab no algorithm: coj ib qho kev tsis sib haum xeeb, los ntawm qhov peb tshem tawm ib tus neeg koom nrog thiab rov ua dua los ntawm qhov seem, tom qab ntawd tshem tawm lwm tus thiab pib rov ua dua. Txij li thaum peb pov ib tug neeg tawm ntawm txhua kauj ruam, tsob ntoo recursion ntawm xws li ib tug algorithm yog binary tsob ntoo ntawm qhov tob. k, yog li tag nrho cov algorithm ua haujlwm hauv qhov twg n yog tus naj npawb ntawm vertices, thiab m - tus naj npawb ntawm tav. Hauv peb qhov piv txwv, qhov no yog kwv yees li kaum lab, uas tuaj yeem suav nrog hauv qhov sib cais thib ob tsis yog ntawm lub laptop nkaus xwb, tab sis txawm tias ntawm lub xov tooj ntawm tes.
Cov piv txwv saum toj no yog ib qho piv txwv parameterized algorithm. Parameterized algorithms yog algorithms uas khiav hauv lub sijhawm f(k) poly(n)qhov twg p - polynomial, f yog ib tug arbitrary computable muaj nuj nqi, thiab k - qee qhov parameter, uas, tejzaum nws yuav muaj ntau me dua qhov loj ntawm qhov teeb meem.
Txhua qhov laj thawj ua ntej no algorithm muab piv txwv kernelization yog ib qho ntawm cov txheej txheem dav dav rau kev tsim cov parameterized algorithms. Kernelization yog qhov txo qhov teeb meem loj rau tus nqi txwv los ntawm kev ua haujlwm ntawm qhov ntsuas. Qhov teeb meem tshwm sim feem ntau hu ua kernel. Yog li, los ntawm cov laj thawj yooj yim txog qib ntawm vertices, peb tau txais ib lub quadratic kernel rau Vertex Cover teeb meem, parameterized los ntawm qhov loj ntawm cov lus teb. Muaj lwm qhov chaw koj tuaj yeem xaiv rau txoj haujlwm no (xws li Vertex Cover Above LP), tab sis qhov no yog qhov chaw uas peb yuav tham txog.
Pace Challenge
Kev sib tw (The Parameterized Algorithms and Computational Experiments Challenge) yug hauv 2015 los tsim kom muaj kev sib txuas ntawm parameterized algorithms thiab cov txheej txheem siv hauv kev xyaum los daws cov teeb meem kev suav. Thawj peb qhov kev sib tw tau mob siab rau nrhiav tsob ntoo dav ntawm daim duab (), nrhiav ib tsob ntoo Steiner () thiab nrhiav ib pawg ntawm vertices uas txiav cycles (). Xyoo no, ib qho teeb meem uas koj tuaj yeem sim koj txhais tes yog qhov vertex npog teeb meem tau piav qhia saum toj no.
Qhov kev sib tw tau txais koob meej txhua xyoo. Yog tias koj ntseeg tias cov ntaub ntawv ua ntej, xyoo no 24 pawg tau koom nrog hauv kev sib tw los daws qhov teeb meem npog qhov vertex ib leeg. Nws yog tsim nyog sau cia tias qhov kev sib tw tsis ntev los no ob peb teev lossis ib lub lim tiam, tab sis ob peb lub hlis. Cov pab pawg muaj lub cib fim los kawm cov ntaub ntawv, tuaj nrog lawv tus kheej lub tswv yim thiab sim siv nws. Hauv qhov tseeb, qhov kev sib tw no yog qhov kev tshawb fawb. Cov tswv yim rau cov kev daws teeb meem zoo tshaj plaws thiab muab khoom plig ntawm cov neeg yeej yuav muaj nyob rau hauv kev sib tham nrog lub rooj sib tham (International Symposium on Parameterized and Exact Computation) ua ib feem ntawm lub rooj sib tham algorithmic loj tshaj plaws hauv Tebchaws Europe . Cov ncauj lus kom ntxaws ntxiv txog kev sib tw nws tus kheej tuaj yeem nrhiav tau ntawm , thiab cov txiaj ntsig ntawm xyoo dhau los yog dag .
Kev daws teeb meem
Txhawm rau daws qhov teeb meem vertex npog, kuv sim siv cov txheej txheem parameterized. Lawv feem ntau muaj ob ntu: cov kev cai yooj yim (uas yog qhov zoo tshaj plaws ua rau kernelization) thiab kev faib cov cai. Cov kev cai yooj yim yog preprocessing ntawm cov tswv yim nyob rau hauv lub sij hawm polynomial. Lub hom phiaj ntawm kev siv cov kev cai no yog txo qhov teeb meem mus rau qhov sib npaug ntawm qhov teeb meem me me. Cov kev cai yooj yim yog qhov kim tshaj plaws ntawm cov algorithm, thiab siv qhov no ua rau tag nrho lub sijhawm khiav es tsis txhob siv lub sij hawm polynomial yooj yim. Nyob rau hauv peb cov ntaub ntawv, cov kev sib cais yog raws li qhov tseeb hais tias rau txhua vertex koj yuav tsum tau coj nws los yog nws cov neeg zej zog raws li ib tug teb.
Lub tswv yim dav dav yog qhov no: peb siv cov kev cai yooj yim, tom qab ntawd peb xaiv qee qhov vertex, thiab ua ob qhov kev hu rov qab: thawj zaug peb coj nws los teb, thiab lwm qhov peb coj tag nrho nws cov neeg nyob ze. Qhov no yog qhov peb hu ua splitting (branching) raws qhov vertex.
Muaj ib qho ntxiv yuav raug ua rau lub tswv yim no hauv kab lus tom ntej.
Cov tswv yim rau kev sib cais (brunching) cov cai
Wb sib tham txog yuav ua li cas xaiv ib tug vertex raws li qhov splitting yuav tshwm sim.
Lub tswv yim tseem ceeb yog greedy heev nyob rau hauv lub algorithmic siab: cia peb coj ib tug vertex ntawm siab tshaj plaws degree thiab faib raws nws. Vim li cas nws zoo dua? Vim hais tias nyob rau hauv lub thib ob ceg ntawm recursive hu peb yuav tshem tawm ntau vertices nyob rau hauv no txoj kev. Koj tuaj yeem suav rau ntawm daim duab me me uas tseem tshuav thiab peb tuaj yeem ua haujlwm sai.
Txoj hauv kev no, nrog rau qhov twb tau tham txog cov txheej txheem kernelization yooj yim, qhia nws tus kheej zoo thiab daws qee qhov kev sim ntawm ntau txhiab qhov loj. Tab sis, piv txwv li, nws tsis ua hauj lwm zoo rau lub cubic graphs (uas yog, cov duab uas nws qib ntawm txhua vertex yog peb).
Muaj lwm lub tswv yim raws li lub tswv yim yooj yim: yog tias daim duab raug txiav, qhov teeb meem ntawm nws cov khoom sib txuas tuaj yeem daws tau ntawm nws tus kheej, sib txuas cov lus teb thaum kawg. Qhov no, los ntawm txoj kev, yog ib qho kev hloov kho me me uas tau cog lus tseg hauv cov tswv yim, uas yuav ua rau muaj kev daws teeb meem sai: yav dhau los, hauv qhov no, peb tau ua haujlwm rau cov khoom ntawm lub sijhawm rau kev suav cov lus teb ntawm cov khoom, tab sis tam sim no peb ua haujlwm rau. cov sum. Thiab txhawm rau kom nrawm dua, koj yuav tsum tig daim duab txuas mus rau hauv ib qho kev sib txuas.
Yuav ua li cas? Yog hais tias muaj ib qho kev taw qhia hauv daim duab, koj yuav tsum tau tawm tsam ntawm nws. Ib qho kev sib txuas lus yog ib qho vertex uas thaum tshem tawm, daim duab poob nws txoj kev sib txuas. Tag nrho cov ntsiab lus sib txuas hauv ib daim duab tuaj yeem pom siv cov classical algorithm hauv linear time. Qhov no txoj kev no ho speeds li branching.
Thaum ib qho ntawm cov xaiv vertices raug tshem tawm, daim duab yuav muab faib ua cov khoom sib txuas.
Peb yuav ua qhov no, tab sis peb xav tau ntau dua. Piv txwv li, nrhiav me me vertex txiav nyob rau hauv daim duab thiab phua raws lub vertices los ntawm nws. Txoj kev ua tau zoo tshaj plaws uas kuv paub kom pom qhov tsawg kawg nkaus lub ntiaj teb vertex txiav yog siv tsob ntoo Gomori-Hu, uas yog tsim nyob rau hauv cubic lub sij hawm. Hauv PACE Challenge, cov duab loj loj yog ob peb txhiab vertices. Hauv qhov xwm txheej no, ntau lab ntawm cov haujlwm yuav tsum tau ua ntawm txhua qhov vertex ntawm tsob ntoo recursion. Nws hloov tawm tias nws tsuas yog tsis yooj yim sua kom daws tau qhov teeb meem hauv lub sijhawm teem tseg.
Cia peb sim ua kom zoo tshaj qhov kev daws teeb meem. Qhov tsawg kawg nkaus vertex txiav ntawm ib khub ntawm vertices tuaj yeem pom los ntawm ib qho algorithm uas tsim kom muaj qhov siab tshaj plaws. Koj tuaj yeem cia nws mus rau lub network zoo li no , hauv kev xyaum nws ua haujlwm sai heev. Kuv muaj qhov tsis txaus ntseeg tias nws yog qhov ua tau los ua pov thawj qhov kwv yees rau lub sijhawm ua haujlwm , uas yog twb tau txais heev.
Kuv sim ob peb zaug los nrhiav kev txiav ntawm ob khub ntawm random vertices thiab coj qhov sib npaug tshaj plaws. Hmoov tsis zoo, qhov no ua rau cov txiaj ntsig tsis zoo hauv kev sim qhib PACE Challenge. Kuv muab piv rau nws nrog cov algorithm uas faib cov vertices ntawm qhov siab tshaj plaws degree, khiav lawv nrog kev txwv ntawm qhov tob ntawm qhovntsej thiaj tsis mob. Ib qho algorithm sim nrhiav kev txiav hauv txoj kev no tau tso tseg cov duab loj dua. Qhov no yog vim qhov tseeb hais tias qhov kev txiav tawm los ua qhov tsis sib npaug: tau tshem tawm 5-10 vertices, nws tuaj yeem faib tawm tsuas yog 15-20.
Nws yog tsim nyog sau cia tias cov lus hais txog qhov theoretical ceev tshaj plaws algorithms siv ntau cov txuj ci siab tshaj los xaiv cov vertices rau kev sib cais. Cov tswv yim zoo li no muaj kev siv ntau heev thiab feem ntau ua haujlwm tsis zoo ntawm lub sijhawm thiab kev nco. Kuv tsis tuaj yeem txheeb xyuas cov uas tau txais txiaj ntsig zoo rau kev xyaum.
Yuav Thov Li Cas Cov Cai Simplification
Peb twb muaj tswv yim rau kernelization. Cia kuv ceeb toom koj:
- Yog tias muaj ib qho vertex cais, rho tawm nws.
- Yog tias muaj vertex ntawm degree 1, tshem nws thiab coj nws cov neeg zej zog teb.
- Yog tias muaj qhov vertex ntawm degree tsawg kawg k+ 1, coj nws rov qab.
Nrog thawj ob txhua yam yog qhov tseeb, nrog rau qhov thib peb yog ib qho ua kom yuam kev. Yog hais tias nyob rau hauv ib tug comic teeb meem hais txog ib tug bar peb tau muab lub siab tshaj txwv ntawm k, tom qab ntawd hauv PACE Challenge koj tsuas yog yuav tsum nrhiav lub vertex npog ntawm qhov tsawg kawg nkaus. Qhov no yog ib qho kev hloov pauv ntawm Kev Tshawb Fawb Cov Teeb Meem rau Kev Txiav Txim Siab; feem ntau tsis muaj qhov sib txawv ntawm ob hom teeb meem. Hauv kev xyaum, yog tias peb sau ib qho kev daws teeb meem rau qhov vertex npog qhov teeb meem, tej zaum yuav muaj qhov sib txawv. Piv txwv li, nyob rau hauv lub ntsiab lus thib peb.
Los ntawm qhov kev xav ntawm kev siv, muaj ob txoj hauv kev los mus. Thawj txoj hauv kev yog hu ua Iterative Deepening. Nws yog raws li nram no: peb tuaj yeem pib nrog qee qhov kev txwv tsim nyog los ntawm cov lus teb hauv qab no, thiab tom qab ntawd khiav peb cov algorithm siv qhov kev txwv no raws li qhov txwv ntawm cov lus teb los ntawm saum toj no, tsis tas yuav rov qab qis dua li qhov txwv no. Yog tias peb tau pom qee cov lus teb, nws tau lees tias yuav ua tau zoo, txwv tsis pub peb tuaj yeem nce qhov kev txwv no los ntawm ib qho thiab pib dua.
Lwm txoj hauv kev yog khaws qee cov lus teb zoo tam sim no thiab nrhiav cov lus teb me me, hloov qhov ntsuas no thaum pom k rau kev txiav ntau dua ntawm cov ceg tsis tsim nyog hauv kev tshawb nrhiav.
Tom qab ua ntau qhov kev sim hmo ntuj, kuv tau txiav txim siab ua ke ntawm ob txoj hauv kev no: ua ntej, kuv khiav kuv cov algorithm nrog qee yam kev txwv ntawm kev tshawb nrhiav qhov tob (xaiv nws kom nws siv sij hawm tsis txaus siab piv rau cov ntsiab lus tseem ceeb) thiab siv qhov zoo tshaj plaws kev daws teeb meem pom raws li kev txwv siab rau cov lus teb - uas yog, rau tib yam k.
Vertices ntawm degree 2
Peb tau cuam tshuam nrog vertices ntawm degree 0 thiab 1. Nws hloov tawm tias qhov no tuaj yeem ua tiav nrog vertices ntawm qib 2, tab sis qhov no yuav xav tau ntau txoj haujlwm nyuaj los ntawm daim duab.
Txhawm rau piav qhia qhov no, peb yuav tsum ua qee yam xaiv cov vertices. Cia peb hu lub vertex ntawm degree 2 a vertex v, thiab nws cov neeg zej zog - vertices x и y. Tom ntej no peb yuav muaj ob rooj plaub.
- Thaum x и y - cov neeg nyob ze. Ces koj teb tau x и ythiab v rho tawm. Tseeb tiag, los ntawm daim duab peb sab no tsawg kawg yog ob lub vertices yuav tsum tau rov qab los, thiab peb yeej yuav tsis poob yog tias peb coj. x и y: tej zaum lawv muaj lwm tus neeg nyob ze, thiab v Lawv tsis nyob ntawm no.
- Thaum x и y - tsis nyob ze. Tom qab ntawd nws tau hais tias tag nrho peb qhov vertices tuaj yeem muab khi rau hauv ib qho. Lub tswv yim yog hais tias nyob rau hauv cov ntaub ntawv no muaj ib tug zoo lus teb, nyob rau hauv uas peb coj los yog v, los yog ob qho tib si vertices x и y. Ntxiv mus, nyob rau hauv thawj rooj plaub peb yuav tau coj tag nrho cov neeg zej zog teb x и y, tab sis nyob rau hauv qhov thib ob nws tsis tsim nyog. Qhov no raws nraim sib raug rau cov rooj plaub thaum peb tsis coj lub vertex glued nyob rau hauv teb thiab thaum peb ua. Nws tsuas yog yuav tsum nco ntsoov tias nyob rau hauv ob qho tib si cov lus teb los ntawm xws li kev ua haujlwm txo qis los ntawm ib qho.
Nws yog ib qho tsim nyog sau cia tias txoj hauv kev no yog qhov nyuaj heev los ua kom raug raws li lub sijhawm ncaj ncees linear. Gluing vertices yog ib txoj haujlwm nyuaj; koj yuav tsum luam cov npe ntawm cov neeg nyob ze. Yog tias qhov no ua tiav tsis tu ncua, koj tuaj yeem xaus nrog asymptotically suboptimal khiav lub sijhawm (piv txwv li, yog tias koj luam ntau cov npoo tom qab txhua gluing). Kuv tau txiav txim siab nrhiav tag nrho txoj hauv kev los ntawm vertices ntawm qib 2 thiab tshuaj xyuas ib pawg ntawm cov xwm txheej tshwj xeeb, xws li cov voj voog ntawm cov vertices lossis los ntawm tag nrho cov vertices tshwj tsis yog ib qho.
Tsis tas li ntawd, nws yog ib qho tsim nyog uas qhov kev ua haujlwm no yuav thim rov qab, yog li thaum rov qab los ntawm recursion peb rov qab kho cov duab rau nws daim ntawv qub. Txhawm rau kom ntseeg tau qhov no, kuv tsis tau tshem tawm cov npe ntawm ntug kev sib koom ua ke, thiab tom qab ntawd kuv tsuas paub tias cov npoo yuav tsum mus qhov twg. Qhov kev siv cov duab no kuj xav tau qhov tseeb, tab sis nws muab lub sijhawm ncaj ncees. Thiab rau cov duab ntawm ntau kaum tawm txhiab tus npoo, nws haum rau hauv lub processor cache, uas muab cov txiaj ntsig zoo hauv kev ceev.
Linear ntsiav
Thaum kawg, qhov nthuav tshaj plaws ntawm cov ntsiav.
Yuav pib nrog, nco qab tias hauv bipartite graphs qhov tsawg kawg nkaus vertex npog tuaj yeem pom siv . Txhawm rau ua qhov no koj yuav tsum siv cov algorithm nyob rau hauv thiaj li yuav nrhiav tau qhov siab tshaj plaws txuam muaj, thiab ces siv lub theorem .
Lub tswv yim ntawm linear kernel yog qhov no: ua ntej peb bifurcate daim duab, uas yog, es tsis txhob ntawm txhua vertex v cia peb ntxiv ob lub ncov и , thiab es tsis txhob ntawm txhua ntug ua - v cia peb ntxiv ob ribs и . Cov txiaj ntsig tau yuav yog bipartite. Cia peb pom qhov tsawg kawg nkaus vertex npog hauv nws. Qee qhov vertices ntawm thawj daim duab yuav mus txog qhov ntawd ob zaug, qee qhov tsuas yog ib zaug, thiab qee qhov tsis tau. Nemhauser-Trotter theorem hais tias nyob rau hauv cov ntaub ntawv no ib tug yuav tshem tawm vertices uas tsis ntaus ib zaug thiab coj rov qab cov uas ntaus ob zaug. Ntxiv mus, nws hais tias ntawm qhov seem seem (cov uas ntaus ib zaug) koj yuav tsum tau noj tsawg kawg yog ib nrab los teb.
Peb nyuam qhuav kawm tawm tsis ntau tshaj li 2k ncov Qhov tseeb, yog tias cov lus teb seem yog tsawg kawg yog ib nrab ntawm tag nrho cov vertices, ces tsis muaj vertices nyob rau hauv tag nrho ntau tshaj. 2k.
Ntawm no kuv muaj peev xwm ua ib kauj ruam me me rau pem hauv ntej. Nws yog qhov tseeb tias cov ntsiav tsim nyob rau hauv txoj kev no nyob ntawm seb yam tsawg kawg nkaus vertex npog peb coj hauv daim duab bipartite. Kuv xav muab ib qho kom cov lej ntawm qhov seem seem tsawg tsawg. Yav tas los, lawv muaj peev xwm ua tau qhov no tsuas yog nyob rau lub sijhawm . Kuv tuaj nrog kev siv ntawm no algorithm nyob rau lub sijhawm , yog li, cov tub ntxhais no tuaj yeem tshawb nrhiav hauv cov duab ntawm ntau pua txhiab tus vertices ntawm txhua theem ceg.
tshwm sim
Kev xyaum qhia tau hais tias kuv qhov kev daws teeb meem ua haujlwm tau zoo ntawm kev sim ntawm ob peb puas vertices thiab ob peb txhiab npoo. Hauv cov kev ntsuam xyuas zoo li no nws yog qhov ua tau kom cia siab tias yuav pom qhov kev daws teeb meem hauv ib nrab teev. Qhov tshwm sim ntawm kev nrhiav cov lus teb nyob rau hauv ib lub sij hawm tsim nyog, nyob rau hauv txoj cai, nce yog hais tias daim duab muaj ib tug txaus tus naj npawb ntawm vertices ntawm high degree, piv txwv li, degree 10 thiab siab dua.
Txhawm rau koom nrog kev sib tw, cov kev daws teeb meem yuav tsum raug xa mus rau . Kev txiav txim los ntawm cov ntaub ntawv tau nthuav tawm muaj , kuv qhov kev daws teeb meem hauv kev sim qhib yog thib peb ntawm nees nkaum, nrog qhov sib txawv loj ntawm qhov thib ob. Yuav kom ua ncaj ncees, nws tsis meej meej tias cov kev daws teeb meem yuav raug ntsuas li cas ntawm kev sib tw nws tus kheej: piv txwv li, kuv cov kev daws teeb meem dhau qhov kev sim tsawg dua li qhov kev daws teeb meem hauv qhov chaw thib plaub, tab sis ntawm cov uas dhau mus, nws ua haujlwm sai dua.
Cov txiaj ntsig ntawm kev xeem kaw yuav raug paub thaum Lub Xya Hli XNUMXst.
Tau qhov twg los: www.hab.com