{"id":35406,"date":"2019-10-31T22:04:08","date_gmt":"2019-10-31T19:04:08","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov\/"},"modified":"2021-01-02T13:01:41","modified_gmt":"2021-01-02T11:01:41","slug":"kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","status":"publish","type":"post","link":"https:\/\/prohoster.info\/da\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"S\u00e5dan l\u00f8ser man NP-sv\u00e6re problemer med parametrede algoritmer.","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Forskning og udvikling er m\u00e5ske den mest interessante del af vores uddannelse. Ideen er at pr\u00f8ve sig af i det valgte omr\u00e5de allerede p\u00e5 universitetet. For eksempel g\u00e5r studerende fra Software Engineering og Machine Learning ofte ud for at udf\u00f8re forsknings- og udviklingsprojekter i virksomheder (prim\u00e6rt JetBrains eller Yandex, men ikke kun).<\/p>\n

I dette indl\u00e6g vil jeg fort\u00e6lle om mit projekt inden for Computer Science. I forbindelse med arbejdet har jeg studeret og praktisk implementeret tilgange til at l\u00f8se et af de mest kendte NP-sv\u00e6re problemer: vertex cover-problemet<\/b>.<\/p>\n

Der udvikles i \u00f8jeblikket hurtigt en interessant tilgang til NP-sv\u00e6re problemer - parametriserede algoritmer. Jeg vil pr\u00f8ve at introducere dig til emnet, fort\u00e6lle om et par simple parametriserede algoritmer og beskrive en kraftfuld metode, der har hjulpet mig meget. Jeg pr\u00e6senterede mine resultater ved PACE Challenge-konkurrencen: efter de \u00e5bne tests ligger min l\u00f8sning p\u00e5 tredje plads, og de endelige resultater vil blive kendt den 1. juli.<\/p>\n

\"S\u00e5dan
\n<\/a><\/noindex><\/p>\n

Om mig<\/h3>\n

Mit navn er Vasilij Alferov, jeg er i \u00f8jeblikket ved at afslutte mit tredje \u00e5r p\u00e5 National Research University Higher School of Economics - St. Petersburg. Jeg har v\u00e6ret interesseret i algoritmer siden mine skole\u00e5r, da jeg gik i Moskvas 179. skole og aktivt deltog i informatikolympiader.<\/p>\n

Et begr\u00e6nset antal specialister inden for parametriserede algoritmer g\u00e5r ind i en bar...<\/h3>\n

Eksemplet er taget fra bogen \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

Forestil dig, at du er sikkerhedsvagt i en bar i en lille by. Hver fredag kommer halvdelen af byen ind i din bar for at slappe af, hvilket giver dig en del hovedpine: du skal smide de voldelige g\u00e6ster ud for at undg\u00e5 slagsm\u00e5l. Til sidst bliver du tr\u00e6t af det og beslutter dig for at tage forebyggende foranstaltninger.<\/p>\n

Da byen er lille, ved du pr\u00e6cist, hvilke par g\u00e6ster der med stor sandsynlighed vil komme i slagsm\u00e5l, hvis de er i baren sammen. Du har en liste over n<\/i> g\u00e6ster, der kommer i aften til baren. Du beslutter dig for ikke at lade nogen lokale g\u00e5 ind i baren, s\u00e5 ingen kommer i slagsm\u00e5l. Samtidig \u00f8nsker dit lederskab ikke at miste indt\u00e6gt og vil ikke v\u00e6re tilfredse, hvis du ikke lader flere end k<\/i> g\u00e6ster g\u00e5 ind.<\/p>\n

