{"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\/de\/blog\/novosti-interneta\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Wie man NP-schwierige Probleme mit parametrisierten Algorithmen l\u00f6st","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Die wissenschaftliche Forschung ist wahrscheinlich der spannendste Teil unseres Studiums. Die Idee ist, sich bereits an der Universit\u00e4t in einem gew\u00e4hlten Bereich auszuprobieren. Zum Beispiel gehen Studenten der Fachrichtungen Software Engineering und Machine Learning oft zu Unternehmen f\u00fcr ihre Forschungsarbeiten (haupts\u00e4chlich JetBrains oder Yandex, aber nicht nur).<\/p>\n

In diesem Beitrag werde ich \u00fcber mein Projekt im Bereich der Computerwissenschaften berichten. Im Rahmen meiner Arbeit habe ich Ans\u00e4tze zur L\u00f6sung eines der bekanntesten NP-schwierigen Probleme untersucht und praktisch umgesetzt: das Vertex-Cover-Problem<\/b>.<\/p>\n

Derzeit entwickelt sich ein interessanter Ansatz f\u00fcr NP-schwierige Probleme sehr schnell \u2013 parametrisierten Algorithmen. Ich werde versuchen, Ihnen einen \u00dcberblick zu geben, einige einfache parametrisierten Algorithmen vorzustellen und eine leistungsstarke Methode zu beschreiben, die mir sehr geholfen hat. Meine Ergebnisse habe ich beim Wettbewerb PACE Challenge pr\u00e4sentiert: Nach den offenen Tests belegt meine L\u00f6sung den dritten Platz, und die endg\u00fcltigen Ergebnisse werden am 1. Juli bekannt gegeben.<\/p>\n

\"Wie
\n<\/a><\/noindex><\/p>\n

\u00dcber mich<\/h3>\n

Mein Name ist Wasilij Alfjorow, ich bin gerade im dritten Jahr an der Nationalen Forschungshochschule f\u00fcr Volkswirtschaft \u2013 Sankt Petersburg. Seit meiner Schulzeit in der Moskauer 179. Schule interessieren mich Algorithmen, und ich habe erfolgreich an Informatikwettbewerben teilgenommen.<\/p>\n

Eine endliche Anzahl von Fachleuten f\u00fcr parametrische Algorithmen betritt die Bar\u2026<\/h3>\n

Das Beispiel wurde aus dem Buch entnommen \u201eParametrisierte Algorithmen\u201c<\/a><\/noindex><\/i><\/p>\n

Stellen Sie sich vor, Sie sind der Barkeeper in einer kleinen Stadt. Jeden Freitagabend kommt die H\u00e4lfte der Stadt in Ihre Bar, um sich zu entspannen, was Ihnen einiges an M\u00fche bereitet: Sie m\u00fcssen st\u00f6rende G\u00e4ste herauswerfen, um Schl\u00e4gereien zu vermeiden. Schlie\u00dflich wird Ihnen das l\u00e4stig, und Sie beschlie\u00dfen, pr\u00e4ventive Ma\u00dfnahmen zu ergreifen.<\/p>\n

Da Ihre Stadt klein ist, wissen Sie genau, welche G\u00e4ste mit hoher Wahrscheinlichkeit miteinander aneinandergeraten, wenn sie zusammen in die Bar kommen. Sie haben eine Liste von n<\/i> Menschen, die heute Abend in die Bar kommen werden. Sie beschlie\u00dfen, einige B\u00fcrger nicht hereinzulassen, um sicherzustellen, dass sich niemand streitet. Gleichzeitig m\u00f6chte Ihre Vorgesetzte keine Gewinne verlieren und wird unzufrieden sein, wenn Sie nicht mehr als k<\/i> Personen in die Bar lassen.<\/p>\n

Leider ist das Problem, vor dem Sie stehen, ein klassisches NP-vollst\u00e4ndiges Problem. Vielleicht kennen Sie es als Vertex Cover<\/a><\/noindex>, oder als das Problem des Punkt\u00fcberdeckens. F\u00fcr solche Probleme sind im Allgemeinen keine Algorithmen bekannt, die in akzeptabler Zeit arbeiten. Genauer gesagt sagt die nicht bewiesene und ziemlich starke Hypothese ETH (Exponential Time Hypothesis), dass dieses Problem nicht in der Zeit gel\u00f6st werden kann \"Wie, was bedeutet, dass man nichts finden kann, was deutlich besser ist als eine vollst\u00e4ndige Exhaustion. Stellen Sie sich vor, in Ihre Bar kommen gleich n = 1000<\/i> Personen. Dann w\u00fcrde die vollst\u00e4ndige Exhaustion \"Wie Varianten generieren, was ungef\u00e4hr \"Wie \u2014 unglaublich viel ist. Gl\u00fccklicherweise hat Ihre Gesch\u00e4ftsf\u00fchrung Ihnen eine Begrenzung gesetzt auf k = 10<\/i>, sodass die Anzahl der Kombinationen, die Sie durchgehen m\u00fcssen, viel geringer ist: die Anzahl der Teilmengen von zehn Elementen ist \"Wie. Das ist schon besser, aber trotzdem kann man nicht einmal an einem leistungsstarken Cluster alle Optionen innerhalb eines Tages durchrechnen.
\n\"Wie
\nUm das Risiko von K\u00e4mpfen durch die angespannte Beziehung zwischen den Barbesuchern ausschlie\u00dfen zu k\u00f6nnen, m\u00fcssen Sie Bob, Daniel und Fyodor nicht einlassen. L\u00f6sungen, bei denen nur zwei ausgeschlossen sind, existieren nicht.<\/p>\n

Bedeutet das, dass es an der Zeit ist, aufzugeben und alle hereinzulassen? Lassen Sie uns andere Optionen betrachten. Zum Beispiel k\u00f6nnte man nur die Personen nicht einlassen, die wahrscheinlich mit einer sehr gro\u00dfen Anzahl von Menschen k\u00e4mpfen w\u00fcrden. Wenn jemand mit mindestens k + 1<\/i> anderen Personen k\u00e4mpfen kann, dann darf er auf keinen Fall hereingelassen werden \u2014 andernfalls m\u00fcssten Sie alle k + 1<\/i> Einwohner, mit denen er k\u00e4mpfen k\u00f6nnte, nicht reinlassen, was das Management sicherlich ver\u00e4rgern w\u00fcrde.<\/p>\n

Angenommen, Sie haben alle, die Sie konnten, nach diesem Prinzip ausgeschlossen. Dann k\u00f6nnten alle anderen nicht mehr mit k<\/i> Menschen k\u00e4mpfen. Wenn Sie daraus k<\/i> Personen ausschlie\u00dfen, k\u00f6nnen Sie nicht mehr als \"Wie Konflikte verhindern. Das hei\u00dft, wenn mehr als \"Wie Personen an mindestens einem Konflikt beteiligt sind, k\u00f6nnen Sie deren alle sicher nicht verhindern. Da, ganz klar, Sie garantiert diejenigen ohne Konflikte hereinzulassen, m\u00fcssen Sie alle Teilmengen der Gr\u00f6\u00dfe zehn aus zweihundert Personen durchgehen. Es gibt ungef\u00e4hr \"Wie, und eine solche Anzahl an Operationen kann bereits in einem Cluster durchgearbeitet werden.<\/p>\n

Wenn es m\u00f6glich ist, v\u00f6llig nicht konflikttr\u00e4chtige Personen aufzunehmen, wie steht es dann mit denen, die nur an einem Konflikt beteiligt sind? Tats\u00e4chlich k\u00f6nnen auch sie hereingelassen werden, w\u00e4hrend wir die T\u00fcr vor ihrem Gegner schlie\u00dfen. Ist es nicht so, dass, wenn Alice nur mit Bob in Konflikt steht, wir nichts verlieren, wenn wir Alice von beiden hereinlassen? Bob k\u00f6nnte andere Konflikte haben, w\u00e4hrend Alice definitiv keine hat. Es w\u00e4re au\u00dferdem sinnlos, beide nicht hereinzulassen. Nach solchen Operationen bleibt nicht mehr als \"Wie G\u00e4ste mit ungewisser Zukunft: Insgesamt haben wir \"Wie Konflikte, an denen jeweils zwei Teilnehmer beteiligt sind und jeder mindestens an zwei teilnimmt. Das bedeutet, wir m\u00fcssen insgesamt nur \"Wie Varianten durchgehen, was durchaus an einem halben Tag auf einem Laptop machbar ist.<\/p>\n

In der Tat k\u00f6nnen wir mit einfachen \u00dcberlegungen noch attraktivere Bedingungen erzielen. Es ist wichtig, dass wir alle Streitigkeiten l\u00f6sen, das hei\u00dft, aus jedem strittigen Paar mindestens eine Person auszuw\u00e4hlen, die wir nicht zulassen werden. Betrachten wir einen Algorithmus: Wir nehmen einen Konflikt, entfernen einen Teilnehmer und starten rekursiv mit den verbleibenden. Dann entfernen wir den anderen und starten ebenfalls rekursiv. Da wir in jedem Schritt jemanden ausschlie\u00dfen, ist der Rekursionsbaum eines solchen Algorithmus ein bin\u00e4rer Baum mit einer Tiefe k<\/i>, sodass der Algorithmus insgesamt f\u00fcr \"Wie, wobei n<\/i> \u2014 die Anzahl der Knoten, und m<\/i> \u2014 die Anzahl der Kanten. In unserem Beispiel sind das etwa zehn Millionen, was in Bruchteilen von Sekunden nicht nur auf einem Laptop, sondern sogar auf einem Mobiltelefon berechnet werden kann.<\/p>\n

Das obige Beispiel ist ein Beispiel f\u00fcr einen parametrisierten Algorithmus<\/b>. Parametrisierte Algorithmen sind Algorithmen, die in der Zeit f(k) poly(n)<\/i>, wobei p<\/i> \u2014 ein Polynom, f<\/i> \u2014 eine beliebige berechenbare Funktion, und k<\/i> \u2014 ein Parameter, der m\u00f6glicherweise viel kleiner als die Gr\u00f6\u00dfe des Problems ist.<\/p>\n

Alle \u00dcberlegungen bis zu diesem Algorithmus f\u00fchren das Beispiel an der Kernelisierung<\/b> \u2014 eine der g\u00e4ngigen Techniken zur Erstellung parametrischer Algorithmen. Kernisierung bezeichnet die Reduzierung der Aufgabengr\u00f6\u00dfe auf einen Wert, der durch eine Funktion vom Parameter begrenzt wird. Die resultierende Aufgabe wird oft als Kern bezeichnet. So haben wir durch einfache \u00dcberlegungen bez\u00fcglich der Gradanzahl ein quadratisches Kern f\u00fcr das Vertex Cover Problem erhalten, parametrisiert nach der Antwortgr\u00f6\u00dfe. Es gibt auch andere Parameter, die f\u00fcr dieses Problem ausgew\u00e4hlt werden k\u00f6nnen (zum Beispiel Vertex Cover Above LP), jedoch werden wir genau diesen Parameter diskutieren.<\/p>\n

Pace Challenge<\/h3>\n

Wettbewerb PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) wurde 2015 ins Leben gerufen, um eine Verbindung zwischen parametrisierten Algorithmen und den in der Praxis verwendeten Ans\u00e4tzen zur L\u00f6sung von Berechnungsproblemen herzustellen. Die ersten drei Wettbewerbe waren der Suche nach der Baumweite eines Graphen (Baumweite<\/a><\/noindex>), der Suche nach einem Steinerbaum (Steinerbaum<\/a><\/noindex>) und der Suche nach einer Menge von Knoten, die Zyklen durchtrennt (Feedback Vertex Set<\/a><\/noindex>). In diesem Jahr war eine der Aufgaben, in denen man sein K\u00f6nnen unter Beweis stellen konnte, das oben beschriebene Problem des Knoten\u00fcberdeckens.<\/p>\n

