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

Die wissenschaftliche Forschungsarbeit ist, denke ich, der interessanteste Teil unserer Ausbildung. Die Idee ist, bereits w\u00e4hrend des Studiums in das gew\u00e4hlte Fachgebiet hineinzuschnuppern. Zum Beispiel gehen Studenten der Richtungen Software Engineering und Machine Learning oft in Unternehmen (vor allem JetBrains oder Yandex, aber nicht nur), um Forschungsprojekte zu machen.<\/p>\n

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

Derzeit entwickelt sich ein interessanter Ansatz zu NP-schweren Problemen sehr schnell - parametrische Algorithmen. Ich werde versuchen, Sie auf den neuesten Stand zu bringen, Ihnen einige einfache parametrische Algorithmen vorzustellen und eine m\u00e4chtige Methode zu beschreiben, die mir sehr geholfen hat. Meine Ergebnisse habe ich beim PACE Challenge-Wettbewerb pr\u00e4sentiert: Nach den Ergebnissen der 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 Wassili Alferow, ich beende derzeit das dritte Jahr an der Higher School of Economics in St. Petersburg. Seit meiner Schulzeit interessiere ich mich f\u00fcr Algorithmen, als ich in der Moskauer Schule Nr. 179 war und erfolgreich an Informatikwettbewerben teilnahm.<\/p>\n

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

Das Beispiel stammt aus dem Buch \u201eParameterized algorithms\u201c<\/a><\/noindex><\/i><\/p>\n

Stellen Sie sich vor, Sie sind der Sicherheitsbeamte einer Bar in einer kleinen Stadt. Jeden Freitag kommt die H\u00e4lfte der Stadt in Ihre Bar, um sich zu entspannen, was Ihnen eine Menge \u00c4rger bereitet: Sie m\u00fcssen raufenden Kunden aus der Bar werfen, um Schl\u00e4gereien zu vermeiden. Irgendwann wird Ihnen das zu langweilig, und Sie beschlie\u00dfen, pr\u00e4ventive Ma\u00dfnahmen zu ergreifen.<\/p>\n

Da Ihre Stadt klein ist, wissen Sie genau, welche Paare von G\u00e4sten mit hoher Wahrscheinlichkeit in der Bar aneinandergeraten, wenn sie zusammen sind. Sie haben eine Liste von n<\/i> Personen, die heute Abend in die Bar kommen werden. Sie entscheiden sich, bestimmte B\u00fcrger nicht in die Bar zu lassen, sodass es keinen Streit gibt. Gleichzeitig m\u00f6chte Ihre Chefetage keinen Gewinn verlieren und wird unzufrieden sein, wenn Sie mehr als k<\/i> Personen nicht in die Bar lassen.<\/p>\n

Leider ist das Problem, vor dem Sie stehen, ein klassisches NP-schweres Problem. Vielleicht kennen Sie es als Vertex Cover.<\/a><\/noindex>, oder als Problem der Knotenabdeckung. F\u00fcr solche Aufgaben sind im Allgemeinen keine Algorithmen bekannt, die in akzeptabler Zeit arbeiten. Genauer gesagt besagt die nicht bewiesene und ziemlich starke Hypothese ETH (Exponential Time Hypothesis), dass dieses Problem nicht in polynomialer Zeit gel\u00f6st werden kann. \"Wie, das hei\u00dft, dass man merklich nichts Besseres als vollst\u00e4ndige Durchmusterung erfinden kann. Nehmen wir zum Beispiel an, es m\u00f6chten n = 1000<\/i> Menschen in Ihre Bar kommen. Dann betr\u00e4gt die vollst\u00e4ndige Durchmusterung \"Wie Varianten, was ungef\u00e4hr \"Wie \u2014 unvorstellbar viel ist. Zum Gl\u00fcck hat Ihr Management Ihnen eine Einschr\u00e4nkung gesetzt k = 10<\/i>, sodass die Anzahl der Kombinationen, die Sie durchprobieren m\u00fcssen, viel kleiner ist: die Anzahl der Teilmengen von zehn Elementen betr\u00e4gt \"Wie. Das ist schon besser, aber trotzdem ist es unm\u00f6glich, dies in einem Tag auch nur auf einem leistungsstarken Cluster zu z\u00e4hlen.
\n\"Wie
\nUm die Wahrscheinlichkeit von Streitigkeiten bei einer solchen Konfiguration gespannter Beziehungen zwischen den Barbesuchern auszuschlie\u00dfen, d\u00fcrfen Sie Bob, Daniel und Fyodor nicht hineinlassen. Es gibt keine L\u00f6sung, bei der nur zwei drau\u00dfen bleiben.<\/p>\n