Desv\u00e6rre er opgaven, du st\u00e5r overfor, et klassisk NP-h\u00e5rdt problem. Du har m\u00e5ske kendskab til det som Vertex Cover<\/a><\/noindex>, or how to solve the vertex cover problem. For such problems, there are generally no algorithms that work in a reasonable time. To be precise, the unproven and fairly strong hypothesis ETH (Exponential Time Hypothesis) suggests that this problem cannot be solved in time \"S\u00e5dan, meaning that nothing significantly better than brute force can be invented. For example, let's say that a total of n = 1000<\/i> people are planning to come to your bar. Then, brute forcing leads to \"S\u00e5dan combinations, which is approximately \"S\u00e5dan \u2014 an incredibly large number. Fortunately, your management has set a limit of k = 10<\/i>, so the number of combinations you need to consider is much smaller: the number of subsets of ten elements is equal to \"S\u00e5dan. This is already better, but still can't be counted in a day even on a powerful cluster.
\n\"S\u00e5dan
\nTo avoid potential fights in such a tense relationship among the bar visitors, you need to exclude Bob, Daniel, and Fyodor. There is no solution where only two are left outside.<\/p>\n

Does this mean it's time to give up and let everyone in? Let's consider other options. For example, you could not let in those who are likely to fight with a very large number of people. If someone can fight with at least k + 1<\/i> other individuals, then they definitely shouldn't be allowed in \u2014 otherwise, you'll have to turn away all k + 1<\/i> the townsfolk they could potentially fight with, which would definitely upset management.<\/p>\n

Suppose you've thrown out everyone you could based on this principle. Then all the rest can fight with no more than k<\/i> people. By removing k<\/i> individuals from them, you can prevent at most \"S\u00e5dan conflicts. Thus, if more than \"S\u00e5dan people are involved in at least one conflict, you definitely won\u2019t be able to prevent them all. Since, obviously, the completely non-conflictual people will definitely be let in, you need to consider all subsets of size ten from the two hundred people. There are approximately \"S\u00e5dan, and such a number of operations can be handled on a cluster.<\/p>\n

Hvis man sikkert kan tage helt konfliktfrie personer, hvad med dem, der kun deltager i \u00e9n konflikt? Faktisk kan vi ogs\u00e5 lukke dem ind, mens vi lukker d\u00f8ren for deres modstander. Og sandt, hvis Alice kun har konflikt med Bob, s\u00e5 hvis vi lukker Alice ind af de to, taber vi ikke: Bob kan have andre konflikter, men Alice har bestemt ikke. Desuden giver det ikke mening at holde begge ude. Efter s\u00e5danne operationer er der ikke mere \"S\u00e5dan g\u00e6ster med uafklaret sk\u00e6bne: vi har i alt \"S\u00e5dan konflikter, hver med to deltagere, og hver deltager i mindst to. S\u00e5 det er kun n\u00f8dvendigt at gennemg\u00e5 \"S\u00e5dan muligheder, hvilket rimeligt kan g\u00f8res p\u00e5 en halvdag med en b\u00e6rbar computer.<\/p>\n

I virkeligheden kan man med enkle overvejelser opn\u00e5 endnu mere attraktive betingelser. Bem\u00e6rk, at vi n\u00f8dvendigvis skal l\u00f8se alle tvister, alts\u00e5 fra hver konfliktfugerende par v\u00e6lge mindst \u00e9n person, som vi ikke lukker ind. Lad os overveje en s\u00e5dan algoritme: vi tager enhver konflikt, fjerner \u00e9n deltager og starter rekurserende fra resten, derefter fjerner vi den anden og starter ogs\u00e5 rekurserende. Da vi fjerner nogen p\u00e5 hvert trin, er rekursionstr\u00e6et for en s\u00e5dan algoritme et bin\u00e6rt tr\u00e6 i dybden k<\/i>, s\u00e5 samlet set arbejder algoritmen p\u00e5 \"S\u00e5dan, hvor n<\/i> \u2014 antallet af noder, og m<\/i> \u2014 antallet af kanter. P\u00e5 vores eksempel var det omkring ti millioner, hvilket kan beregnes p\u00e5 br\u00f8kdelen af et sekund, ikke kun p\u00e5 en b\u00e6rbar computer, men endda p\u00e5 en mobiltelefon.<\/p>\n

