Gibt es eine allgemeine Methode zur Bewertung der Optimalität eines Optimierungsalgorithmus?

Gibt es eine allgemeine Methode zur Bewertung der Optimalität eines Optimierungsalgorithmus, beispielsweise einen Algorithmus zur Lösung eines ansonsten NP-harten oder NP-vollständigen Problems?

Die einzige Methode, die ich bisher gefunden habe, ist der Vergleich der Ergebnisse des Algorithmus mit bereits bekannten optimalen Lösungen.

Wenn nicht, gibt es spezielle Methoden für spezielle Probleme?

BEARBEITEN Zur Verdeutlichung: Mit Optimalität meine ich, wie nahe das Ergebnis an einem optimalen Lösungsergebnis liegt.

Das hängt von der Art des Problems ab.

Wenn es für das Problem ein Polynom-Zeit-Approximationsschema (PTAS) gibt (z. B. Euklidisches TSP), können Sie eine Lösung erhalten, die der optimalen Lösung in der Polynomzeit willkürlich nahe kommt. Das bedeutet, dass es für jedes e > 0 einen Polynomzeitalgorithmus gibt, der eine ungefähre Lösung für Ihr Problem findet, die garantiert innerhalb (1+ e ) der optimalen Lösung liegt. In diesem Fall würden Sie nur die Laufzeit- / Speicherkomplexität für zwei Algorithmen für die gleichen Werte von e vergleichen . Wenn ein Algorithmus die gleichen "Optimalitätsgarantien" wie der andere geben kann, jedoch bei geringeren Laufzeit- / Speicherkosten, ist dies wahrscheinlich der bessere Algorithmus.

Wenn das Problem APX, aber nicht PTAS ist , dh wenn es polynomielle Zeitnäherungsalgorithmen gibt, die garantiert Lösungen erzeugen, die innerhalb eines konstanten Faktors der optimalen Lösung liegen, können Sie diesen konstanten Faktor vergleichen. Der mit dem niedrigeren Faktor führt zu besseren Lösungen (jedoch häufig auf Kosten höherer Laufzeit- / Speicherkosten).

Wenn das Problem in keiner dieser Klassen liegt, können Sie meiner Meinung nach am besten ihre Lösungen für eine Reihe zufälliger Probleme oder für Probleme mit bekannten optimalen Lösungen vergleichen.

Ich glaube nicht, dass es einen allgemeinen Weg gibt, aber es gibt sicherlich Methoden, dies zu tun.

Nehmen Sie zum Beispiel das Problem SET-COVER. Für diejenigen, die das Problem nicht kennen, ist wie folgt:

Gegeben eine Reihe von Elementen B={1,2,...,m}und eine Reihe von Teilmengen, S_1, S_2, ..., S_nderen Vereinigung ist B. Sie versuchen, die Mindestanzahl dieser Teilmengen so zu ermitteln, dass die Gewerkschaft noch besteht B. Ein realistisches typisches Beispiel für dieses Problem ist, dass Sie eine Sammlung von Stadtteilen erhalten und versuchen, die optimalen Orte für die Platzierung von Schulen zu finden, sodass jedes Viertel weniger als eine Entfernung dvon der nächsten Schule entfernt bedient wird. In diesem Fall Bhandelt es sich um die Menge der Nachbarschaften und S_xbesteht aus allen Mengen innerhalb dder Stadt x.

Sie beweisen, dass dieses Problem NP-COMPLETE ist. Es gibt jedoch eine einfache gierige Lösung, bei der Sie wiederholt das Set S_imit der größten Anzahl nicht abgedeckter Elemente auswählen . Und Sie können beweisen, dass dieser Algorithmus gut funktioniert .

Wenn der optimale Algorithmus aus kMengen besteht , besteht der Greedy-Algorithmus aus nicht mehr als k ln(n)Mengen, wobei ln der natürliche Logarithmus ist.

Das Problem der Bestimmung, ob ein Programm für nahezu jede Definition von "Optimalitätsleistung" die "Optimalitätsleistung" A oder die "Optimalitätsleistung" B aufweist, ist im Allgemeinen nicht zu entscheiden (Beweis unten). Dies bedeutet, dass es keine einzige Methode gibt, die Ihnen immer sagen kann, wie optimal ein Algorithmus ist.

Es gibt jedoch Methoden, die häufig bei der Analyse von Approximationsalgorithmen angewendet werden. Oft werden Approximationsalgorithmen anhand ihrer Garantien dahingehend bewertet, wie weit ihre Lösung von der optimalen Lösung entfernt ist. Ich werde ein Beispiel für ein Problem und eine Annäherung geben, die ich mit der Methode der unteren Grenze beweisen werde, die eine sehr häufig verwendete Methode zum Nachweis von Verhältnissen ist.

Das fragliche Problem ist das Problem des „Ladens von Lastwagen“: Wir haben viele identische Lastwagen (so viele wie wir möchten), die jeweils eine Ladung mit einem Gewicht von höchstens T tragen können. Wir haben n Objekte, für die wir in diese Lastwagen laden möchten Transport. Jedes Objekt i hat ein Gewicht w_i, wobei w_i <= T ist (es gibt also keine Gegenstände, die nicht einmal alleine auf einen LKW passen). Gegenstände können nicht in Teile geteilt werden. Wir möchten LKWs auffüllen, damit wir so wenig LKWs wie möglich benötigen. Dieses Problem ist NP-vollständig.

