Die Forschungsarbeit ist vielleicht der interessanteste Teil unserer Ausbildung. Die Idee ist, sich bereits während des Studiums in die von Ihnen gewählte Richtung zu versuchen. Beispielsweise gehen Studierende aus den Bereichen Software Engineering und Maschinelles Lernen häufig zur Forschung in Unternehmen (hauptsächlich JetBrains oder Yandex, aber nicht nur).
In diesem Beitrag werde ich über mein Projekt in der Informatik sprechen. Im Rahmen meiner Arbeit habe ich Ansätze zur Lösung eines der bekanntesten NP-schweren Probleme untersucht und in die Praxis umgesetzt: Scheitelpunktabdeckungsproblem.
Heutzutage entwickelt sich sehr schnell ein interessanter Ansatz für NP-schwere Probleme – parametrisierte Algorithmen. Ich werde versuchen, Sie auf den neuesten Stand zu bringen, Ihnen einige einfache parametrisierte Algorithmen vorzustellen und eine leistungsstarke Methode zu beschreiben, die mir sehr geholfen hat. Meine Ergebnisse habe ich beim PACE Challenge-Wettbewerb präsentiert: Nach den Ergebnissen offener Tests belegt meine Lösung den dritten Platz und die endgültigen Ergebnisse werden am 1. Juli bekannt gegeben.
Über mich
Mein Name ist Vasily Alferov, ich beende jetzt mein drittes Jahr an der National Research University Higher School of Economics – St. Petersburg. Ich interessiere mich seit meiner Schulzeit für Algorithmen, als ich an der Moskauer Schule Nr. 179 studierte und erfolgreich an Informatikolympiaden teilnahm.
Eine begrenzte Anzahl von Spezialisten für parametrisierte Algorithmen betritt die Bar ...
Beispiel aus dem Buch
Stellen Sie sich vor, Sie wären Sicherheitsbeamter in einer Bar in einer Kleinstadt. Jeden Freitag kommt die halbe Stadt zum Entspannen in Ihre Bar, was Ihnen viel Ärger bereitet: Sie müssen lautstarke Kunden aus der Bar werfen, um Schlägereien zu verhindern. Irgendwann haben Sie die Nase voll und beschließen, vorbeugende Maßnahmen zu ergreifen.
Da Ihre Stadt klein ist, wissen Sie genau, welche Gästepaare sich wahrscheinlich streiten, wenn sie zusammen in einer Bar landen. Haben Sie eine Liste von n Leute, die heute Abend in die Bar kommen werden. Sie beschließen, einige Stadtbewohner von der Bar fernzuhalten, ohne dass jemand in Streit gerät. Gleichzeitig möchten Ihre Vorgesetzten keine Gewinneinbußen hinnehmen und werden unzufrieden sein, wenn Sie nicht mehr zulassen k Menschen.
Leider handelt es sich bei dem vorliegenden Problem um ein klassisches NP-schweres Problem. Du kennst sie vielleicht als oder als Scheitelpunktüberdeckungsproblem. Für solche Probleme gibt es im Allgemeinen keine Algorithmen, die in akzeptabler Zeit funktionieren. Genauer gesagt besagt die unbewiesene und ziemlich starke Hypothese ETH (Exponential Time Hypothesis), dass dieses Problem nicht rechtzeitig gelöst werden kann , das heißt, Sie können sich nichts nennenswert Besseres vorstellen als eine vollständige Suche. Nehmen wir zum Beispiel an, dass jemand in Ihre Bar kommt n = 1000 Menschlich. Dann wird die vollständige Suche durchgeführt Optionen, die es ungefähr gibt - verrückte Menge. Glücklicherweise hat Ihnen Ihr Management ein Limit gesetzt k = 10Daher ist die Anzahl der Kombinationen, über die Sie iterieren müssen, viel kleiner: Die Anzahl der Teilmengen von zehn Elementen beträgt . Das ist zwar besser, wird aber selbst auf einem leistungsstarken Cluster immer noch nicht an einem Tag gezählt.
Um die Möglichkeit eines Kampfes in dieser Konstellation angespannter Beziehungen zwischen den Besuchern der Bar auszuschließen, müssen Sie Bob, Daniel und Fedor draußen halten. Es gibt keine Lösung, bei der nur zwei zurückbleiben.
Bedeutet das, dass es an der Zeit ist, nachzugeben und alle hereinzulassen? Betrachten wir andere Optionen. Nun, zum Beispiel kann man nicht nur diejenigen hereinlassen, die wahrscheinlich mit einer sehr großen Anzahl von Menschen kämpfen. Wenn jemand wenigstens mit kämpfen kann k+1 Wenn du noch eine andere Person hast, dann darfst du sie auf keinen Fall reinlassen – sonst musst du alle draußen halten k+1 Stadtbewohner, mit denen er kämpfen kann, was die Führung definitiv verärgern wird.
Mögen Sie nach diesem Prinzip jeden rauswerfen, den Sie konnten. Dann können alle anderen mit nicht mehr als kämpfen k Menschen. Wirf sie raus k Mann, du kannst nichts mehr verhindern als Konflikte. Das heißt, wenn es mehr als gibt Wenn eine Person in mindestens einen Konflikt verwickelt ist, kann man sicherlich nicht alle verhindern. Da Sie natürlich auf jeden Fall völlig konfliktfreie Personen aufnehmen, müssen Sie alle Teilmengen der Größe zehn von zweihundert Personen durchgehen. Es gibt ungefähr , und diese Anzahl von Operationen kann bereits auf dem Cluster aussortiert werden.
Wenn Sie problemlos Personen aufnehmen können, die überhaupt keinen Konflikt haben, was ist dann mit denen, die nur an einem Konflikt beteiligt sind? Tatsächlich können sie auch hereingelassen werden, indem sie ihrem Gegner die Tür verschließen. In der Tat, wenn Alice nur mit Bob im Konflikt steht, werden wir nicht verlieren, wenn wir Alice aus den beiden herauslassen: Bob mag andere Konflikte haben, aber Alice hat sie sicherlich nicht. Außerdem macht es für uns keinen Sinn, uns beide nicht hereinzulassen. Nach solchen Operationen bleibt nichts mehr übrig Gäste mit ungeklärtem Schicksal: Wir haben nur Konflikte, an denen jeweils zwei Beteiligten beteiligt sind und an denen jeweils mindestens zwei beteiligt sind. Es bleibt also nur noch das Sortieren Optionen, die problemlos als halber Tag auf einem Laptop in Betracht gezogen werden können.
Tatsächlich können Sie mit einfachen Überlegungen sogar noch attraktivere Konditionen erzielen. Beachten Sie, dass wir auf jeden Fall alle Streitigkeiten beilegen müssen, das heißt, aus jedem Konfliktpaar müssen wir mindestens eine Person auswählen, die wir nicht hereinlassen. Betrachten wir den folgenden Algorithmus: Nehmen wir einen beliebigen Konflikt, aus dem wir einen Teilnehmer entfernen und rekursiv mit dem Rest beginnen, dann entfernen wir den anderen und beginnen ebenfalls rekursiv. Da wir bei jedem Schritt jemanden rauswerfen, ist der Rekursionsbaum eines solchen Algorithmus ein binärer Tiefenbaum k, also funktioniert der Algorithmus insgesamt Wo n ist die Anzahl der Eckpunkte und m - Anzahl der Rippen. In unserem Beispiel sind es etwa zehn Millionen, die sich nicht nur auf einem Laptop, sondern sogar auf einem Mobiltelefon in Sekundenbruchteilen berechnen lassen.
Das obige Beispiel ist ein Beispiel parametrisierter Algorithmus. Parametrisierte Algorithmen sind Algorithmen, die zeitlich ablaufen f(k) Poly(n)Wo p - Polynom, f ist eine beliebige berechenbare Funktion und k - ein Parameter, der möglicherweise viel kleiner ist als die Größe des Problems.
Alle Überlegungen vor diesem Algorithmus geben ein Beispiel Kernelisierung ist eine der allgemeinen Techniken zur Erstellung parametrisierter Algorithmen. Kernelisierung ist die Reduzierung der Problemgröße auf einen durch eine Funktion eines Parameters begrenzten Wert. Das resultierende Problem wird oft als Kernel bezeichnet. Durch einfache Überlegungen zu den Graden der Scheitelpunkte haben wir einen quadratischen Kernel für das Scheitelpunktüberdeckungsproblem erhalten, parametrisiert durch die Größe der Antwort. Es gibt andere Optionen, die für diese Aufgabe ausgewählt werden können (z. B. Vertex Cover Above LP), aber diese Option werden wir besprechen.
Tempo-Herausforderung
Wettbewerb (The Parametrized Algorithms and Computational Experiments Challenge) wurde 2015 ins Leben gerufen, um eine Verbindung zwischen parametrisierten Algorithmen und Ansätzen herzustellen, die in der Praxis zur Lösung rechnerischer Probleme eingesetzt werden. Die ersten drei Wettbewerbe waren der Ermittlung der Baumbreite eines Diagramms gewidmet (), auf der Suche nach einem Steiner-Baum () und Suche nach einer Menge von Eckpunkten, die Kreise schneidet (). Eines der Probleme, an denen Sie sich in diesem Jahr versuchen konnten, war das oben beschriebene Scheitelpunktabdeckungsproblem.
Der Wettbewerb erfreut sich von Jahr zu Jahr größerer Beliebtheit. Glaubt man den vorläufigen Daten, nahmen in diesem Jahr 24 Teams an dem Wettbewerb teil, bei dem es allein um die Lösung des Scheitelpunktabdeckungsproblems ging. Es ist erwähnenswert, dass der Wettbewerb nicht mehrere Stunden oder gar eine Woche, sondern mehrere Monate dauert. Die Teams haben die Möglichkeit, die Literatur zu studieren, eine eigene Idee zu entwickeln und zu versuchen, diese umzusetzen. Im Wesentlichen handelt es sich bei diesem Wettbewerb um ein Forschungsprojekt. Im Rahmen der Konferenz werden Ideen für die effektivsten Lösungen vorgestellt und die Gewinner ausgezeichnet (International Symposium on Parametrized and Exact Computation) im Rahmen des größten jährlichen Algorithmentreffens in Europa . Nähere Informationen zum Wettbewerb selbst finden Sie unter , und die Ergebnisse der Vorjahre lügen .
Lösungsschema
Um das Scheitelpunktabdeckungsproblem zu lösen, habe ich versucht, parametrisierte Algorithmen zu verwenden. Sie bestehen typischerweise aus zwei Teilen: Vereinfachungsregeln (die idealerweise zur Kernelisierung führen) und Aufteilungsregeln. Vereinfachungsregeln sind eine Vorverarbeitung der Eingabe in polynomieller Zeit. Der Zweck der Anwendung solcher Regeln besteht darin, das Problem auf ein äquivalentes kleineres Problem zu reduzieren. Vereinfachungsregeln sind der teuerste Teil des Algorithmus, und die Anwendung dieses Teils führt zur Gesamtlaufzeit statt einfacher Polynomzeit. In unserem Fall basieren die Aufteilungsregeln auf der Tatsache, dass Sie für jeden Scheitelpunkt entweder diesen oder seinen Nachbarn als Antwort nehmen müssen.
Das allgemeine Schema ist folgendes: Wir wenden die Vereinfachungsregeln an, wählen dann einen Scheitelpunkt aus und führen zwei rekursive Aufrufe durch: Im ersten nehmen wir ihn als Antwort und im anderen nehmen wir alle seine Nachbarn. Dies nennen wir Aufteilung (Verzweigung) entlang dieses Scheitelpunkts.
Genau eine Ergänzung zu diesem Schema wird im nächsten Absatz vorgenommen.
Ideen für Splitting-(Brunch-)Regeln
Lassen Sie uns besprechen, wie Sie einen Scheitelpunkt auswählen, entlang dem die Aufteilung erfolgen soll.
Die Grundidee ist im algorithmischen Sinne sehr gierig: Nehmen wir einen Scheitelpunkt mit maximalem Grad und teilen wir ihn entlang. Warum scheint es besser zu sein? Denn im zweiten Zweig des rekursiven Aufrufs werden wir auf diese Weise viele Vertices entfernen. Sie können mit einer kleinen verbleibenden Grafik rechnen und wir können schnell daran arbeiten.
Dieser Ansatz mit den bereits besprochenen einfachen Kernelisierungstechniken bewährt sich gut und löst einige Tests mit einer Größe von mehreren tausend Scheitelpunkten. Aber es funktioniert beispielsweise nicht gut für kubische Graphen (d. h. Graphen, deren Grad an jedem Scheitelpunkt drei beträgt).
Es gibt noch eine andere Idee, die auf einer ziemlich einfachen Idee basiert: Wenn der Graph nicht zusammenhängend ist, kann das Problem seiner verbundenen Komponenten unabhängig gelöst werden, indem die Antworten am Ende kombiniert werden. Dies ist übrigens eine kleine versprochene Änderung des Schemas, die die Lösung deutlich beschleunigen wird: Bisher haben wir in diesem Fall für die Berechnung der Reaktionen der Komponenten nach dem Produkt der Zeiten gearbeitet, jetzt arbeiten wir nach die Summe. Und um die Verzweigung zu beschleunigen, müssen Sie einen verbundenen Graphen in einen nicht verbundenen Graphen umwandeln.
Wie kann man das machen? Wenn es in der Grafik einen Artikulationspunkt gibt, müssen Sie darum kämpfen. Ein Artikulationspunkt ist ein Scheitelpunkt, bei dessen Entfernung der Graph seine Konnektivität verliert. Alle Knotenpunkte in einem Diagramm können mit einem klassischen Algorithmus in linearer Zeit gefunden werden. Dieser Ansatz beschleunigt die Verzweigung erheblich.
Wenn einer der ausgewählten Scheitelpunkte entfernt wird, wird das Diagramm in verbundene Komponenten aufgeteilt.
Wir werden das tun, aber wir wollen mehr. Suchen Sie beispielsweise nach kleinen Scheitelpunktschnitten im Diagramm und teilen Sie es entlang der Scheitelpunkte auf. Der effizienteste Weg, den ich kenne, um den minimalen globalen Scheitelpunktschnitt zu ermitteln, ist die Verwendung eines Gomori-Hu-Baums, der in Kubikzeit erstellt wird. Bei der PACE Challenge beträgt die typische Diagrammgröße mehrere tausend Eckpunkte. In dieser Situation müssen an jedem Scheitelpunkt des Rekursionsbaums Milliarden von Operationen ausgeführt werden. Es stellt sich heraus, dass es einfach unmöglich ist, das Problem in der vorgegebenen Zeit zu lösen.
Versuchen wir, die Lösung zu optimieren. Der minimale Scheitelpunktschnitt zwischen einem Scheitelpunktpaar kann von jedem Algorithmus ermittelt werden, der einen maximalen Fluss konstruiert. Sie können es in ein solches Netzwerk einbinden , in der Praxis funktioniert es sehr schnell. Ich habe den Verdacht, dass es theoretisch möglich ist, eine Schätzung für die Betriebsdauer nachzuweisen , was schon durchaus akzeptabel ist.
Ich habe mehrmals versucht, nach Schnitten zwischen Paaren zufälliger Scheitelpunkte zu suchen und den ausgewogensten zu wählen. Leider führte dies bei offenen PACE-Challenge-Tests zu schlechten Ergebnissen. Ich habe es mit einem Algorithmus verglichen, der Scheitelpunkte mit maximalem Grad aufteilt und sie mit einer Begrenzung der Abstiegstiefe ausführt. Ein Algorithmus, der auf diese Weise einen Schnitt zu finden versuchte, hinterließ größere Diagramme. Dies liegt daran, dass sich die Schnitte als sehr unausgewogen herausstellten: Nach dem Entfernen von 5–10 Scheitelpunkten konnten nur 15–20 abgespalten werden.
Es ist erwähnenswert, dass Artikel über die theoretisch schnellsten Algorithmen viel fortgeschrittenere Techniken zur Auswahl von Scheitelpunkten für die Aufteilung verwenden. Solche Techniken sind sehr komplex in der Implementierung und weisen häufig eine schlechte Leistung hinsichtlich Zeit und Speicher auf. Es ist mir nicht gelungen, diejenigen zu identifizieren, die für die Praxis durchaus akzeptabel sind.
So wenden Sie Vereinfachungsregeln an
Wir haben bereits Ideen zur Kernelisierung. Lass mich dich errinnern:
- Wenn ein isolierter Scheitelpunkt vorhanden ist, löschen Sie ihn.
- Wenn es einen Scheitelpunkt vom Grad 1 gibt, entfernen Sie ihn und nehmen Sie als Antwort seinen Nachbarn.
- Wenn es zumindest einen Scheitelpunkt gibt k+1, Nimm es zurück.
Bei den ersten beiden ist alles klar, beim dritten gibt es einen Trick. Bei einem komischen Problem über eine Bar wurde uns eine Obergrenze von gegeben k, dann müssen Sie in der PACE Challenge nur noch eine Scheitelpunktabdeckung mit der Mindestgröße finden. Dies ist eine typische Umwandlung von Suchproblemen in Entscheidungsprobleme; oft gibt es keinen Unterschied zwischen den beiden Problemtypen. Wenn wir in der Praxis einen Löser für das Scheitelpunktüberdeckungsproblem schreiben, kann es einen Unterschied geben. Zum Beispiel wie im dritten Punkt.
Aus Umsetzungssicht gibt es zwei Vorgehensweisen. Der erste Ansatz heißt Iterative Deepening. Es ist wie folgt: Wir können mit einer vernünftigen Einschränkung von unten für die Antwort beginnen und dann unseren Algorithmus unter Verwendung dieser Einschränkung als Einschränkung für die Antwort von oben ausführen, ohne in der Rekursion tiefer als diese Einschränkung zu gehen. Wenn wir eine Antwort gefunden haben, ist diese garantiert optimal, andernfalls können wir diese Grenze um eins erhöhen und von vorne beginnen.
Ein anderer Ansatz besteht darin, eine aktuelle optimale Antwort zu speichern und nach einer kleineren Antwort zu suchen und diesen Parameter zu ändern, wenn er gefunden wird k zum besseren Abschneiden unnötiger Zweige bei der Suche.
Nachdem ich mehrere nächtliche Experimente durchgeführt hatte, entschied ich mich für eine Kombination dieser beiden Methoden: Zuerst führe ich meinen Algorithmus mit einer Art Begrenzung der Suchtiefe aus (ich wähle sie so aus, dass sie im Vergleich zur Hauptlösung vernachlässigbar lange dauert) und verwende die beste gefundene Lösung als Obergrenze der Antwort - also des Gleichen k.
Eckpunkte vom Grad 2
Wir haben uns mit Eckpunkten vom Grad 0 und 1 befasst. Es stellt sich heraus, dass dies mit Scheitelpunkten vom Grad 2 möglich ist, dies erfordert jedoch komplexere Operationen aus dem Diagramm.
Um dies zu erklären, müssen wir die Eckpunkte irgendwie bezeichnen. Nennen wir einen Scheitelpunkt vom Grad 2 einen Scheitelpunkt vund seine Nachbarn - Eckpunkte x и y. Als nächstes werden wir zwei Fälle haben.
- Wenn x и y - Nachbarn. Dann können Sie antworten x и yUnd v löschen. Tatsächlich müssen von diesem Dreieck im Gegenzug mindestens zwei Eckpunkte genommen werden, und wir werden definitiv nicht verlieren, wenn wir sie nehmen x и y: Sie haben wahrscheinlich andere Nachbarn, und v Sie sind nicht da.
- Wenn x и y - keine Nachbarn. Dann heißt es, dass alle drei Eckpunkte zu einem zusammengeklebt werden können. Die Idee ist, dass es in diesem Fall eine optimale Antwort gibt, bei der wir entweder nehmen voder beide Eckpunkte x и y. Darüber hinaus müssen wir im ersten Fall alle Nachbarn als Reaktion darauf berücksichtigen x и y, aber im zweiten ist es nicht notwendig. Dies entspricht genau den Fällen, in denen wir den geklebten Scheitelpunkt nicht als Antwort nehmen, und in denen wir dies tun. Es bleibt nur zu beachten, dass in beiden Fällen die Reaktion einer solchen Operation um eins abnimmt.
Es ist erwähnenswert, dass es ziemlich schwierig ist, diesen Ansatz in angemessener linearer Zeit genau umzusetzen. Das Kleben von Scheitelpunkten ist ein komplexer Vorgang; Sie müssen Listen von Nachbarn kopieren. Wenn dies unvorsichtig gemacht wird, kann es zu einer asymptotisch suboptimalen Laufzeit kommen (z. B. wenn Sie nach jedem Kleben viele Kanten kopieren). Ich entschied mich dafür, ganze Pfade von Scheitelpunkten 2. Grades zu finden und eine Reihe von Sonderfällen zu analysieren, etwa Zyklen von solchen Scheitelpunkten oder von allen solchen Scheitelpunkten bis auf einen.
Darüber hinaus ist es notwendig, dass dieser Vorgang reversibel ist, damit wir bei der Rückkehr von der Rekursion den Graphen in seine ursprüngliche Form zurückversetzen. Um dies sicherzustellen, habe ich die Kantenlisten der zusammengeführten Scheitelpunkte nicht gelöscht, und dann wusste ich nur, welche Kanten wohin gehen mussten. Diese Implementierung von Diagrammen erfordert ebenfalls Genauigkeit, bietet jedoch eine angemessene lineare Zeit. Und bei Diagrammen mit mehreren Zehntausend Kanten passt es in den Prozessor-Cache, was große Geschwindigkeitsvorteile bietet.
Linearer Kernel
Zum Schluss der interessanteste Teil des Kernels.
Denken Sie zunächst daran, dass in bipartiten Graphen die minimale Scheitelpunktabdeckung mithilfe von ermittelt werden kann . Dazu müssen Sie den Algorithmus verwenden um dort die maximale Übereinstimmung zu finden, und verwenden Sie dann den Satz .
Die Idee eines linearen Kernels ist folgende: Zuerst verzweigen wir den Graphen, also anstelle jedes Scheitelpunkts v Fügen wir zwei Spitzen hinzu и , und anstelle jeder Kante u - v Fügen wir zwei Rippen hinzu и . Der resultierende Graph ist zweiteilig. Finden wir darin die minimale Scheitelpunktabdeckung. Einige Eckpunkte des ursprünglichen Diagramms werden dort zweimal ankommen, andere nur einmal und andere nie. Das Nemhauser-Trotter-Theorem besagt, dass man in diesem Fall Eckpunkte entfernen kann, die nicht einmal getroffen haben, und diejenigen zurücknehmen kann, die zweimal getroffen haben. Darüber hinaus sagt sie, dass man von den verbleibenden Scheitelpunkten (denjenigen, die einmal treffen) mindestens die Hälfte als Antwort nehmen muss.
Wir haben gerade gelernt, nicht mehr als zu verlassen 2k Gipfel Wenn die Restantwort tatsächlich mindestens die Hälfte aller Scheitelpunkte beträgt, dann gibt es insgesamt nicht mehr Scheitelpunkte als 2k.
Hier konnte ich einen kleinen Schritt nach vorne machen. Es ist klar, dass der auf diese Weise konstruierte Kernel davon abhängt, welche Art von minimaler Scheitelpunktabdeckung wir im bipartiten Graphen angenommen haben. Ich würde gerne einen nehmen, damit die Anzahl der verbleibenden Scheitelpunkte minimal ist. Bisher gelang ihnen dies nur rechtzeitig . Ich habe damals eine Implementierung dieses Algorithmus entwickelt Daher kann dieser Kern in Diagrammen mit Hunderttausenden von Eckpunkten in jeder Verzweigungsstufe gesucht werden.
Erlebe die Kraft effektiver Ergebnisse
Die Praxis zeigt, dass meine Lösung bei Tests mit mehreren hundert Eckpunkten und mehreren tausend Kanten gut funktioniert. Bei solchen Tests kann man durchaus damit rechnen, dass in einer halben Stunde eine Lösung gefunden wird. Die Wahrscheinlichkeit, in akzeptabler Zeit eine Antwort zu finden, steigt grundsätzlich, wenn der Graph eine ausreichend große Anzahl von Eckpunkten mit hohem Grad aufweist, beispielsweise Grad 10 und höher.
Um am Wettbewerb teilzunehmen, mussten Lösungen an gesendet werden . Den dort präsentierten Informationen nach zu urteilen , meine Lösung liegt in offenen Tests auf Platz drei von zwanzig, mit großem Abstand zum zweiten. Um ganz ehrlich zu sein, ist es nicht ganz klar, wie Lösungen beim Wettbewerb selbst bewertet werden: Meine Lösung besteht beispielsweise weniger Tests als die Lösung auf dem vierten Platz, aber bei den bestandenen funktioniert sie schneller.
Die Ergebnisse der geschlossenen Tests werden am XNUMX. Juli bekannt gegeben.
Source: habr.com