Näherungsalgorithmus

Im Informatik und Unternehmensforschung, Näherungsalgorithmen sind effizient Algorithmen das findet ungefähr Lösungen an Optimierungsprobleme (im Speziellen Np-harte Probleme mit nachweisbare Garantien Auf der Entfernung der zurückgegebenen Lösung zum optimalen.[1] Näherungsalgorithmen entstehen natürlich im Bereich von Theoretische Informatik Infolge der weithin geglaubten P ≠ np Vermutung. Unter dieser Vermutung kann eine breite Klasse von Optimierungsproblemen nicht genau gelöst werden Polynomzeit. Das Feld der Approximationsalgorithmen versucht daher zu verstehen, wie eng es möglich ist, optimale Lösungen für solche Probleme in der Polynomzeit zu approximieren. In einer überwältigenden Mehrheit der Fälle ist die Garantie solcher Algorithmen ein multiplikatives, das als Annäherungsverhältnis oder Approximationsfaktor ausgedrückt wird, d. H. Die optimale Lösung wird immer garantiert innerhalb eines (vorgegebenen) multiplikativen Faktors der zurückgegebenen Lösung garantiert. Es gibt jedoch auch viele Annäherungsalgorithmen, die eine additive Garantie für die Qualität der zurückgegebenen Lösung bieten. Ein bemerkenswertes Beispiel für einen Annäherungsalgorithmus, der liefert beide ist der klassische Näherungsalgorithmus von Lenstra, Shmoys und TARDOS[2] zum Planung auf nicht verwandten parallelen Maschinen.

Das Design und die Analyse von Approximationsalgorithmen beinhalten entscheidend einen mathematischen Beweis, der die Qualität der zurückgegebenen Lösungen im schlimmsten Fall zertifiziert.[1] Dies unterscheidet sie von Heuristik wie zum Beispiel Glühen oder genetische Algorythmen, die in einigen Eingaben einigermaßen gute Lösungen finden, aber zu Beginn keinen klaren Hinweis geben, wenn sie erfolgreich sein oder scheitern können.

Es besteht ein weit verbreitetes Interesse an Theoretische Informatik Um die Grenzen, an die wir bestimmte berühmte Optimierungsprobleme annähern können, besser zu verstehen. Zum Beispiel ist eine der langjährigen offenen Fragen in der Informatik festzustellen, ob es einen Algorithmus gibt, der die übertrifft 1,5 Approximationsalgorithmus von Christofides zur Metrik reisende Verkäuferprobleme. Der Wunsch, die schwierigen Optimierungsprobleme aus der Sicht der Annäherung zu verstehen, wird durch die Entdeckung überraschender mathematischer Verbindungen und allgemein anwendbarer Techniken zur Entwurf von Algorithmen für harte Optimierungsprobleme motiviert. Ein bekanntes Beispiel für das erstere ist das Goemans -Williamson -Algorithmus zum Maximaler Schnitt, was ein graphentheoretisches Problem unter Verwendung einer hohen dimensionalen Geometrie löst.[3]

Einführung

Ein einfaches Beispiel für einen Näherungsalgorithmus ist eines für die Mindestabdeckung von Scheitelpunkten Problem, wobei das Ziel darin besteht, den kleinsten Satz von Scheitelpunkten so auszuwählen, dass jede Kante im Eingangsdiagramm mindestens einen ausgewählten Scheitelpunkt enthält. Eine Möglichkeit, eine Scheitelpunktabdeckung zu finden, besteht darin, den folgenden Vorgang zu wiederholen: Suchen Sie eine unbedeckte Kante, fügen Sie beide Endpunkte in die Abdeckung und entfernen Sie alle Kanten, die von den Scheitelpunkten aus dem Diagramm ausfallen. Da jeder Scheitelpunktabdeckung des Eingangsdiagramms einen bestimmten Scheitelpunkt verwenden muss, um jede Kante abzudecken, die im Prozess berücksichtigt wurde (da er a Matching) Die produzierte Scheitelpunktabdeckung ist daher höchstens doppelt so groß wie die optimale. Mit anderen Worten, das ist a Algorithmus des Konstantenfaktors mit einem Annäherungsfaktor von 2. unter den jüngsten Einzigartige Spiele vermutlichDieser Faktor ist sogar der bestmögliche.[4]

NP-harte Probleme variieren stark in ihrer Annäherung; einige, wie die Rucksackproblem, kann innerhalb eines multiplikativen Faktors angenähert werden , für alle festen und erzeugen daher Lösungen willkürlich nahe am Optimum (eine solche Familie von Annäherungsalgorithmen wird als a genannt Polynomzeitnäherungsschema oder ptas). Andere sind unmöglich, sich innerhalb eines konstanten oder sogar Polynoms zu approximieren, es sei denn P = np, wie im Fall der Maximales Clique -Problem. Ein wichtiger Vorteil bei der Untersuchung von Annäherungsalgorithmen ist daher eine feinkörnige Klassifizierung der Schwierigkeit verschiedener NP-HART-Probleme, die über die von der gelieferten Personen hinausgehen Theorie der NP-Vervollständigung. Mit anderen Worten, obwohl NP-Complete-Probleme aus der Perspektive der genauen Lösungen äquivalent sein können (unter Polynomzeitreduzierungen), verhalten sich die entsprechenden Optimierungsprobleme sehr unterschiedlich als die Perspektive der ungefähren Lösungen.

Algorithmus -Designtechniken

Inzwischen gibt es mehrere etablierte Techniken, um Annäherungsalgorithmen zu entwerfen. Dazu gehören die folgenden.

  1. Gieriger Algorithmus
  2. Lokale Suche
  3. Aufzählung und Dynamische Programmierung
  4. Lösung a Konvexe Programmierung Entspannung, um eine fraktionale Lösung zu erhalten. Wenden Sie diese fraktionale Lösung dann durch eine geeignete Rundung in eine praktikable Lösung. Zu den beliebten Relaxationen gehören die folgenden.
  5. Urmethoden
  6. Doppelpassend
  7. Einbetten Sie das Problem in eine Metrik ein und lösen Sie dann das Problem in der Metrik. Dies wird auch als metrische Einbettung bezeichnet.
  8. Zufällige Stichproben und die Verwendung von Zufälligkeit im Allgemeinen in Verbindung mit den oben genannten Methoden.

Ein posteriori garantiert

Während Annäherungsalgorithmen immer eine a priori schlimmste Fallgarantie (additiv oder multiplikativ) bieten, bieten sie in einigen Fällen auch eine A -posteriori -Garantie, die oft viel besser ist. Dies ist häufig bei Algorithmen der Fall, die durch Lösen von a funktionieren Konvexe Entspannung des Optimierungsproblems auf der angegebenen Eingabe. Zum Beispiel gibt es einen anderen Annäherungsalgorithmus für minimale Scheitelpunktabdeckungen, die a löst Lineare Programmierrelaxation Um eine Scheitelpunktabdeckung zu finden, die höchstens so doppelt so hoch ist wie der Wert der Entspannung. Da der Wert der Relaxation nie größer ist als die Größe der optimalen Scheitelpunktabdeckung, ergibt dies einen weiteren 2-Anerkennungsalgorithmus. Während dies der a priori -Garantie des vorherigen Annäherungsalgorithmus ähnlich ist, kann die Garantie des letzteren viel besser sein (wenn der Wert der LP -Relaxation weit entfernt von der Größe der optimalen Scheitelpunktabdeckung ist).

Annäherungshärte

Näherungsalgorithmen als Forschungsgebiet sind eng mit dem verwandt mit und informiert von Unangemessenheitstheorie wobei die Nichtbelegung effizienter Algorithmen mit bestimmten Approximationsverhältnissen (konditioniert auf allgemein angesehene Hypothesen wie die p ≠ np-Vermutung) mittels nachgewiesen wird Reduzierungen. Im Fall des Problems mit metrisch reisenden Verkäufern schließt das am bekannteste unangemessene Ergebnis -Ergebnis Algorithmen mit einem Annäherungsverhältnis von weniger als 123/122 ≈ 1,008196 aus, es sei denn, P = NP, Karpinski, Lampis, Schmied.[5] In Verbindung mit der Kenntnis der Existenz des 1,5 -Annäherungsalgorithmus von Christofides zeigt uns, dass der Schwellenwert der Annäherung an metrische reisende Verkäufer (falls vorhanden) zwischen 123/122 und 1,5 liegt.

Während seit den 1970er Jahren unangemessene Ergebnisse nachgewiesen wurden, wurden solche Ergebnisse mit Ad -hoc -Mitteln erzielt und zu diesem Zeitpunkt kein systematisches Verständnis verfügbar. Erst seit dem Ergebnis von Feige, Goldwasser, Lovász, Safra und Szegedy von 1990 über die unangemessene Unabhängiger Satz[6] und der berühmte PCP -Theorem,[7] Die modernen Instrumente zum Nachweis von unangemessenen Ergebnissen wurden aufgedeckt. Der PCP -Theorem zeigt zum Beispiel das Johnsons 1974 Approximationalgorithmen für Max Sat, Deckung festlegen, unabhängiger Satz und Färbung Alle erreichen das optimale Approximationsverhältnis unter der Annahme von p ≠ np.[8]

Praktikabilität

Nicht alle Annäherungsalgorithmen sind für direkte praktische Anwendungen geeignet. Einige beinhalten das Lösen von Nichttrivial Lineares Programmieren/semidefinit Entspannungen (die selbst das berufen können Ellipsoid -Algorithmus), komplexe Datenstrukturen oder ausgefeilte algorithmische Techniken, die zu schwierigen Implementierungsproblemen oder einer verbesserten Laufzeitleistung (über exakte Algorithmen) nur bei unpraktisch großen Eingaben führen. Abgesehen von Problemen der Umsetzung und Laufzeit, die Garantien, die durch Annäherungsalgorithmen bereitgestellt werden, sind möglicherweise nicht stark genug, um ihre Überlegungen in der Praxis zu rechtfertigen. Trotz ihrer Unfähigkeit, in praktischen Anwendungen "aus dem Box" verwendet zu werden, können die Ideen und Erkenntnisse hinter der Gestaltung solcher Algorithmen häufig auf andere Weise in praktischen Algorithmen aufgenommen werden. Auf diese Weise ist das Studium selbst sehr teurer Algorithmen keine völlig theoretische Verfolgung, da sie wertvolle Erkenntnisse liefern können.

In anderen Fällen können die Algorithmen im Laufe der Zeit im Laufe der Zeit mit einem verbesserten Verständnis von rein theoretischem Interesse mit einem verbesserten Verständnis sind, um praktischer zu werden. Ein solches Beispiel ist die anfängliche PTAs für Euklidischer TSP durch Sanjeev Arora (und unabhängig von Joseph Mitchell), die eine unerschwingliche Laufzeit hatten Für ein Annäherung.[9] Innerhalb eines Jahres wurden diese Ideen jedoch in eine nahezu lineare Zeit aufgenommen Algorithmus für jede Konstante .[10]

Leistungsgarantien

Bei einigen Approximationsalgorithmen ist es möglich, bestimmte Eigenschaften über die Annäherung des optimalen Ergebnisses zu beweisen. Zum Beispiel a ρ-Amgläubiger Algorithmus A wird als Algorithmus definiert, für den sich der Wert/die Kosten nachgewiesen hat, dass der Wert/die Kosten, f(x) der ungefähren Lösung A(x) zu einer Instanz x wird nicht mehr (oder weniger, abhängig von der Situation) als ein Faktor sein ρ mal den Wert, opt, einer optimalen Lösung.

Der Faktor ρ wird genannt Relative Leistungsgarantie. Ein Annäherungsalgorithmus hat eine Absolute Leistungsgarantie oder Begrenzter Fehler c, wenn es für jede Instanz nachgewiesen wurde x das

Ebenso das Leistungsgarantie, R(x, y) von einer Lösung y zu einem Fall x ist definiert als

wo f(y) ist der Wert/die Kosten der Lösung y für die Instanz x. Die Leistungsgarantie ist eindeutig größer als oder gleich 1 und gleich 1, wenn und nur wenn y ist eine optimale Lösung. Wenn ein Algorithmus A Garantien für die Rückgabe von Lösungen mit einer Leistungsgarantie höchstens r(n), dann A soll ein r(n) -Anprüfungsalgorithmus und hat eine Annäherungsverhältnis von r(n). Ebenso ein Problem mit einem r(n) -Anprüfungsalgorithmus soll r sein(n)-annähernd oder ein Annäherungsverhältnis von haben r(n).[11][12]

Bei Minimierungsproblemen liefern die beiden verschiedenen Garantien das gleiche Ergebnis, und für Maximierungsprobleme ist eine relative Leistungsgarantie von ρ gleichwertig einer Leistungsgarantie von . In der Literatur sind beide Definitionen häufig, aber es ist klar, welche Definition verwendet wird, da für Maximierungsprobleme als ρ ≤ 1 während r ≥ 1.

Das Absolute Leistungsgarantie eines Annäherungsalgorithmus A, wo x bezieht sich auf eine Instanz eines Problems und wo ist die Leistungsgarantie von A an x (d. H. ρ als Probleminstanz x) ist:

Das heißt das ist die größte Grenze für das Annäherungsverhältnis, rDas sieht man über alle möglichen Instanzen des Problems. Ebenso das Asymptotisches Leistungsverhältnis ist:

Das heißt, dass es dasselbe ist wie das Absolute Leistungsverhältnismit einer unteren Grenze n über die Größe der Probleminstanzen. Diese beiden Arten von Verhältnissen werden verwendet, da es Algorithmen gibt, bei denen der Unterschied zwischen diesen beiden signifikant ist.

Leistungsgarantien
r-Applox[11][12] ρ-Applox rel. Error[12] rel. Error[11] Norm. rel. Error[11][12] Abs. Error[11][12]
Max:
Mindest:

Epsilon -Begriffe

In der Literatur ein Annäherungsverhältnis für eine Maximierung (Minimierung) Problem von c - ϵ (min: c + ϵ) bedeutet, dass der Algorithmus ein Annäherungsverhältnis von hat c ∓ ϵ für willkürliche ϵ> 0, das Verhältnis jedoch nicht für ϵ = 0. Ein Beispiel hier Max-3sat Beispiele aufgrund Johan Håstad.[13] Wie bereits erwähnt, wann c = 1 soll das Problem a haben Polynom-Zeit-Approximationsschema.

Ein ϵ-Term kann auftreten, wenn ein Approximationsalgorithmus einen multiplikativen Fehler und einen konstanten Fehler einführt, während das minimale Optimum an Größenfällen anfällt n geht zur Unendlichkeit als n tut. In diesem Fall ist das Annäherungsverhältnis ck / Opt = c ∓ o (1) für einige Konstanten c und k. Bei willkürlicher ϵ> 0 kann man ein groß genug wählen N so dass der Begriff k / Opt <ϵ für jeden n ≥ n. Für jedes feste ϵ, Instanzen der Größe n <n kann durch Brute -Kraft gelöst werden, wodurch ein Annäherungsverhältnis gezeigt wird - Existenz von Approximationsalgorithmen mit einer Garantie - von - von c ∓ ϵ für jedes ϵ> 0.

Siehe auch

Zitate

  1. ^ a b Bernard., Shmoys, David (2011). Das Design von Approximationsalgorithmen. Cambridge University Press. ISBN 9780521195270. OCLC 671709856.
  2. ^ Lenstra, Jan Karel; Shmoys, David B.; TARDOS, ÉVA (1990-01-01). "Näherungsalgorithmen zur Planung von nicht verwandten parallelen Maschinen". Mathematische Programmierung. 46 (1–3): 259–271. Citeseerx 10.1.1.115.708. doi:10.1007/bf01585745. ISSN 0025-5610. S2CID 206799898.
  3. ^ Goemans, Michel X.; Williamson, David P. (November 1995). "Verbesserte Approximationsalgorithmen für maximale Schnitt- und Erfüllbarkeitsprobleme unter Verwendung einer semidfiniten Programmierung". J. ACM. 42 (6): 1115–1145. Citeseerx 10.1.1.34.8500. doi:10.1145/227683.227684. ISSN 0004-5411. S2CID 15794408.
  4. ^ Khot, Subhash; Regev, ODED (2008-05-01). "Die Scheitelpunktabdeckung ist möglicherweise schwer zu innerhalb von 2 - ε zu approximieren.". Journal of Computer and System Sciences. Computerkomplexität 2003. 74 (3): 335–349. doi:10.1016/j.jcss.2007.06.019.
  5. ^ Karpinski, Marek; Lampis, Michael; Schmied, Richard (2015-12-01). "Neue unzählige Grenzen für TSP". Journal of Computer and System Sciences. 81 (8): 1665–1677. Arxiv:1303.6437. doi:10.1016/j.jcs.2015.06.003.
  6. ^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (März 1996). "Interaktive Beweise und die Härte der Annäherung von Cliquen". J. ACM. 43 (2): 268–292. doi:10.1145/226643.226652. ISSN 0004-5411.
  7. ^ Arora, Sanjeev; Safra, Shmuel (Januar 1998). "Probabilistische Überprüfung von Beweisen: Eine neue Charakterisierung von NP". J. ACM. 45 (1): 70–122. doi:10.1145/273865.273901. ISSN 0004-5411. S2CID 751563.
  8. ^ Johnson, David S. (1974-12-01). "Näherungsalgorithmen für kombinatorische Probleme". Journal of Computer and System Sciences. 9 (3): 256–278. doi:10.1016/s0022-0000 (74) 80044-9.
  9. ^ Arora, S. (Oktober 1996). "Polynomzeitnäherungsschemata für euklidische TSP und andere geometrische Probleme". Verfahren der 37. Konferenz über Stiftungen der Informatik. S. 2–11. Citeseerx 10.1.1.32.3376. doi:10.1109/sfcs.1996.548458. ISBN 978-0-8186-7594-2. S2CID 1499391. {{}}: Fehlen oder leer |title= (Hilfe)
  10. ^ Arora, S. (Oktober 1997). "Fast lineare Zeitnäherungsschemata für euklidische TSP und andere geometrische Probleme". Proceedings 38. jährliches Symposium für Grundlagen der Informatik. S. 554–563. doi:10.1109/sfcs.1997.646145. ISBN 978-0-8186-8197-4. S2CID 10656723. {{}}: Fehlen oder leer |title= (Hilfe)
  11. ^ a b c d e G. Ausiello; P. crescenzi; G. Gamsisi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). Komplexität und Näherung: Kombinatorische Optimierungsprobleme und deren Annäherungseigenschaften.
  12. ^ a b c d e Viggo Kann (1992). Bei der Annäherung an NP-Complete-Optimierungsprobleme (PDF).
  13. ^ Johan Håstad (1999). "Einige optimale Unangemessenheitsergebnisse". Journal of the ACM. 48 (4): 798–859. Citeseerx 10.1.1.638.2808. doi:10.1145/502090.502098. S2CID 5120748.

Verweise

Externe Links