Bedeutet das, dass es an der Zeit ist, aufzugeben und alle hereinzulassen? Lassen Sie uns andere Optionen pr\u00fcfen. Nun, man k\u00f6nnte beispielsweise nur diejenigen nicht hereinlassen, die wahrscheinlich mit vielen Leuten streiten werden. Wenn jemand mit mindestens k + 1<\/i> anderen Leuten streiten kann, darf er auf keinen Fall hereingelassen werden \u2013 sonst m\u00fcssen Sie alle k + 1<\/i> B\u00fcrger, mit denen er sich streiten k\u00f6nnte, drau\u00dfen lassen, was das Management sicherlich ver\u00e4rgern wird.<\/p>\n

Angenommen, Sie haben alle, die Sie konnten, nach diesem Prinzip ausgeschlossen. Dann k\u00f6nnen alle anderen nicht mit mehr als k<\/i> Leuten streiten. Wenn Sie aus ihnen k<\/i> Menschen ausschlie\u00dfen, k\u00f6nnen Sie nicht mehr als \"Wie Konflikte verhindern. Das bedeutet, wenn mehr als \"Wie Menschen an mindestens einem Konflikt beteiligt sind, werden Sie sicher nicht alle verhindern k\u00f6nnen. Da Sie, wie klar ist, die v\u00f6llig konfliktfreien Personen auf jeden Fall hineinlassen werden, m\u00fcssen Sie alle Teilmengen der Gr\u00f6\u00dfe zehn aus zweihundert Menschen durchprobieren. Das sind ungef\u00e4hr \"Wie, und eine solche Anzahl von Operationen l\u00e4sst sich bereits auf einem Cluster durchprobieren.<\/p>\n

Wenn es m\u00f6glich ist, v\u00f6llig unkonfliktuale Pers\u00f6nlichkeiten zu ber\u00fccksichtigen, was ist dann mit denen, die nur an einem Konflikt beteiligt sind? Tats\u00e4chlich k\u00f6nnen auch sie herein gelassen werden, indem wir die T\u00fcren vor ihrem Gegner schlie\u00dfen. Und tats\u00e4chlich, wenn Alice nur mit Bob in Konflikt steht, gewinnen wir nichts, wenn wir von den beiden Alice hineinlassen: Bob kann andere Konflikte haben, w\u00e4hrend Alice sicher keine hat. Es macht also keinen Sinn, beide nicht hereinzulassen. Nach solchen Operationen bleibt nicht mehr als \"Wie die G\u00e4ste mit ungewisser Schicksal: insgesamt haben wir \"Wie Konflikte, an denen jeweils zwei Teilnehmer beteiligt sind und jeder mindestens an zweien teilnimmt. Das bedeutet, wir m\u00fcssen nur insgesamt \"Wie Varianten durchgehen, was durchaus als einen halben Tag auf einem Laptop gelten kann.<\/p>\n

Tats\u00e4chlich k\u00f6nnen wir mit einfachen \u00dcberlegungen noch attraktivere Bedingungen erreichen. Beachten wir, dass wir alle Streitigkeiten unbedingt kl\u00e4ren m\u00fcssen, das hei\u00dft, aus jedem Konfliktpaar mindestens eine Person auszuw\u00e4hlen, die wir nicht hineinlassen werden. Betrachten wir einen solchen Algorithmus: Wir nehmen einen beliebigen Konflikt, entfernen einen Teilnehmer und starten rekursiv mit dem Rest, anschlie\u00dfend entfernen wir den anderen und starten ebenfalls rekursiv. Da wir bei jedem Schritt jemanden ausschlie\u00dfen, ist der Rekursionsbaum eines solchen Algorithmus ein bin\u00e4rer Baum der Tiefe k<\/i>, daher l\u00e4uft der Algorithmus insgesamt in \"Wie