Det ovenfor n\u00e6vnte eksempel er et eksempel p\u00e5 parametrisk algoritme<\/b>. Parametriske algoritmer er algoritmer, der arbejder p\u00e5 tid f(k) poly(n)<\/i>, hvor p<\/i> \u2014 et polynomium, f<\/i> \u2014 en vilk\u00e5rlig beregnelig funktion, og k<\/i> \u2014 en eller anden parameter, der muligvis vil v\u00e6re meget mindre end st\u00f8rrelsen af opgaven.<\/p>\n

Alle overvejelser frem til denne algoritme f\u00f8rer til et eksempel p\u00e5 kernelisering<\/b> \u2014 en af de generelle teknikker til at skabe parameteriserede algoritmer. Kernalisering er at reducere opgavens st\u00f8rrelse til et niveau, der er begr\u00e6nset af en funktion af parameteren. Den resulterende opgave kaldes ofte kernen. Med simple overvejelser om graderne af noderne fik vi en kvadratisk kerne til problemet Vertex Cover, parameteriseret efter svarst\u00f8rrelsen. Der findes ogs\u00e5 andre parametre, der kan v\u00e6lges til denne opgave (f.eks. Vertex Cover Above LP), men vi vil netop diskutere denne parameter.<\/p>\n

Pace Challenge<\/h3>\n

Konkurrence PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) blev grundlagt i 2015 for at etablere en forbindelse mellem parameteriserede algoritmer og de metoder, der anvendes i praksis til at l\u00f8se beregningsm\u00e6ssige opgaver. De f\u00f8rste tre konkurrencer var dedikeret til at finde tr\u00e6bredden af grafen (Treewidth<\/a><\/noindex>), finde Steiner-tr\u00e6et (Steiner Tree<\/a><\/noindex>) og finde en klump af noder, der sk\u00e6rer cykler (Feedback Vertex Set<\/a><\/noindex>). I \u00e5r var en af opgaverne, hvor man kunne pr\u00f8ve sine kr\u00e6fter, den ovenfor beskrevne opgave om vertexd\u00e6kning.<\/p>\n

Konkurrence vinder i popularitet for hvert \u00e5r. Hvis man skal tro de forel\u00f8bige data, deltager kun i \u00e5r 24 hold i konkurrencen for at l\u00f8se opgaven om vertexd\u00e6kning. Det skal bem\u00e6rkes, at konkurrencen ikke varer i nogle timer eller endda en uge, men flere m\u00e5neder. Holdene har mulighed for at studere litteraturen, komme med deres originale id\u00e9 og fors\u00f8ge at realisere den. I bund og grund repr\u00e6senterer denne konkurrence et forskningsarbejde. Ideerne for de mest effektive l\u00f8sninger og bel\u00f8nningen af vinderne vil finde sted i forbindelse med konferencen IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) inden for den st\u00f8rste \u00e5rlige algoritmiske samling i Europa ALGO<\/a><\/noindex>. Mere detaljerede oplysninger om selve konkurrencen kan findes p\u00e5 websitet<\/a><\/noindex>, mens resultaterne fra tidligere \u00e5r findes her<\/a><\/noindex>.<\/p>\n

L\u00f8sningsdiagram<\/h3>\n

For tackling the vertex cover problem, I attempted to apply parameterized algorithms. They generally consist of two parts: simplification rules (which ideally lead to kernelization) and splitting rules. Simplification rules are a preprocessing step on the input that takes polynomial time. The purpose of applying these rules is to reduce the problem to an equivalent problem of smaller size. Simplification rules are the most resource-intensive part of the algorithm, and applying this part leads to a total runtime \"S\u00e5dan instead of simple polynomial time. In our case, the splitting rules are based on the fact that for each vertex, we need to take either it or its neighbor as a response.<\/p>\n

The overall scheme is as follows: we apply the simplification rules, then select a vertex, and make two recursive calls: in the first, we take it as a response, and in the other, we take all its neighbors. We refer to this as splitting (branching) on that vertex.<\/p>\n

One addition will be made to this scheme in the next paragraph.<\/p>\n

Ideas for splitting rules (branching)<\/h3>\n