Die Veranstaltung gewinnt Jahr f\u00fcr Jahr an Popularit\u00e4t. Laut vorl\u00e4ufigen Daten haben in diesem Jahr allein im Wettbewerb um das Vertex Cover Problem 24 Teams teilgenommen. Es ist erw\u00e4hnenswert, dass das Event nicht nur wenige Stunden oder eine Woche dauert, sondern mehrere Monate. Die Teams haben die M\u00f6glichkeit, Literatur zu studieren, ihre eigenen originellen Ideen zu entwickeln und diese umzusetzen. Im Grunde genommen handelt es sich bei diesem Wettbewerb um eine Forschungsarbeit. Die besten Ideen und die Auszeichnung der Gewinner finden gemeinsam mit der Konferenz statt. IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) im Rahmen des gr\u00f6\u00dften j\u00e4hrlichen Algorithmus-Meetings in Europa ALGO<\/a><\/noindex>. Weitere Informationen zum Wettbewerb finden Sie auf Webseite<\/a><\/noindex>, w\u00e4hrend die Ergebnisse der Vorjahre hier verf\u00fcgbar sind. hier<\/a><\/noindex>.<\/p>\n

L\u00f6sungsdiagramm<\/h3>\n

Um das Problem der Spitzenabdeckung zu l\u00f6sen, habe ich versucht, parametrisierte Algorithmen anzuwenden. Diese bestehen in der Regel aus zwei Teilen: Vereinfachungsregeln (die idealerweise zu einer Kernerstellung f\u00fchren) und Aufspaltungsregeln. Die Vereinfachungsregeln sind eine Vorverarbeitung der Eingabe in polynomialer Zeit. Ziel dieser Regeln ist es, das Problem auf ein \u00e4quivalentes, kleineres Problem zu reduzieren. Die Vereinfachungsregeln stellen den kostenintensivsten Teil des Algorithmus dar, und die Anwendung genau dieses Teils f\u00fchrt zu einer Gesamtlaufzeit anstelle einfach polynomialer Zeit. \"Wie In unserem Fall basieren die Aufspaltungsregeln darauf, dass f\u00fcr jede Spitze entweder sie selbst oder ihr Nachbar in Betracht gezogen werden muss.<\/p>\n

