Wie man NP-schwierige Probleme mit parametrisierten Algorithmen löst

Die wissenschaftliche Forschung ist wahrscheinlich der spannendste Teil unseres Studiums. Die Idee ist, sich bereits an der Universität in einem gewählten Bereich auszuprobieren. Zum Beispiel gehen Studenten der Fachrichtungen Software Engineering und Machine Learning oft zu Unternehmen für ihre Forschungsarbeiten (hauptsächlich JetBrains oder Yandex, aber nicht nur).

In diesem Beitrag werde ich über mein Projekt im Bereich der Computerwissenschaften berichten. Im Rahmen meiner Arbeit habe ich Ansätze zur Lösung eines der bekanntesten NP-schwierigen Probleme untersucht und praktisch umgesetzt: das Vertex-Cover-Problem.

Derzeit entwickelt sich ein interessanter Ansatz für NP-schwierige Probleme sehr schnell – parametrisierten Algorithmen. Ich werde versuchen, Ihnen einen Überblick 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äsentiert: Nach den offenen Tests belegt meine Lösung den dritten Platz, und die endgültigen Ergebnisse werden am 1. Juli bekannt gegeben.

Über mich

Mein Name ist Wasilij Alfjorow, ich bin gerade im dritten Jahr an der Nationalen Forschungshochschule für Volkswirtschaft – Sankt Petersburg. Seit meiner Schulzeit in der Moskauer 179. Schule interessieren mich Algorithmen, und ich habe erfolgreich an Informatikwettbewerben teilgenommen.

Eine bestimmte Anzahl von Spezialisten für parametrisierte Algorithmen betritt eine Bar…

Das Beispiel wurde aus dem Buch entnommen „Parametrisierte Algorithmen“

Stellen Sie sich vor, Sie sind der Barkeeper in einer kleinen Stadt. Jeden Freitagabend kommt die Hälfte der Stadt in Ihre Bar, um sich zu entspannen, was Ihnen einiges an Mühe bereitet: Sie müssen störende Gäste herauswerfen, um Schlägereien zu vermeiden. Schließlich wird Ihnen das lästig, und Sie beschließen, präventive Maßnahmen zu ergreifen.

Da Ihre Stadt klein ist, wissen Sie genau, welche Gäste mit hoher Wahrscheinlichkeit miteinander aneinandergeraten, wenn sie zusammen in die Bar kommen. Sie haben eine Liste von n Menschen, die heute Abend in die Bar kommen werden. Sie beschließen, einige Bürger nicht hereinzulassen, um sicherzustellen, dass sich niemand streitet. Gleichzeitig möchte Ihre Vorgesetzte keine Gewinne verlieren und wird unzufrieden sein, wenn Sie nicht mehr als k Personen in die Bar lassen.

Leider ist das Problem, vor dem Sie stehen, ein klassisches NP-vollständiges Problem. Vielleicht kennen Sie es als Vertex Cover, oder als das Problem des Punktüberdeckens. Für 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öst werden kann , was bedeutet, dass man nichts finden kann, was deutlich besser ist als eine vollständige Exhaustion. Stellen Sie sich vor, in Ihre Bar kommen gleich n = 1000 Personen. Dann würde die vollständige Exhaustion Varianten generieren, was ungefähr — unglaublich viel ist. Glücklicherweise hat Ihre Geschäftsführung Ihnen eine Begrenzung gesetzt auf k = 10, sodass die Anzahl der Kombinationen, die Sie durchgehen müssen, viel geringer ist: die Anzahl der Teilmengen von zehn Elementen ist . Das ist schon besser, aber trotzdem kann man nicht einmal an einem leistungsstarken Cluster alle Optionen innerhalb eines Tages durchrechnen.

Um das Risiko von Kämpfen durch die angespannte Beziehung zwischen den Barbesuchern ausschließen zu können, müssen Sie Bob, Daniel und Fyodor nicht einlassen. Lösungen, bei denen nur zwei ausgeschlossen sind, existieren nicht.