Let's discuss how to choose a vertex for the splitting process.
\nThe main idea is very greedy in an algorithmic sense: let\u2019s take the vertex of maximum degree and split on it. Why does it seem to be a better option? Because in the second branch of the recursive call, we will thus remove a lot of vertices. We can expect that a small graph will remain, and we can work quickly on it.<\/p>\n

This approach, combined with the previously discussed simple kernelization techniques, performs reasonably well, solving some tests with a few thousand vertices. However, it performs poorly for cubic graphs (that is, graphs where the degree of each vertex equals three).
\nThere is another idea based on a fairly simple thought: if the graph is disconnected, the task on its connected components can be solved independently, combining the answers at the end. This is, by the way, the small promised modification in the scheme that will significantly accelerate the solution: previously, in such cases, we worked with the product of the times for counting the answers of the components, whereas now we work with the sum. To speed up branching, a connected graph needs to be transformed into a disconnected one.<\/p>\n

Hvordan g\u00f8r man det? Hvis der er et knudepunkt i grafen, skal vi bifurcere netop ved det. Et knudepunkt er en v\u00e6rdi, hvis fjernelse g\u00f8r grafen uforbundet. Man kan finde alle knudepunkter i grafen ved hj\u00e6lp af den klassiske algoritme p\u00e5 line\u00e6r tid. Denne tilgang accelererer bifurkationen v\u00e6sentligt.
\n\"S\u00e5dan
\nVed at fjerne en hvilken som helst af de markerede noder, vil grafen falde sammen til forbindelseskomponenter.<\/p>\n

Det vil vi g\u00f8re, men vi \u00f8nsker mere. For eksempel skal vi lede efter sm\u00e5 vertex-sk\u00e6ringer i grafen og udf\u00f8re bifurkation baseret p\u00e5 dem. Den mest effektive metode, jeg kender til at finde den minimale globale vertex-sk\u00e6ring, er at bruge Gomory-Hu tr\u00e6et, hvilket bygger sig p\u00e5 kubisk tid. I PACE Challenge er den typiske st\u00f8rrelse af grafen flere tusinde noder. Under s\u00e5danne omst\u00e6ndigheder skal milliarder af operationer udf\u00f8res i hver node af tilbagekaldningstr\u00e6et. Det viser sig, at det simpelthen ikke er muligt at l\u00f8se opgaven inden for den afsatte tid.<\/p>\n

Lad os fors\u00f8ge at optimere l\u00f8sningen. Den minimale vertex-sk\u00e6ring mellem et par noder kan findes ved hj\u00e6lp af enhver algoritme, der bygger et maksimalt flow. Man kan anvende Dinic's algoritme<\/a><\/noindex>, som i praksis fungerer meget hurtigt. Jeg har en mistanke om, at man teoretisk kan bevise en tidsvurdering \"S\u00e5dan, hvilket allerede er helt acceptabelt.<\/p>\n

Jeg har fors\u00f8gt flere gange at finde sk\u00e6ringer mellem par af tilf\u00e6ldige noder og tage den mest afbalancerede derfra. Desv\u00e6rre gav dette d\u00e5rlige resultater i de \u00e5bne tests af PACE Challenge. Jeg sammenlignede med algoritmen, der bifurkede p\u00e5 maks. grad-noder, ved at k\u00f8re dem med en begr\u00e6nsning p\u00e5 dybden af nedstigning. Efter algoritmen, der fors\u00f8gte at finde en sk\u00e6ring p\u00e5 denne m\u00e5de, forblev der grafiker af st\u00f8rre st\u00f8rrelse. Dette skyldes, at sk\u00e6ringerne var meget ubalancerede: n\u00e5r man fjernede 5-10 noder, kunne man kun afsk\u00e6re 15-20.<\/p>\n

Det b\u00f8r n\u00e6vnes, at artikler om de teoretisk hurtigste algoritmer bruger meget mere avancerede teknikker til udvalg af noder til bifurkation. S\u00e5danne teknikker har en meget kompleks implementering og ofte d\u00e5rlige tids- og pladsvurderinger. Jeg har ikke v\u00e6ret i stand til at udpege brugbare fra disse.<\/p>\n