Das allgemeine Schema sieht folgenderma\u00dfen aus: Wir wenden die Vereinfachungsregeln an, w\u00e4hlen dann eine Spitze aus und f\u00fchren zwei rekursive Aufrufe durch: Im ersten Fall nehmen wir sie in die Antwort auf, im anderen Fall nehmen wir alle ihre Nachbarn. Dies nennen wir das Aufspalten (Branching) an dieser Spitze.<\/p>\n

In diesen Rahmen wird genau eine Erg\u00e4nzung im n\u00e4chsten Absatz eingef\u00fchrt.<\/p>\n

Ideen f\u00fcr Aufspaltungsregeln (Branching)<\/h3>\n

Lassen Sie uns besprechen, wie wir den Knoten ausw\u00e4hlen, an dem die Zerlegung erfolgen soll.
\nDie Grundidee ist algorithmisch sehr gierig: Lassen Sie uns den Knoten mit der maximalen Gradzahl w\u00e4hlen und genau an diesem Punkt die Zerlegung durchf\u00fchren. Warum scheint das besser zu sein? Weil wir auf diese Weise im zweiten Zweig des rekursiven Aufrufs viele Knoten entfernen k\u00f6nnen. Man kann davon ausgehen, dass ein kleinerer Graph \u00fcbrig bleibt, auf dem wir dann schnell arbeiten k\u00f6nnen.<\/p>\n