n<\/i> \u2013 der Anzahl der Knoten, und m<\/i> \u2013 der Anzahl der Kanten. In unserem Beispiel sind das etwa zehn Millionen, was in Bruchteilen von Sekunden nicht nur auf dem Laptop, sondern sogar auf einem Mobiltelefon berechnet werden kann.<\/p>\n

Das oben angef\u00fchrte Beispiel ist ein Beispiel f\u00fcr einen parametrisierten Algorithmus<\/b>. Parametrisierte Algorithmen sind Algorithmen, die in der Zeit arbeiten f(k) poly(n)<\/i>

p<\/i> \u2013 ein Polynom, f<\/i> \u2013 eine beliebige berechenbare Funktion, und k<\/i> \u2013 ein Parameter, der m\u00f6glicherweise viel kleiner ist als die Gr\u00f6\u00dfe des Problems.<\/p>\n

Alle \u00dcberlegungen bis zu diesem Algorithmus f\u00fchren zum Beispiel von Kernelisierung<\/b> \u2014 eine der allgemeinen Techniken zur Erstellung parametrisierter Algorithmen. Kernelisation ist die Reduzierung der Gr\u00f6\u00dfe eines Problems auf einen Wert, der durch eine Funktion des Parameters begrenzt wird. Das erhaltene Problem wird oft als Kern bezeichnet. So haben wir durch einfache \u00dcberlegungen zu den Graden der Knoten einen quadratischen Kern f\u00fcr das Problem des Vertex Cover erhalten, parametrisiert durch die Gr\u00f6\u00dfe der Antwort. Es gibt auch andere Parameter, die f\u00fcr dieses Problem gew\u00e4hlt werden k\u00f6nnen (zum Beispiel Vertex Cover Above LP), aber wir werden genau \u00fcber diesen Parameter sprechen.<\/p>\n

Pace Challenge<\/h3>\n

Wettbewerb PACE Challenge<\/a><\/noindex> (Die Herausforderung der parametrisierten Algorithmen und rechnerischen Experimente) entstand 2015, um eine Verbindung zwischen parametrisierten Algorithmen und den in der Praxis verwendeten Ans\u00e4tzen zur L\u00f6sung von Rechenproblemen herzustellen. Die ersten drei Wettbewerbe waren dem Finden der Baumweite eines Graphen (Treewidth<\/a><\/noindex>), dem Finden eines Steiner-Baums (Steiner Tree<\/a><\/noindex>) und dem Finden eines Satzes von Knoten, der Zyklen schneidet (Feedback Vertex Set<\/a><\/noindex>). In diesem Jahr war eine der Aufgaben, in denen man sein K\u00f6nnen versuchen konnte, das oben beschriebene Problem des Vertex Cover.<\/p>\n

Der Wettbewerb gewinnt von Jahr zu Jahr an Popularit\u00e4t. Wenn man den vorl\u00e4ufigen Daten Glauben schenken darf, haben in diesem Jahr alleine beim Wettbewerb zur L\u00f6sung des Vertex Cover-Problems 24 Teams teilgenommen. Es ist erw\u00e4hnenswert, dass der Wettbewerb nicht nur einige Stunden oder sogar eine Woche dauert, sondern mehrere Monate. Die Teams haben die M\u00f6glichkeit, Fachliteratur zu studieren, ihre eigene originelle Idee zu entwickeln und diese umzusetzen. Im Grunde genommen stellt dieser Wettbewerb eine Forschungsarbeit dar. Die Ideen der effektivsten L\u00f6sungen und die Preisverleihung der Gewinner finden gemeinsam mit der Konferenz IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) im Rahmen der gr\u00f6\u00dften j\u00e4hrlichen algorithmischen Versammlung in Europa ALGO<\/a><\/noindex>. Detailliertere Informationen zum Wettbewerb selbst finden Sie auf Website<\/a><\/noindex>, w\u00e4hrend die Ergebnisse der vergangenen Jahre liegen hier<\/a><\/noindex>.<\/p>\n

L\u00f6sungsansatz<\/h3>\n

