Online -Algorithmus

Nicht zu verwechseln mit online und offline.

Im Informatik, ein Online -Algorithmus[1] ist eine, die seine Eingangspiefe seriell verarbeiten kann, d. H. In der Reihenfolge, dass die Eingabe an die eingespeist wird Algorithmus, ohne den gesamten Eingang von Anfang an verfügbar zu haben.

Dagegen eine Offline -Algorithmus Wird die gesamten Problemdaten von Anfang an gegeben und ist erforderlich, um eine Antwort auszugeben, die das vorliegende Problem löst. Im UnternehmensforschungDer Bereich, in dem Online -Algorithmen entwickelt werden, wird genannt Online -Optimierung.

Betrachten Sie als Beispiel die Sortieren von Algorithmen Auswahlsorten und Sortieren durch Einfügen: Die Auswahlsortierung wählt wiederholt das Mindestelement aus dem unortheiligen Rest aus und platziert es vorne, was den Zugriff auf die gesamte Eingabe erfordert. Es ist also ein Offline -Algorithmus. Andererseits berücksichtigt die Insertions -Sortierung ein Eingabeelement pro Iteration und erzeugt eine teilweise Lösung, ohne zukünftige Elemente zu berücksichtigen. Somit ist die Insertions -Sortierung ein Online -Algorithmus.

Beachten Sie, dass das Endergebnis einer Insertionsart optimal ist, d. H. Eine korrekt sortierte Liste. Bei vielen Problemen können Online -Algorithmen nicht mit der Leistung von Offline -Algorithmen übereinstimmen. Wenn das Verhältnis zwischen der Leistung eines Online -Algorithmus und einem optimalen Offline -Algorithmus begrenzt ist, wird der Online -Algorithmus aufgerufen wettbewerbsfähig.[1]

Nicht jeder Offline -Algorithmus hat eine effiziente online Gegenstück.

Definition

Da es nicht die gesamte Eingabe kennt, ist ein Online-Algorithmus gezwungen, Entscheidungen zu treffen, die später nicht optimal sind, und die Studie von Online-Algorithmen hat sich auf die Qualität der Entscheidungsfindung konzentriert, die in dieser Umgebung möglich ist. Wettbewerbsanalyse Formalisiert diese Idee, indem Sie die relative Leistung eines Online- und Offline -Algorithmus für dieselbe Probleminstanz vergleichen. Insbesondere ist das Wettbewerbsverhältnis eines Algorithmus als das schlimmste Verhältnis seiner Kosten geteilt durch die optimalen Kosten über alle möglichen Eingaben. Das Wettbewerbsverhältnis eines Online -Problems ist das beste Wettbewerbsverhältnis, das durch einen Online -Algorithmus erzielt wird. Intuitiv liefert das Wettbewerbsverhältnis eines Algorithmus eine Maßnahme für die Qualität der von diesem Algorithmus erzeugten Lösungen, während das Wettbewerbsverhältnis eines Problems zeigt, wie wichtig es ist, die Zukunft für dieses Problem zu kennen.

Andere Interpretationen

Für andere Standpunkte auf Online -Eingaben zu Algorithmen, sehen

  • Streaming -Algorithmus: Konzentration auf die Menge an Speicher, die erforderlich ist, um frühere Eingaben genau darzustellen;
  • Dynamischer Algorithmus: Konzentration auf die Zeitkomplexität der Aufrechterhaltung von Lösungen für Probleme mit Online -Inputs.

Beispiele

Etwas Online -Algorithmen:

Online -Probleme

Ein Problem, das die Konzepte von Online -Algorithmen veranschaulicht, ist die Kanadisches Reisenderproblem. Ziel dieses Problems ist es, die Kosten für das Erreichen eines Ziels in einem gewichteten Diagramm zu minimieren, in dem einige der Kanten unzuverlässig sind und möglicherweise aus dem Diagramm entfernt wurden. Es wurde jedoch eine Kante entfernt (gescheitert) wird nur offenbart der Reisende Wenn sie/er einen der Endpunkte des Edge erreicht. Der schlimmste Fall für dieses Problem ist einfach, dass alle unzuverlässigen Kanten fehlschlagen und das Problem auf die üblichen Abfälle reduziert werden Kürzestes Pfadproblem. Eine alternative Analyse des Problems kann mit Hilfe der Wettbewerbsanalyse durchgeführt werden. Für diese Analysemethode weiß der Offline -Algorithmus im Voraus, welche Kanten fehlschlagen, und das Ziel ist es, das Verhältnis zwischen der Leistung der Online- und Offline -Algorithmen zu minimieren. Dieses Problem ist PSPACE-Complete.

Es gibt viele formelle Probleme, die mehr als einen bieten Online -Algorithmus als Lösung:

Siehe auch

Verweise

  1. ^ a b Karp, Richard M. (1992). "Online-Algorithmen gegen Offline-Algorithmen: Wie viel ist es wert, die Zukunft zu kennen?" (PDF). IFIP -Kongress (1). 12: 416–429. Abgerufen 17. August 2015.
  2. ^ Dochow, Robert (2016). Online -Algorithmen für das Problem der Portfolioauswahl. Springer Gabler.

Externe Links