Dieser Ansatz zusammen mit den bereits besprochenen einfachen Kerneltechniken zeigt sich recht vielversprechend und kann Tests mit mehreren tausend Knoten l\u00f6sen. Allerdings funktioniert er bei kubischen Grafen (das hei\u00dft bei Graphen, deren Grad jeder Knoten drei betr\u00e4gt) nicht gut.
\nEs gibt noch eine weitere Idee, die auf einem recht einfachen Gedanken basiert: Wenn der Graph nicht zusammenh\u00e4ngend ist, k\u00f6nnen die Aufgaben zur Verbindung seiner Komponenten unabh\u00e4ngig gel\u00f6st werden, indem die Antworten am Ende zusammengef\u00fchrt werden. Dies ist \u00fcbrigens die kleine, versprochene Modifikation im Schema, die die L\u00f6sung erheblich beschleunigen wird: Fr\u00fcher haben wir in einem solchen Fall mit dem Produkt der Zeit f\u00fcr das Z\u00e4hlen der Antworten der Komponenten gearbeitet, jetzt arbeiten wir mit der Summe. Und um das Branching zu beschleunigen, m\u00fcssen wir den zusammenh\u00e4ngenden Graphen in einen nicht zusammenh\u00e4ngenden umwandeln.<\/p>\n