Bedeutet das, dass es an der Zeit ist, aufzugeben und alle hereinzulassen? Lassen Sie uns andere Optionen betrachten. Zum Beispiel könnte man nur die Personen nicht einlassen, die wahrscheinlich mit einer sehr großen Anzahl von Menschen kämpfen würden. Wenn jemand mit mindestens k + 1 anderen Personen kämpfen kann, dann darf er auf keinen Fall hereingelassen werden — andernfalls müssten Sie alle k + 1 Einwohner, mit denen er kämpfen könnte, nicht reinlassen, was das Management sicherlich verärgern würde.

Angenommen, Sie haben alle, die Sie konnten, nach diesem Prinzip ausgeschlossen. Dann könnten alle anderen nicht mehr mit k Menschen kämpfen. Wenn Sie daraus k Personen ausschließen, können Sie nicht mehr als Konflikte verhindern. Das heißt, wenn mehr als Personen an mindestens einem Konflikt beteiligt sind, können Sie deren alle sicher nicht verhindern. Da, ganz klar, Sie garantiert diejenigen ohne Konflikte hereinzulassen, müssen Sie alle Teilmengen der Größe zehn aus zweihundert Personen durchgehen. Es gibt ungefähr , und eine solche Anzahl an Operationen kann bereits in einem Cluster durchgearbeitet werden.

Wenn es möglich ist, völlig nicht konfliktträchtige Personen aufzunehmen, wie steht es dann mit denen, die nur an einem Konflikt beteiligt sind? Tatsächlich können auch sie hereingelassen werden, während wir die Tür vor ihrem Gegner schließen. Ist es nicht so, dass, wenn Alice nur mit Bob in Konflikt steht, wir nichts verlieren, wenn wir Alice von beiden hereinlassen? Bob könnte andere Konflikte haben, während Alice definitiv keine hat. Es wäre außerdem sinnlos, beide nicht hereinzulassen. Nach solchen Operationen bleibt nicht mehr als Gäste mit ungewisser Zukunft: Insgesamt haben wir Konflikte, an denen jeweils zwei Teilnehmer beteiligt sind und jeder mindestens an zwei teilnimmt. Das bedeutet, wir müssen insgesamt nur Varianten durchgehen, was durchaus an einem halben Tag auf einem Laptop machbar ist.

In der Tat können wir mit einfachen Überlegungen noch attraktivere Bedingungen erzielen. Es ist wichtig, dass wir alle Streitigkeiten lösen, das heißt, aus jedem strittigen Paar mindestens eine Person auszuwählen, 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ßen, ist der Rekursionsbaum eines solchen Algorithmus ein binärer Baum mit einer Tiefe k, sodass der Algorithmus insgesamt für , wobei n — die Anzahl der Knoten, und m — 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.

Das obige Beispiel ist ein Beispiel für einen parametrisierten Algorithmus. Parametrisierte Algorithmen sind Algorithmen, die in der Zeit f(k) poly(n), wobei p — ein Polynom, f — eine beliebige berechenbare Funktion, und k — ein Parameter, der möglicherweise viel kleiner als die Größe des Problems ist.

Alle Überlegungen bis zu diesem Algorithmus führen das Beispiel an der Kernelisierung — eine der gängigen Techniken zur Erstellung parametrischer Algorithmen. Kernisierung bezeichnet die Reduzierung der Aufgabengröße auf einen Wert, der durch eine Funktion vom Parameter begrenzt wird. Die resultierende Aufgabe wird oft als Kern bezeichnet. So haben wir durch einfache Überlegungen bezüglich der Gradanzahl ein quadratisches Kern für das Vertex Cover Problem erhalten, parametrisiert nach der Antwortgröße. Es gibt auch andere Parameter, die für dieses Problem ausgewählt werden können (zum Beispiel Vertex Cover Above LP), jedoch werden wir genau diesen Parameter diskutieren.

Pace Challenge