Um das Problem der Knotenabdeckung zu l\u00f6sen, habe ich versucht, parametrisierte Algorithmen anzuwenden. Diese bestehen in der Regel aus zwei Teilen: Vereinfachungsregeln (die idealerweise zu einer Kernelisierung f\u00fchren) und Aufspaltungsregeln. Die Vereinfachungsregeln sind eine Vorverarbeitung des Eingangs in polynomieller Zeit. Das Ziel der Anwendung solcher Regeln besteht darin, das Problem auf eine \u00e4quivalente, kleinere Version zu reduzieren. Die Anwendung dieser Vereinfachungsregeln ist der arbeitsintensivste Teil des Algorithmus, und die Anwendung genau dieses Teils f\u00fchrt zu einer Gesamtlaufzeit \"Wie anstatt zu einfacher polynomieller Zeit. In unserem Fall basieren die Aufspaltungsregeln darauf, dass f\u00fcr jeden Knoten entweder dieser oder sein Nachbar gew\u00e4hlt werden muss.<\/p>\n

Das allgemeine Schema ist folgendes: Wir wenden die Vereinfachungsregeln an, w\u00e4hlen dann einen Knoten aus und machen zwei rekursive Aufrufe: im ersten nehmen wir ihn als Antwort, im anderen nehmen wir alle seine Nachbarn. Dies nennen wir das Aufspalten (Branching) \u00fcber diesen Knoten.<\/p>\n

In dieses Schema wird im n\u00e4chsten Absatz genau eine Erg\u00e4nzung aufgenommen.<\/p>\n

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

Lassen Sie uns besprechen, wie man einen Knoten w\u00e4hlt, \u00fcber den es zu einem Aufspalten kommt.
\nDie Hauptidee ist algorithmisch sehr gierig: Lassen Sie uns einen Knoten mit dem h\u00f6chsten Grad nehmen und genau \u00fcber ihn aufspalten. Warum scheint das besser zu sein? Weil wir im zweiten Zweig des rekursiven Aufrufs auf diese Weise sehr viele Knoten eliminieren. Man kann erwarten, dass ein kleiner Graph \u00fcbrig bleibt, und auf diesem werden wir schnell arbeiten.<\/p>\n

Dieser Ansatz mit den bereits besprochenen einfachen Kerntechniken zeigt sich als ziemlich effektiv und l\u00f6st einige Tests mit mehreren Tausend Knoten. Aber zum Beispiel funktioniert er schlecht bei kubischen Graphen (d.h. Graphen, bei denen der Grad jedes Knotens drei betr\u00e4gt).
\nEs gibt noch eine Idee, die auf einem ziemlich einfachen Gedanken basiert: Wenn der Graph nicht zusammenh\u00e4ngend ist, kann das Problem auf seinen Zusammenhangskomponenten unabh\u00e4ngig gel\u00f6st werden, indem die Antworten am Ende zusammengef\u00fchrt werden. Das 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 Zeiten zur Berechnung der Antworten der Komponenten gearbeitet, nun arbeiten wir mit der Summe. Und um das Branching zu beschleunigen, muss man einen zusammenh\u00e4ngenden Graph in einen nicht zusammenh\u00e4ngenden umwandeln.<\/p>\n

Wie macht man das? Wenn im Graphen ein Schnittpunkt vorhanden ist, muss man genau an diesem schneiden. Ein Schnittpunkt ist ein Knoten, dessen Entfernung die Zusammenh\u00e4ngigkeit des Graphen beeintr\u00e4chtigt. Alle Schnittpunkte im Graphen kann man mit einem klassischen Algorithmus in linearer Zeit finden. Dieser Ansatz beschleunigt das Schneiden erheblich.
\n\"Wie
\nWenn einer der hervorgehobenen Knoten entfernt wird, zerf\u00e4llt der Graph in Zusammenh\u00e4ngende Komponenten.<\/p>\n

Das werden wir machen, aber ich m\u00f6chte mehr. Zum Beispiel kleine Knoten-Schnitte im Graphen suchen und darauf das Schneiden durchf\u00fchren. Der effektivste mir bekannte Weg, einen minimalen globalen Knoten-Schnitt zu finden, ist die Verwendung des Gomory-Hu-Baums, der in kubischer Zeit aufgebaut wird. Im PACE Challenge ist die typische Gr\u00f6\u00dfe des Graphen mehrere tausend Knoten. In diesem Fall m\u00fcssten wir in jedem Knoten des Rekursionsbaumes Milliarden von Operationen durchf\u00fchren. Daher ist es einfach unm\u00f6glich, die Aufgabe in der vorgegebenen Zeit zu l\u00f6sen.<\/p>\n