Wie macht man das? Wenn im Graphen ein Verzweigungspunkt vorhanden ist, sollten wir genau an diesem Punkt branchieren. Ein Verzweigungspunkt ist ein Knoten, dessen Entfernung den Graphen nicht mehr zusammenh\u00e4ngend macht. Alle Verzweigungspunkte im Graphen k\u00f6nnen mit einem klassischen Algorithmus in linearer Zeit gefunden werden. Dieser Ansatz beschleunigt das Branching erheblich.
\n\"Wie
\nBei der Entfernung eines der hervorgehobenen Knoten wird der Graph in Komponenten zerfallen.<\/p>\n

Das k\u00f6nnen wir tun, aber wir streben mehr an. Zum Beispiel, kleine minimale Scheitel-Schnitte in Graphen zu suchen und eine Aufteilung an den Scheitelpunkten durchzuf\u00fchren. Der effizienteste mir bekannte Weg, um einen minimalen globalen Scheitel-Schnitt zu finden, ist die Anwendung des Gomory-Hu-Baums, der in kubischer Zeit aufgebaut wird. Bei der PACE Challenge liegt die typische Gr\u00f6\u00dfe des Graphen bei mehreren tausend Knoten. In einem solchen Szenario m\u00fcssen in jedem Knoten des Rekursionsbaums Milliarden von Operationen durchgef\u00fchrt werden. Daher ist es einfach unm\u00f6glich, das Problem innerhalb der vorgegebenen Zeit zu l\u00f6sen.<\/p>\n

Lassen Sie uns versuchen, die L\u00f6sung zu optimieren. Den minimalen Scheitel-Schnitt zwischen einem Paar von Knoten kann man mit jedem Algorithmus finden, der den maximalen Fluss bestimmt. Man kann in ein solches Netzwerk den Dinic-Algorithmus<\/a><\/noindex>, einsetzen, der in der Praxis sehr schnell arbeitet. Ich habe den Verdacht, dass man theoretisch eine Laufzeitscha\u0308tzung beweisen kann \"Wie, was bereits durchaus akzeptabel ist.<\/p>\n

Ich habe mehrmals versucht, Schnitte zwischen Paaren zuf\u00e4lliger Knoten zu finden und die ausgewogensten auszuw\u00e4hlen. Leider brachte das bei den \u00f6ffentlichen Tests des PACE Challenge schlechte Ergebnisse. Ich habe es mit einem Algorithmus verglichen, der an Knoten mit maximaler Gradzahl aufteilte und diese mit einer Einschr\u00e4nkung auf die L\u00f6sungstiefe ausf\u00fchrte. Nach dem Algorithmus, der versuchte, auf diese Weise Schnitte zu finden, blieben gr\u00f6\u00dfere Graphen \u00fcbrig. Das liegt daran, dass die Schnitte sehr unausgewogen waren: Wenn man 5-10 Knoten entfernte, konnte man nur 15-20 abspalten.<\/p>\n

Es ist erw\u00e4hnenswert, dass in Artikeln \u00fcber theoretisch die schnellsten Algorithmen wesentlich fortschrittlichere Techniken zur Auswahl von Knoten f\u00fcr das Abspalten verwendet werden. Diese Techniken haben eine sehr komplexe Implementierung und oft eine schlechte Bewertung bez\u00fcglich Zeit und Speicher. Es ist mir nicht gelungen, aus ihnen praktikable L\u00f6sungen zu gewinnen.<\/p>\n