Hvordan man anvender forenklingeregler<\/h3>\n

Vi har allerede ideer til kernelesing. Lad mig minde om:<\/p>\n

    \n
  1. Hvis der er en isoleret node, skal den fjernes.<\/li>\n
  2. Hvis der er en knude med grad 1, skal den fjernes, og dens nabo tages som svar.<\/li>\n
  3. Hvis der er en knude med mindst k + 1<\/i>, tag den som svar.<\/li>\n<\/ol>\n

    Med de f\u00f8rste to er det klart, men der er en lille trick med den tredje. Hvis vi i den sjove opgave om baren fik et \u00f8vre begr\u00e6nsning p\u00e5 k<\/i>, s\u00e5 skal vi i PACE Challenge blot finde et minimalt st\u00f8rrelses vertex d\u00e6k. Dette er en typisk transformation af s\u00f8gningsopgaver (Search Problem) til beslutningsopgaver (Decision Problem), hvor der ofte ikke skelnes mellem de to typer opgaver. I praksis, hvis vi skriver en l\u00f8ser til vertex d\u00e6k-opgaven, kan der v\u00e6re forskel. For eksempel som i punkt tre.<\/p>\n

    Set fra implementeringens synspunkt kan vi gribe det an p\u00e5 to m\u00e5der. Den f\u00f8rste tilgang kaldes Iterative Deepening. Det g\u00e5r ud p\u00e5, at vi kan starte med en rimelig nedre gr\u00e6nse for svaret, og derefter k\u00f8re vores algoritme, hvor vi bruger denne gr\u00e6nse som en \u00f8vre begr\u00e6nsning for svaret, uden at dykke ned i rekursioner, der er lavere end denne gr\u00e6nse. Hvis vi har fundet et svar, er det garanteret optimalt; ellers kan vi \u00f8ge denne gr\u00e6nse med en enhed og starte forfra.<\/p>\n

    Den anden tilgang er at gemme et aktuelt optimalt svar og s\u00f8ge efter et svar af mindre st\u00f8rrelse og \u00e6ndre denne parameter, n\u00e5r vi finder et. k<\/i> for at sk\u00e6re bort un\u00f8dvendige grene i s\u00f8gningen.<\/p>\n

    Efter at have k\u00f8rt nogle nat eksperimenter, landede jeg p\u00e5 en kombination af disse to metoder: f\u00f8rst k\u00f8rer jeg min algoritme med en s\u00f8gemulighedsdybde (v\u00e6lger den, s\u00e5 den tager en ubetydelig tidsperiode i forhold til den prim\u00e6re l\u00f8sning) og bruger den bedste fundne l\u00f8sning som en \u00f8vre gr\u00e6nse for svaret \u2014 det vil sige netop det. k<\/i>.<\/p>\n

    Knuder med grad 2<\/h3>\n

    Vi har styr p\u00e5 knuderne med grad 0 og 1. Det viser sig, at det ogs\u00e5 kan g\u00f8res med knuder med grad 2, men dette kr\u00e6ver mere komplekse operationer i grafen.<\/p>\n

    For at forklare dette, skal vi p\u00e5 en eller anden m\u00e5de betegne knuderne. Lad os kalde en knude med grad 2 for knuden v<\/i>, og dens naboer som knuderne x<\/i> og y<\/i>. Derefter vil vi have to tilf\u00e6lde.<\/p>\n

      \n
    1. N\u00e5r x<\/i> og y<\/i> \u2014 naboer. S\u00e5 kan vi tage som svar x<\/i> og y<\/i>, og v<\/i> fjerne. Og det er sandt, i denne trekant skal vi tage mindst to knuder som svar, og vi vil bestemt ikke tabe, hvis vi tager x<\/i> og y<\/i>: de har sandsynligvis ogs\u00e5 andre naboer, mens v<\/i> de ikke har.<\/li>\n
    2. N\u00e5r x<\/i> og y<\/i> \u2014 ikke naboer. S\u00e5 p\u00e5st\u00e5s det, at alle tre toppe kan klistres sammen til \u00e9n. Ideen er, at der i s\u00e5 fald findes et optimalt svar, hvor vi tager enten v<\/i>, eller begge toppe x<\/i> og y<\/i>. I det f\u00f8rste tilf\u00e6lde skal vi tage alle naboer med i svaret x<\/i> og y<\/i>, mens det i det andet ikke er n\u00f8dvendigt. Dette svarer pr\u00e6cist til tilf\u00e6ldene, hvor vi ikke tager den klistrede top med i svaret, og n\u00e5r vi g\u00f8r. Det er kun tilbage at bem\u00e6rke, at svaret fra s\u00e5dan en operation reduceres med \u00e9n i begge tilf\u00e6lde.<\/li>\n<\/ol>\n

      \"S\u00e5dan<\/p>\n

      Det skal bem\u00e6rkes, at en s\u00e5dan tilgang er ret vanskelig at implementere korrekt p\u00e5 rimelig line\u00e6r tid. Klistre toppe \u2014 det er en kompleks operation, da man skal kopiere naboernes lister. Hvis man g\u00f8r dette uforsigtigt, kan man f\u00e5 et asymptotisk suboptimalt k\u00f8retid (f.eks. hvis man efter hver klistreoperation kopierer mange kanter). Jeg stoppede med at lede efter hele stier fra toppe med grad 2 og med at overveje en masse specielle tilf\u00e6lde, som cykler af s\u00e5danne toppe eller af alle s\u00e5danne toppe undtagen \u00e9n.<\/p>\n

      Derudover skal denne operation v\u00e6re reversibel, s\u00e5 vi kan genskabe grafen i sin oprindelige form, n\u00e5r vi vender tilbage fra rekursionen. For at sikre dette slettede jeg ikke listerne over kanter for de klistrede toppe; derefter vidste jeg simpelthen, hvilke kanter der skulle rettes mod hvor. En s\u00e5dan grafimplementering kr\u00e6ver ogs\u00e5 omhu, men sikrer en rimelig line\u00e6r tid. Og for grafer med flere titusinde kanter passer det udm\u00e6rket i CPU-cache, hvilket giver store hastighedsfordele.<\/p>\n

      Line\u00e6r kerne<\/h3>\n

      Endelig er den mest interessante del af kernen.<\/p>\n

      For det f\u00f8rste, lad os huske, at et minimalt vertex d\u00e6kke kan findes i bipartite grafer p\u00e5 \"S\u00e5dan. For dette skal vi bruge algoritmen Hopcroft-Karp<\/a><\/noindex> for at finde det maksimale match, og derefter anvende s\u00e6tningen K\u00f6nigs-Egervari<\/a><\/noindex>.<\/p>\n

      Ideen med den line\u00e6re kerne er som f\u00f8lger: f\u00f8rst opdeler vi grafen, det vil sige, i stedet for hver top v<\/i> opretter vi to toppe \"S\u00e5dan og \"S\u00e5dan, og i stedet for hver kant u \u2014 v<\/i> opretter vi to kanter \"S\u00e5dan og \"S\u00e5danDen opn\u00e5ede graf vil v\u00e6re to delte. Lad os finde en minimal hj\u00f8rne d\u00e6kning i den. Nogle hj\u00f8rner i den oprindelige graf vil blive d\u00e6kket to gange, nogle kun \u00e9n gang, og nogle slet ikke. Nemhauser-Trotter teoremet siger, at i s\u00e5 fald kan vi fjerne de hj\u00f8rner, der ikke er d\u00e6kket overhovedet, og tage dem, der er d\u00e6kket to gange, som svar. Desuden siger det, at blandt de tilbagev\u00e6rende hj\u00f8rner (dem, der er d\u00e6kket \u00e9n gang), skal vi tage mindst halvdelen som svar.<\/p>\n

      Vi har netop l\u00e6rt at efterlade i grafen ikke mere end 2k<\/i> hj\u00f8rner. Og det er sandt, hvis svaret best\u00e5r af mindst halvdelen af alle hj\u00f8rner, s\u00e5 er der ikke flere hj\u00f8rner end 2k<\/i>.<\/p>\n

      Her har jeg form\u00e5et at tage et lille skridt fremad. Det er klart, at den kerne, der er opbygget p\u00e5 denne m\u00e5de, afh\u00e6nger af, hvilken minimal hj\u00f8rne d\u00e6kning i den to delte graf vi har valgt. Man \u00f8nsker at v\u00e6lge en, s\u00e5 antallet af tilbagev\u00e6rende hj\u00f8rner er minimalt. Tidligere kunne dette kun g\u00f8res p\u00e5 tid \"S\u00e5dan. Jeg har dog opfundet en implementering af denne algoritme p\u00e5 tid \"S\u00e5dan, s\u00e5 denne kerne kan s\u00f8ges i grafer med hundrede tusinde hj\u00f8rner i hvert trin af branching.<\/p>\n

      Resultat<\/h3>\n

      Praksis viser, at min l\u00f8sning fungerer godt p\u00e5 tests med flere hundrede hj\u00f8rner og flere tusinde kanter. P\u00e5 s\u00e5danne tests kan man forvente, at l\u00f8sningen findes inden for en halv time. Sandsynligheden for at finde et svar inden for acceptabel tid stiger generelt, hvis der er tilstr\u00e6kkeligt mange hj\u00f8rner med h\u00f8j grad i grafen, for eksempel grad 10 og derover.<\/p>\n

      For at deltage i konkurrencen skulle l\u00f8sningerne sendes til optil.io<\/a><\/noindex>. If\u00f8lge det pr\u00e6senterede skema<\/a><\/noindex>, tager min l\u00f8sning tredjepladsen blandt tyve p\u00e5 \u00e5bne tests med en betydelig margen til andenpladsen. For at v\u00e6re helt \u00e6rlig er det ikke helt klart, hvordan l\u00f8sningerne vil blive bed\u00f8mt i selve konkurrencen: for eksempel min l\u00f8sning best\u00e5 f\u00e6rre tests end l\u00f8sningen p\u00e5 fjerdepladsen, men p\u00e5 dem, hvor den best\u00e5r, arbejder den hurtigere.<\/p>\n

      Resultaterne p\u00e5 de lukkede tests vil blive kendt den f\u00f8rste juli.<\/p>\n

      Kilde: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

      \u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u044b \u0441 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 Software Engineering \u0438 Machine Learning \u0447\u0430\u0441\u0442\u043e \u0438\u0434\u0443\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u041d\u0418\u0420\u044b \u0432 \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0438 (\u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c, JetBrains \u0438\u043b\u0438 \u042f\u043d\u0434\u0435\u043a\u0441, \u043d\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e). \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u0441\u0432\u043e\u0451\u043c \u043f\u0440\u043e\u0435\u043a\u0442\u0435 \u043f\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044e Computer Science. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":26562,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-35406","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Hvordan man l\u00f8ser NP-sv\u00e6re problemer med parametrisere algoritmer | ProHoster","description":"Forskning er nok den mest interessante del af vores uddannelse. Ideen er at pr\u00f8ve sig selv i den valgte retning allerede p\u00e5 universitetet.","canonical_url":"https:\/\/prohoster.info\/da\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"da_DK","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041a\u0430\u043a \u0440\u0435\u0448\u0430\u0442\u044c NP-\u0442\u0440\u0443\u0434\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 | ProHoster","og:description":"\u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438.","og:url":"https:\/\/prohoster.info\/da\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:04:08+00:00","article:modified_time":"2021-01-02T11:01:41+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"35406","title":null,"description":"","keywords":"","keyphrases":null,"primary_term":null,"canonical_url":"","og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 23:06:35","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:03:22","updated":"2026-01-21 23:06:35","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}