Versuchen wir, die L\u00f6sung zu optimieren. Den minimalen Knoten-Schnitt zwischen einem Paar von Knoten kann man mit jedem Algorithmus finden, der den maximalen Fluss berechnet. Man kann ein Netzwerk darauf ansetzen den Dinic-Algorithmus<\/a><\/noindex>, der in der Praxis sehr schnell funktioniert. Ich vermute, dass man theoretisch eine Absch\u00e4tzung f\u00fcr die Laufzeit beweisen kann \"Wie, was bereits sehr akzeptabel ist.<\/p>\n

Ich habe mehrmals versucht, Schnitte zwischen Paaren zuf\u00e4lliger Knoten zu suchen und den ausgewogensten zu nehmen. Leider hat das in den offenen Tests der PACE Challenge schlechte Ergebnisse geliefert. Ich habe ihn mit einem Algorithmus verglichen, der auf den Knoten mit der h\u00f6chsten Gradzahl basiert, und sie mit einer Begrenzung f\u00fcr die Tiefe gestartet. Nach dem Algorithmus, der versucht hat, den Schnitt auf diese Weise zu finden, lagen gr\u00f6\u00dfere Graphen zur\u00fcck. Das h\u00e4ngt damit zusammen, dass die Schnitte sehr unausgewogen waren: Wenn ich 5-10 Knoten entfernte, konnte ich nur 15-20 abtrennen.<\/p>\n

Es ist anzumerken, dass in Artikeln \u00fcber theoretisch schnellste Algorithmen deutlich fortgeschrittenere Techniken zur Auswahl von Knoten f\u00fcr das Schneiden verwendet werden. Diese Techniken haben jedoch eine sehr komplexe Umsetzung und oft schlechte Laufzeit- und Speichersch\u00e4tzungen. Es ist mir nicht gelungen, davon praktikable zu extrahieren.<\/p>\n