Wettbewerb PACE Challenge (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ätzen zur Lösung von Berechnungsproblemen herzustellen. Die ersten drei Wettbewerbe waren der Suche nach der Baumweite eines Graphen (Baumweite), der Suche nach einem Steinerbaum (Steinerbaum) und der Suche nach einer Menge von Knoten, die Zyklen durchtrennt (Feedback Vertex Set). In diesem Jahr war eine der Aufgaben, in denen man sein Können unter Beweis stellen konnte, das oben beschriebene Problem des Knotenüberdeckens.

Die Veranstaltung gewinnt Jahr für Jahr an Popularität. Laut vorläufigen Daten haben in diesem Jahr allein im Wettbewerb um das Vertex Cover Problem 24 Teams teilgenommen. Es ist erwähnenswert, dass das Event nicht nur wenige Stunden oder eine Woche dauert, sondern mehrere Monate. Die Teams haben die Möglichkeit, 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 (International Symposium on Parameterized and Exact Computation) im Rahmen des größten jährlichen Algorithmus-Meetings in Europa ALGO. Weitere Informationen zum Wettbewerb finden Sie auf Webseite, während die Ergebnisse der Vorjahre hier verfügbar sind. hier.

Lösungsdiagramm

Um das Problem der Spitzenabdeckung zu lösen, habe ich versucht, parametrisierte Algorithmen anzuwenden. Diese bestehen in der Regel aus zwei Teilen: Vereinfachungsregeln (die idealerweise zu einer Kernerstellung führen) und Aufspaltungsregeln. Die Vereinfachungsregeln sind eine Vorverarbeitung der Eingabe in polynomialer Zeit. Ziel dieser Regeln ist es, das Problem auf ein äquivalentes, kleineres Problem zu reduzieren. Die Vereinfachungsregeln stellen den kostenintensivsten Teil des Algorithmus dar, und die Anwendung genau dieses Teils führt zu einer Gesamtlaufzeit anstelle einfach polynomialer Zeit. In unserem Fall basieren die Aufspaltungsregeln darauf, dass für jede Spitze entweder sie selbst oder ihr Nachbar in Betracht gezogen werden muss.

Das allgemeine Schema sieht folgendermaßen aus: Wir wenden die Vereinfachungsregeln an, wählen dann eine Spitze aus und führen 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.

In diesen Rahmen wird genau eine Ergänzung im nächsten Absatz eingeführt.

Ideen für Aufspaltungsregeln (Branching)

Lassen Sie uns besprechen, wie wir den Knoten auswählen, an dem die Zerlegung erfolgen soll.
Die Grundidee ist algorithmisch sehr gierig: Lassen Sie uns den Knoten mit der maximalen Gradzahl wählen und genau an diesem Punkt die Zerlegung durchführen. Warum scheint das besser zu sein? Weil wir auf diese Weise im zweiten Zweig des rekursiven Aufrufs viele Knoten entfernen können. Man kann davon ausgehen, dass ein kleinerer Graph übrig bleibt, auf dem wir dann schnell arbeiten können.

Dieser Ansatz zusammen mit den bereits besprochenen einfachen Kerneltechniken zeigt sich recht vielversprechend und kann Tests mit mehreren tausend Knoten lösen. Allerdings funktioniert er bei kubischen Grafen (das heißt bei Graphen, deren Grad jeder Knoten drei beträgt) nicht gut.
Es gibt noch eine weitere Idee, die auf einem recht einfachen Gedanken basiert: Wenn der Graph nicht zusammenhängend ist, können die Aufgaben zur Verbindung seiner Komponenten unabhängig gelöst werden, indem die Antworten am Ende zusammengeführt werden. Dies ist übrigens die kleine, versprochene Modifikation im Schema, die die Lösung erheblich beschleunigen wird: Früher haben wir in einem solchen Fall mit dem Produkt der Zeit für das Zählen der Antworten der Komponenten gearbeitet, jetzt arbeiten wir mit der Summe. Und um das Branching zu beschleunigen, müssen wir den zusammenhängenden Graphen in einen nicht zusammenhängenden umwandeln.

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ängend macht. Alle Verzweigungspunkte im Graphen können mit einem klassischen Algorithmus in linearer Zeit gefunden werden. Dieser Ansatz beschleunigt das Branching erheblich.

Bei der Entfernung eines der hervorgehobenen Knoten wird der Graph in Komponenten zerfallen.

Das können wir tun, aber wir streben mehr an. Zum Beispiel, kleine minimale Scheitel-Schnitte in Graphen zu suchen und eine Aufteilung an den Scheitelpunkten durchzuführen. 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öße des Graphen bei mehreren tausend Knoten. In einem solchen Szenario müssen in jedem Knoten des Rekursionsbaums Milliarden von Operationen durchgeführt werden. Daher ist es einfach unmöglich, das Problem innerhalb der vorgegebenen Zeit zu lösen.

Lassen Sie uns versuchen, die Lösung 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, einsetzen, der in der Praxis sehr schnell arbeitet. Ich habe den Verdacht, dass man theoretisch eine Laufzeitschätzung beweisen kann , was bereits durchaus akzeptabel ist.

Ich habe mehrmals versucht, Schnitte zwischen Paaren zufälliger Knoten zu finden und die ausgewogensten auszuwählen. Leider brachte das bei den öffentlichen 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änkung auf die Lösungstiefe ausführte. Nach dem Algorithmus, der versuchte, auf diese Weise Schnitte zu finden, blieben größere Graphen übrig. Das liegt daran, dass die Schnitte sehr unausgewogen waren: Wenn man 5-10 Knoten entfernte, konnte man nur 15-20 abspalten.

Es ist erwähnenswert, dass in Artikeln über theoretisch die schnellsten Algorithmen wesentlich fortschrittlichere Techniken zur Auswahl von Knoten für das Abspalten verwendet werden. Diese Techniken haben eine sehr komplexe Implementierung und oft eine schlechte Bewertung bezüglich Zeit und Speicher. Es ist mir nicht gelungen, aus ihnen praktikable Lösungen zu gewinnen.

Wie man die Vereinfachungsregeln anwendet

Wir haben bereits Ideen zur Kernellisierung. Ich erinnere daran:

1. Wenn es einen isolierten Knoten gibt, entfernen Sie ihn.
2. Wenn es einen Knoten mit Grad 1 gibt, entfernen Sie ihn und nehmen Sie seinen Nachbarn als Ergebnis.
3. Wenn es einen Knoten mit mindestens k + 1, nehmen Sie ihn als Ergebnis.

Bei den ersten beiden ist alles klar, aber bei der dritten gibt es einen kleinen Trick. Wenn uns in der humorvollen Aufgabenstellung über 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önnte es jedoch Unterschiede geben, wenn wir einen Solver für das Deckungsproblem schreiben, wie im dritten Punkt erwähnt. kIn Bezug auf die Implementierung gibt es zwei Ansätze. Der erste Ansatz wird als Iterative Deepening bezeichnet. Die Idee ist folgende: Wir können mit einer gewissen sinnvollen Untergrenze für 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ässt. Wenn wir eine Antwort finden, ist sie garantiert optimal, ansonsten können wir diese Grenze um eins erhöhen und erneut starten.

Der andere Ansatz besteht darin, eine aktuelle optimale Antwort zu speichern und nach einer kleineren Antwort zu suchen, und beim Finden diese Parameter zu ändern,

um überflüssige Äste im Suchprozess besser abzuschneiden. k um überflüssige Verzweigungen in der Suche weiter zu reduzieren.

Nach einigen nächtlichen Experimenten habe ich mich auf eine Kombination dieser beiden Ansätze geeinigt: Zuerst führe ich meinen Algorithmus mit einer Begrenzung der Suchtiefe aus (ich wähle sie so, dass sie im Vergleich zur Hauptlösung nahezu vernachlässigbar ist) und nutze die beste gefundene Lösung als obere Grenze für die Antwort — also für genau das. k.

Knoten vom Grad 2

Wir haben die Knoten vom Grad 0 und 1 geklärt. Es stellt sich heraus, dass dies auch für Knoten vom Grad 2 funktioniert, aber dafür sind komplexere Operationen am Graphen erforderlich.

Um dies zu erklären, müssen die Knoten irgendwie gekennzeichnet werden. Nennen wir einen Knoten vom Grad 2 einen Knoten v, und seine Nachbarn — Knoten x und y. Danach haben wir zwei Fälle.

1. Wenn x und y — Nachbarn sind. Dann können wir als Antwort nehmen x und y, und v löschen. Tatsächlich müssen wir aus diesem Dreieck mindestens zwei Knoten in die Antwort aufnehmen, und wir verlieren sicher nicht, wenn wir x und y: sie haben wahrscheinlich noch weitere Nachbarn, während v sie nicht haben.
2. Wenn x und y — keine Nachbarn sind. Dann wird behauptet, dass alle drei Knoten zu einem zusammengeklebt werden können. Die Idee ist, dass in diesem Fall eine optimale Antwort existiert, die wir entweder voder beide Knoten aufnehmen. x und y. Im ersten Fall müssen wir daher alle Nachbarn berücksichtigen x und y, im zweiten Fall ist das nicht unbedingt erforderlich. Dies entspricht genau den Fällen, in denen wir die zusammengefügte Spitze nicht berücksichtigen und wenn wir es tun. Man sollte nur beachten, dass in beiden Fällen das Ergebnis dieser Operation um eins verringert wird.

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

Darüber hinaus ist es notwendig, dass dieser Vorgang umkehrbar ist, um während der Rückkehr aus der Rekursion das Graf wieder in seinen ursprünglichen Zustand zu versetzen. Um dies zu gewährleisten, habe ich die Listen der Kanten der zusammengeführten Knoten nicht geleert; ich wusste dann einfach, welche Kanten wohin geleitet werden müssen. Eine solche Implementierung von Graphen erfordert ebenfalls Sorgfalt, sorgt jedoch für eine ehrliche lineare Zeit. Außerdem passt sie bei Graphen mit mehreren zehntausend Kanten gut in den Cache des Prozessors, was große Geschwindigkeitsvorteile bietet.

Lineares Kern

Schließlich der interessanteste Teil des Kerns.

Beginnen wir damit, dass wir uns erinnern, dass in bipartiten Graphen das minimale Deckenelement in gesucht werden kann. Dafür muss der Algorithmus Hopcroft-Karp verwendet werden, um dort das maximale Paar zu finden, und dann die Theorem von König-Egerváry.

Die Idee des linearen Kerns ist folgende: Zuerst teilen wir den Graphen, das heißt, anstelle jeder Ecke v führen wir zwei Ecken ein und , und anstelle jeder Kante u — v führen wir zwei Kanten ein und . Der erhaltene Graph wird bipartit sein. Wir finden darin die minimale Vertex-Abdeckung. Einige Knoten des ursprünglichen 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önnen und wir die Knoten, die zweimal erfasst wurden, als Ergebnis nehmen sollten. Darüber hinaus besagt er, dass aus den verbleibenden Knoten (denjenigen, die einmal erfasst wurden) mindestens die Hälfte als Ergebnis genommen werden muss.

Gerade haben wir gelernt, im Graphen nicht mehr als 2k Knoten zu belassen. In der Tat, wenn im Ergebnis mindestens die Hälfte aller Knoten verbleibt, dann gibt es dort nicht mehr als 2k.

Hier ist mir ein kleiner Fortschritt gelungen. Es ist klar, dass das auf diese Weise konstruierte Kern von dem abhängt, welches minimale Vertex-Abdeckung im bipartiten Graphen wir gewählt haben. Man möchte so eine wählen, dass die Anzahl der verbleibenden Knoten minimal ist. Früher konnte man das nur in der Zeit . Ich habe jedoch eine Implementierung dieses Algorithmus in der Zeit gefunden , sodass dieses Kern auf Graphen mit Hunderttausenden von Knoten in jeder Phase des Branching gesucht werden kann.

Ergebnis

Die Praxis zeigt, dass meine Lösung bei Tests mit mehreren Hundert Knoten und mehreren Tausend Kanten gut funktioniert. Bei solchen Tests kann man durchaus damit rechnen, dass die Lösung innerhalb von einer halben Stunde gefunden wird. Die Wahrscheinlichkeit, eine Antwort in angemessener Zeit zu finden, steigt grundsätzlich, wenn im Graphen genügend Knoten mit hoher Knotengrad vorhanden sind, beispielsweise mit einem Grad von 10 und mehr.

Um am Wettbewerb teilzunehmen, mussten die Lösungen an optil.ioeingereicht werden. Laut der dort präsentierten Tabellebelegt meine Lösung 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ösungen im Wettbewerb tatsächlich bewertet werden: Meine Lösung besteht zwar weniger Tests als die Lösung auf dem vierten Platz, ist aber bei den Tests, die sie besteht, schneller.

Die Ergebnisse der geschlossenen Tests werden am ersten Juli bekannt gegeben.

Quelle: habr.com