Wie man die Vereinfachungsregeln anwendet<\/h3>\n

Wir haben bereits Ideen zur Kernellisierung. Ich erinnere daran:<\/p>\n

    \n
  1. Wenn es einen isolierten Knoten gibt, entfernen Sie ihn.<\/li>\n
  2. Wenn es einen Knoten mit Grad 1 gibt, entfernen Sie ihn und nehmen Sie seinen Nachbarn als Ergebnis.<\/li>\n
  3. Wenn es einen Knoten mit mindestens k + 1<\/i>, nehmen Sie ihn als Ergebnis.<\/li>\n<\/ol>\n

    Bei den ersten beiden ist alles klar, aber bei der dritten gibt es einen kleinen Trick. Wenn uns in der humorvollen Aufgabenstellung \u00fcber die Bar eine obere Grenze vorgegeben wurde, geht es beim PACE Challenge darum, eine minimale Deckung zu finden. Dies ist eine typische Umwandlung von Suchproblemen (Search Problem) in Entscheidungsprobleme (Decision Problem), oft wird zwischen den beiden Arten von Aufgaben nicht unterschieden. In der Praxis k\u00f6nnte es jedoch Unterschiede geben, wenn wir einen Solver f\u00fcr das Deckungsproblem schreiben, wie im dritten Punkt erw\u00e4hnt. k<\/i>In Bezug auf die Implementierung gibt es zwei Ans\u00e4tze. Der erste Ansatz wird als Iterative Deepening bezeichnet. Die Idee ist folgende: Wir k\u00f6nnen mit einer gewissen sinnvollen Untergrenze f\u00fcr die Antwort beginnen und dann unseren Algorithmus starten, wobei wir diese Grenze als obere Begrenzung der Antwort verwenden, ohne tiefer in die Rekursion abzutauchen, als es diese Grenze zul\u00e4sst. Wenn wir eine Antwort finden, ist sie garantiert optimal, ansonsten k\u00f6nnen wir diese Grenze um eins erh\u00f6hen und erneut starten.<\/p>\n

    Der andere Ansatz besteht darin, eine aktuelle optimale Antwort zu speichern und nach einer kleineren Antwort zu suchen, und beim Finden diese Parameter zu \u00e4ndern,<\/p>\n

    um \u00fcberfl\u00fcssige \u00c4ste im Suchprozess besser abzuschneiden. k<\/i> um \u00fcberfl\u00fcssige Verzweigungen in der Suche weiter zu reduzieren.<\/p>\n

    Nach einigen n\u00e4chtlichen Experimenten habe ich mich auf eine Kombination dieser beiden Ans\u00e4tze geeinigt: Zuerst f\u00fchre ich meinen Algorithmus mit einer Begrenzung der Suchtiefe aus (ich w\u00e4hle sie so, dass sie im Vergleich zur Hauptl\u00f6sung nahezu vernachl\u00e4ssigbar ist) und nutze die beste gefundene L\u00f6sung als obere Grenze f\u00fcr die Antwort \u2014 also f\u00fcr genau das. k<\/i>.<\/p>\n

    Knoten vom Grad 2<\/h3>\n

    Wir haben die Knoten vom Grad 0 und 1 gekl\u00e4rt. Es stellt sich heraus, dass dies auch f\u00fcr Knoten vom Grad 2 funktioniert, aber daf\u00fcr sind komplexere Operationen am Graphen erforderlich.<\/p>\n

    Um dies zu erkl\u00e4ren, m\u00fcssen die Knoten irgendwie gekennzeichnet werden. Nennen wir einen Knoten vom Grad 2 einen Knoten v<\/i>, und seine Nachbarn \u2014 Knoten x<\/i> und y<\/i>. Danach haben wir zwei F\u00e4lle.<\/p>\n

      \n
    1. Wenn x<\/i> und y<\/i> \u2014 Nachbarn sind. Dann k\u00f6nnen wir als Antwort nehmen x<\/i> und y<\/i>, und v<\/i> l\u00f6schen. Tats\u00e4chlich m\u00fcssen wir aus diesem Dreieck mindestens zwei Knoten in die Antwort aufnehmen, und wir verlieren sicher nicht, wenn wir x<\/i> und y<\/i>: sie haben wahrscheinlich noch weitere Nachbarn, w\u00e4hrend v<\/i> sie nicht haben.<\/li>\n
    2. Wenn x<\/i> und y<\/i> \u2014 keine Nachbarn sind. Dann wird behauptet, dass alle drei Knoten zu einem zusammengeklebt werden k\u00f6nnen. Die Idee ist, dass in diesem Fall eine optimale Antwort existiert, die wir entweder v<\/i>oder beide Knoten aufnehmen. x<\/i> und y<\/i>. Im ersten Fall m\u00fcssen wir daher alle Nachbarn ber\u00fccksichtigen x<\/i> und y<\/i>, im zweiten Fall ist das nicht unbedingt erforderlich. Dies entspricht genau den F\u00e4llen, in denen wir die zusammengef\u00fcgte Spitze nicht ber\u00fccksichtigen und wenn wir es tun. Man sollte nur beachten, dass in beiden F\u00e4llen das Ergebnis dieser Operation um eins verringert wird.<\/li>\n<\/ol>\n

      \"Wie<\/p>\n

      Es ist zu beachten, dass es ziemlich schwierig ist, einen solchen Ansatz in linearer Zeit korrekt umzusetzen. Das Zusammenf\u00fcgen von Spitzen ist eine komplexe Operation, die das Kopieren von Nachbarlisten erfordert. Wenn dies nicht sorgf\u00e4ltig durchgef\u00fchrt wird, kann dies asymptotisch suboptimale Laufzeiten zur Folge haben (zum Beispiel wenn nach jedem Zusammenf\u00fcgen viele Kanten kopiert werden). Ich habe mich darauf konzentriert, ganze Pfade von Spitzen mit Grad 2 zu finden und viele Sonderf\u00e4lle wie Zyklen aus solchen Spitzen oder aus allen solchen Spitzen bis auf eine zu analysieren.<\/p>\n

      Dar\u00fcber hinaus ist es notwendig, dass dieser Vorgang umkehrbar ist, um w\u00e4hrend der R\u00fcckkehr aus der Rekursion das Graf wieder in seinen urspr\u00fcnglichen Zustand zu versetzen. Um dies zu gew\u00e4hrleisten, habe ich die Listen der Kanten der zusammengef\u00fchrten Knoten nicht geleert; ich wusste dann einfach, welche Kanten wohin geleitet werden m\u00fcssen. Eine solche Implementierung von Graphen erfordert ebenfalls Sorgfalt, sorgt jedoch f\u00fcr eine ehrliche lineare Zeit. Au\u00dferdem passt sie bei Graphen mit mehreren zehntausend Kanten gut in den Cache des Prozessors, was gro\u00dfe Geschwindigkeitsvorteile bietet.<\/p>\n

      Lineares Kern<\/h3>\n

      Schlie\u00dflich der interessanteste Teil des Kerns.<\/p>\n

      Beginnen wir damit, dass wir uns erinnern, dass in bipartiten Graphen das minimale Deckenelement in \"Wiegesucht werden kann. Daf\u00fcr muss der Algorithmus Hopcroft-Karp<\/a><\/noindex> verwendet werden, um dort das maximale Paar zu finden, und dann die Theorem von K\u00f6nig-Egerv\u00e1ry<\/a><\/noindex>.<\/p>\n

      Die Idee des linearen Kerns ist folgende: Zuerst teilen wir den Graphen, das hei\u00dft, anstelle jeder Ecke v<\/i> f\u00fchren wir zwei Ecken ein \"Wie und \"Wie, und anstelle jeder Kante u \u2014 v<\/i> f\u00fchren wir zwei Kanten ein \"Wie und \"Wie. Der erhaltene Graph wird bipartit sein. Wir finden darin die minimale Vertex-Abdeckung. Einige Knoten des urspr\u00fcnglichen Graphen werden dort zweimal, einige einmal und einige gar nicht erscheinen. Der Satz von Nemhauser-Trotter besagt, dass in einem solchen Fall Knoten, die kein einziges Mal erfasst wurden, entfernt werden k\u00f6nnen und wir die Knoten, die zweimal erfasst wurden, als Ergebnis nehmen sollten. Dar\u00fcber hinaus besagt er, dass aus den verbleibenden Knoten (denjenigen, die einmal erfasst wurden) mindestens die H\u00e4lfte als Ergebnis genommen werden muss.<\/p>\n

      Gerade haben wir gelernt, im Graphen nicht mehr als 2k<\/i> Knoten zu belassen. In der Tat, wenn im Ergebnis mindestens die H\u00e4lfte aller Knoten verbleibt, dann gibt es dort nicht mehr als 2k<\/i>.<\/p>\n

      Hier ist mir ein kleiner Fortschritt gelungen. Es ist klar, dass das auf diese Weise konstruierte Kern von dem abh\u00e4ngt, welches minimale Vertex-Abdeckung im bipartiten Graphen wir gew\u00e4hlt haben. Man m\u00f6chte so eine w\u00e4hlen, dass die Anzahl der verbleibenden Knoten minimal ist. Fr\u00fcher konnte man das nur in der Zeit \"Wie. Ich habe jedoch eine Implementierung dieses Algorithmus in der Zeit gefunden \"Wie, sodass dieses Kern auf Graphen mit Hunderttausenden von Knoten in jeder Phase des Branching gesucht werden kann.<\/p>\n

      Ergebnis<\/h3>\n

      Die Praxis zeigt, dass meine L\u00f6sung bei Tests mit mehreren Hundert Knoten und mehreren Tausend Kanten gut funktioniert. Bei solchen Tests kann man durchaus damit rechnen, dass die L\u00f6sung innerhalb von einer halben Stunde gefunden wird. Die Wahrscheinlichkeit, eine Antwort in angemessener Zeit zu finden, steigt grunds\u00e4tzlich, wenn im Graphen gen\u00fcgend Knoten mit hoher Knotengrad vorhanden sind, beispielsweise mit einem Grad von 10 und mehr.<\/p>\n

      Um am Wettbewerb teilzunehmen, mussten die L\u00f6sungen an optil.io<\/a><\/noindex>eingereicht werden. Laut der dort pr\u00e4sentierten Tabelle<\/a><\/noindex>belegt meine L\u00f6sung bei den offenen Tests den dritten Platz von zwanzig und liegt deutlich vor dem zweiten Platz. Um ganz ehrlich zu sein, bleibt unklar, wie die L\u00f6sungen im Wettbewerb tats\u00e4chlich bewertet werden: Meine L\u00f6sung besteht zwar weniger Tests als die L\u00f6sung auf dem vierten Platz, ist aber bei den Tests, die sie besteht, schneller.<\/p>\n

      Die Ergebnisse der geschlossenen Tests werden am ersten Juli bekannt gegeben.<\/p>\n

      Quelle: 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-novosti-interneta"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\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\n","aioseo_head_json":{"title":"\ud83e\udd47So l\u00f6sen Sie NP-schwere Aufgaben mit parametrisierten Algorithmen | ProHoster","description":"Wissenschaftliche Arbeiten sind wahrscheinlich der interessanteste Teil unseres Studiums. Die Idee ist, bereits w\u00e4hrend des Studiums Erfahrungen in einem gew\u00e4hlten Bereich zu sammeln. Beispielsweise gehen Studierende der Fachrichtungen Software Engineering und Machine Learning h\u00e4ufig in Unternehmen (haupts\u00e4chlich JetBrains oder Yandex, aber nicht nur), um Forschungsprojekte zu realisieren. In diesem Beitrag werde ich \u00fcber mein Projekt im Bereich Informatik berichten.","canonical_url":"https:\/\/prohoster.info\/de\/blog\/novosti-interneta\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"de_DE","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. \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.","og:url":"https:\/\/prohoster.info\/de\/blog\/novosti-interneta\/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"},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}