Anwendung der Vereinfachungsregeln<\/h3>\n

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

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

    Mit den ersten beiden ist alles klar, aber mit dem dritten gibt es einen Trick. Wenn wir in der lustigen Aufgabe \u00fcber die Bar eine obere Grenze f\u00fcr k<\/i>, gegeben haben, m\u00fcssen wir in der PACE Challenge einfach eine minimal gro\u00dfe Deckung finden. Das ist eine typische Umwandlung von Suchproblemen in Entscheidungsprobleme; oft macht man zwischen den beiden Arten von Aufgaben keinen Unterschied. In der Praxis, wenn wir einen Solver f\u00fcr das Deckungsproblem schreiben, kann es einen Unterschied geben. Zum Beispiel, wie im dritten Punkt.<\/p>\n

    Aus der Sicht der Implementierung kann man auf zwei Arten vorgehen. Der erste Ansatz wird als Iterative Deepening bezeichnet. Er besteht darin, dass wir mit einer vern\u00fcnftigen unteren Grenze f\u00fcr die Antwort beginnen und dann unseren Algorithmus ausf\u00fchren, wobei wir diese Grenze als obere Grenze f\u00fcr die Antwort verwenden, ohne die Rekursion tiefer abzusteigen als diese Grenze. Wenn wir eine Antwort gefunden haben, ist sie garantiert optimal, andernfalls 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 diesen Parameter bei der Auffindung zu \u00e4ndern k<\/i> um \u00fcberfl\u00fcssige Zweige in der Suche st\u00e4rker abzuschneiden.<\/p>\n

    Nach einigen n\u00e4chtlichen Experimenten habe ich mich f\u00fcr eine Kombination dieser beiden Methoden entschieden: Zun\u00e4chst starte ich meinen Algorithmus mit einer Begrenzung der Suchtiefe (indem ich sie so w\u00e4hle, dass sie im Vergleich zur Hauptl\u00f6sung vernachl\u00e4ssigbare Zeit in Anspruch nimmt) und verwende die beste gefundene L\u00f6sung als obere Begrenzung f\u00fcr die Antwort \u2014 also genau f\u00fcr die k<\/i>.<\/p>\n

    Knoten der St\u00e4rke 2<\/h3>\n

    Mit Knoten der St\u00e4rken 0 und 1 sind wir durch. Es stellt sich heraus, dass das auch mit Knoten der St\u00e4rke 2 m\u00f6glich ist, aber daf\u00fcr sind komplexere Operationen am Graphen erforderlich.<\/p>\n

    Um das zu erkl\u00e4ren, m\u00fcssen wir die Knoten irgendwie kennzeichnen. Nennen wir einen Knoten der St\u00e4rke 2 einen Knoten v<\/i>, und seine Nachbarn \u2014 Knoten x<\/i> und y<\/i>. Dann haben wir zwei F\u00e4lle.<\/p>\n

      \n
    1. Wenn x<\/i> und y<\/i> \u2014 Nachbarn. Dann kann man als Antwort nehmen x<\/i> und y<\/i>, und v<\/i> entfernen. Und in der Tat, aus diesem Dreieck m\u00fcssen mindestens zwei Knoten in die Antwort aufgenommen werden, und wir verlieren definitiv nicht, wenn wir nehmen x<\/i> und y<\/i>: Sie haben wahrscheinlich noch Nachbarn, w\u00e4hrend bei v<\/i> diese nicht vorhanden sind.<\/li>\n
    2. Wenn x<\/i> und y<\/i> \u2014 keine Nachbarn. Dann wird behauptet, dass alle drei Eckpunkte zu einem zusammengef\u00fcgt werden k\u00f6nnen. Die Idee ist, dass in diesem Fall eine optimale Antwort vorliegt, in der wir entweder v<\/i>, oder beide Eckpunkte x<\/i> und y<\/i>nehmen m\u00fcssen. Im ersten Fall m\u00fcssen wir alle Nachbarn in die Antwort aufnehmen x<\/i> und y<\/i>, im zweiten Fall ist das nicht unbedingt erforderlich. Dies entspricht genau den F\u00e4llen, in denen wir den zusammengef\u00fcgten Eckpunkt nicht in die Antwort aufnehmen und wenn wir es tun. Es bleibt nur zu bemerken, dass in beiden F\u00e4llen die Antwort durch diese Operation um eins verringert wird.<\/li>\n<\/ol>\n

      \"Wie<\/p>\n

      Es ist erw\u00e4hnenswert, dass es ziemlich schwierig ist, einen solchen Ansatz in ehrlicher linearer Zeit sorgf\u00e4ltig zu implementieren. Das Zusammenf\u00fcgen von Eckpunkten ist eine komplexe Operation, es m\u00fcssen Nachbarlisten kopiert werden. Wenn dies nicht sorgf\u00e4ltig geschieht, kann es zu asymptotisch suboptimalen Laufzeiten kommen (zum Beispiel, wenn nach jeder Zusammenf\u00fcgung viele Kanten kopiert werden). Ich konzentrierte mich auf die Suche nach vollst\u00e4ndigen Wegen aus Eckpunkten der Ordnung 2 und die Analyse vieler spezieller F\u00e4lle, wie z. B. Zyklen aus solchen Eckpunkten oder aus allen solchen Eckpunkten au\u00dfer einem.<\/p>\n

      Dar\u00fcber hinaus muss dieser Vorgang umkehrbar sein, damit wir w\u00e4hrend der R\u00fcckkehr aus der Rekursion den Graphen in seinen urspr\u00fcnglichen Zustand wiederherstellen k\u00f6nnen. Um dies zu gew\u00e4hrleisten, habe ich die Kantenlisten der zusammengef\u00fcgten Eckpunkte nicht gel\u00f6scht; danach wusste ich einfach, wohin die Kanten gerichtet werden m\u00fcssen. Eine solche Implementierung von Grafen erfordert ebenfalls Sorgfalt, bietet jedoch ehrliche lineare Zeit. Und f\u00fcr Grafen mit mehreren Zehntausend Kanten passt es gut in den Cache des Prozessors, was Geschwindigkeitsvorteile bietet.<\/p>\n

      Lineares Kern<\/h3>\n

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

      Zun\u00e4chst erinnern wir uns daran, dass in bipartiten Grafen das minimale Vertex-Deckung in \"Wiegesucht werden kann. Dazu muss der Algorithmus Hopcroft-Karp<\/a><\/noindex> verwendet werden, um dort das maximale Paarung zu finden, und dann das Theorem K\u00f6nigs-Egervari<\/a><\/noindex>.<\/p>\n

      anzuwenden. Die Idee des linearen Kerns ist folgende: Zun\u00e4chst teilen wir den Graphen auf, d.h. anstelle jedes Eckpunkts v<\/i> f\u00fchren wir zwei Eckpunkte ein, \"Wie und \"Wieund anstelle jeder Kante u \u2014 v<\/i> f\u00fchren wir zwei Kanten ein. \"Wie und \"WieDer erhaltene Graph wird bipartit sein. Wir werden darin das minimale Knotencover finden. Einige Knoten des urspr\u00fcnglichen Graphen werden dort zweimal erscheinen, einige nur einmal und einige gar nicht. Der Satz von Nemhauser-Trotter besagt, dass wir in diesem Fall Knoten, die kein einziges Mal vorkommen, entfernen k\u00f6nnen und die diejenigen als Antwort nehmen, die zweimal vorkommen. Dar\u00fcber hinaus sagt er, dass von den verbleibenden Knoten (denjenigen, die einmal vorkommen) mindestens die H\u00e4lfte als Antwort genommen werden sollte.<\/p>\n

      Gerade haben wir gelernt, im Graphen nicht mehr als 2k<\/i> Knoten zu belassen. Es stimmt, wenn in der \u00dcberschussantwort mindestens die H\u00e4lfte aller Knoten vorhanden ist, dann sind es insgesamt nicht mehr als 2k<\/i>.<\/p>\n

      Hier ist mir ein kleiner Schritt vorw\u00e4rts gelungen. Es ist klar, dass der auf diese Weise konstruierte Kern davon abh\u00e4ngt, welches minimale Knotencover im bipartiten Graphen wir gew\u00e4hlt haben. Ich m\u00f6chte eines w\u00e4hlen, bei dem die Anzahl der verbleibenden Knoten minimal ist. Fr\u00fcher konnte man das nur in einer Zeit von \"Wie. Ich habe jedoch eine Implementierung dieses Algorithmus in einer Zeit von \"Wieerfunden, sodass dieser Kern in 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 in Tests mit mehreren Hundert Knoten und einigen Tausend Kanten gut funktioniert. Bei solchen Tests kann man ganz gut erwarten, dass die L\u00f6sung innerhalb einer halben Stunde gefunden wird. Die Wahrscheinlichkeit, dass die Antwort in akzeptabler Zeit gefunden wird, steigt grunds\u00e4tzlich, wenn der Graph gen\u00fcgend viele Knoten hohen Grades hat, zum Beispiel Grad 10 und h\u00f6her.<\/p>\n

      Um am Wettbewerb teilzunehmen, mussten die L\u00f6sungen bis zu optil.io<\/a><\/noindex>eingereicht werden. Anhand der dort vorgestellten Tabelle<\/a><\/noindex>nimmt meine L\u00f6sung in den offenen Tests den dritten Platz von zwanzig mit gro\u00dfem Abstand zum zweiten ein. Um ganz ehrlich zu sein, ist es nicht ganz klar, wie die L\u00f6sungen im Wettbewerb selbst bewertet werden: Zum Beispiel besteht meine L\u00f6sung aus weniger Tests als die L\u00f6sung auf dem vierten Platz, aber sie funktioniert bei denen, 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-news"],"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\udd47Wie man NP-schwierige Probleme mit parametrisierten Algorithmen l\u00f6st | ProHoster","description":"Die wissenschaftliche Forschungsarbeit ist wohl der interessanteste Teil unserer Ausbildung. Die Idee ist, bereits an der Universit\u00e4t zu versuchen, sich in dem gew\u00e4hlten Bereich zu bew\u00e4hren.","canonical_url":"https:\/\/prohoster.info\/de\/blog\/news\/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.","og:url":"https:\/\/prohoster.info\/de\/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\/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}]}}