Für dieses Problem gibt es einen sehr einfachen Approximationsalgorithmus. Wir laden einfach einen LKW mit Gegenständen, bis der LKW so voll ist, dass der nächste Artikel nicht mehr passt. Wir nehmen dann einen anderen LKW und beladen diesen LKW mit diesem Artikel, der nicht auf den vorherigen LKW passte. Wir laden keine Gegenstände mehr auf diesen LKW: Stattdessen nehmen wir einen neuen LKW, füllen ihn wieder mit vielen Artikeln, bis er nicht mehr passt, setzen den letzten Artikel wieder auf seinen eigenen LKW und so weiter.

Dieser Algorithmus ist eine sogenannte 2-Näherung für das Problem: Er verwendet höchstens doppelt so viele Lastwagen, wie die optimale Lösung benötigen würde. Das "höchstens" ist entscheidend: Wir haben vielleicht Glück und finden die optimale Lösung, aber zumindest werden wir es nicht schlecht machen.

Um dies zu beweisen, definieren wir zunächst eine Untergrenze für die optimale Anzahl der benötigten LKWs. Stellen Sie sich dazu vor, wir dürfen Gegenstände in Teile schneiden: Wir könnten dann problemlos jeden LKW bis auf den letzten vollständig füllen. Die Anzahl der LKWs, die wir benötigen würden, ist eine Untergrenze für die Anzahl der LKWs, die wir für die ursprüngliche Frage benötigen: Im "besten" Fall füllt die optimale Lösung jeden LKW immer vollständig aus. In diesem Fall ist die Anzahl der LKWs ist gleich, aber wenn die optimale Lösung LKWs unbesetzt lässt, kann es nur mehr LKWs benötigen.

Nun betrachten wir unseren Approximationsalgorithmus. Beachten Sie, dass wir in jedem Schritt (teilweise) zwei LKWs füllen. Beachten Sie auch, dass aufgrund der Funktionsweise des Algorithmus die Elemente im ersten LKW und das Element im zweiten LKW nicht zusammen in den ersten LKW passen, sodass ihre Summe mindestens T beträgt. Dies bedeutet, dass wir bei jedem Schritt mindestens eine volle Ladung laden LKW-Wert von Gegenständen auf zwei LKWs. Vergleichen Sie dies nun mit unserer Untergrenze: In diesem Fall laden wir einen vollen LKW mit Artikeln auf einen LKW. Mit anderen Worten, unser Approximationsalgorithmus berechnet (in linearer Zeit) eine Lösung, die unserer unteren "Lösung" sehr ähnlich sieht, jedoch zwei LKWs anstelle von einem verwendet. Daher verwenden wir höchstens doppelt so viele Lastwagen wie der optimale Algorithmus, da wir höchstens doppelt so viele Lastwagen verwenden wie unsere Untergrenze für den optimalen Algorithmus.

Dieser Algorithmus liefert eine Konstantfaktor-Näherung: Er ist höchstens zweimal so schlecht wie die optimale Lösung. Einige Beispiele für andere Maßnahmen: höchstens C mehr als die optimale Lösung (additiver Fehler, ziemlich selten), höchstens c log n-mal so schlecht wie die optimale Lösung, höchstens cn-mal so schlecht wie die optimale Lösung, höchstens c 2 ^ (dn) mal so schlecht wie die optimale Lösung (sehr schlecht; zum Beispiel lässt der allgemeine TSP nur Algorithmen mit dieser Art von Garantien zu).

Wenn Sie sicher sein möchten, dass der von Ihnen nachgewiesene Faktor der beste Faktor ist, den Sie nachweisen können, sollten Sie natürlich versuchen, Fälle zu finden, in denen die von Ihrem Algorithmus angegebene Lösung tatsächlich so schlecht ist, wie es nur sein kann.

Beachten Sie auch, dass wir manchmal Approximationsalgorithmen für Probleme verwenden, die nicht NP-hart sind.

Das habe ich (unter anderem) im Kurs für Approximationsalgorithmen an meiner Universität gelernt.

Unentscheidbarkeitsbeweis: Sei P ein Problem und A und B Approximationsalgorithmen für P, wobei A und B nicht die gleiche 'Optimalität' für eine sinnvolle Definition von 'Optimalität' haben und die Laufzeit von A und B beide Omega ist (1) (streng langsamer als die konstante Zeit, dh sie werden für größere Fälle langsamer) und wo A und B immer anhalten.

Sei D ein Programm, das behauptet, dass es Folgendes berechnen kann: Wenn ein Programm C eine Näherung für P berechnet, entscheiden Sie, ob es für ausreichend große Eingaben so gut wie A oder so gut wie B ist (Sie können dies daher verwenden, um Programme zu kategorisieren nach ihrer Optimalität).

Wir können dann D verwenden, um das Halteproblem zu lösen. Sei E ein Programm und F eine Eingabe für dieses Programm. Wir werden D verwenden, um zu entscheiden, ob E bei Eingabe F anhalten wird.

Wir entwerfen ein Programm G, das Folgendes ausführt: Wenn eine Eingabe S für Problem P gegeben ist, wird E auf F und A auf S parallel ausgeführt: Es führt E für eine Weile aus, dann A, dann E erneut und so weiter. Wenn E auf F anhält, hört es auf, A auszuführen, und führt stattdessen B auf S aus und gibt das Ergebnis von B zurück. Wenn A anhält, bevor E anhält, gibt es das Ergebnis von A zurück.

Die Verwendung von D auf G entscheidet nun, ob E auf F anhält: Wenn E auf F anhält, hält E für ausreichend große Eingänge S auf F an, bevor A auf S anhält (da die Zeit, die E zum Anhalten benötigt, nicht von der Größe von abhängt die Eingabe im Gegensatz zu A). D berichtet daher, dass G die Optimalitätseigenschaften von B hat. Wenn E nicht bei F anhält, meldet D, dass G die Optimalitätseigenschaften von A hat.