Jederzeit Algorithmus – Wikipedia

Posted on by
before-content-x4

Algorithmus, der eine gültige Lösung für ein Problem zurückgeben kann, selbst wenn er unterbrochen wird

In der Informatik ist ein jederzeit Algorithmus ist ein Algorithmus, der eine gültige Lösung für ein Problem zurückgeben kann, selbst wenn es vor seinem Ende unterbrochen wird. Es wird erwartet, dass der Algorithmus immer bessere Lösungen findet, je länger er läuft.

Die meisten Algorithmen werden vollständig ausgeführt: Sie geben eine einzige Antwort, nachdem ein fester Rechenaufwand durchgeführt wurde. In einigen Fällen möchte der Benutzer den Algorithmus jedoch möglicherweise vor Abschluss beenden. Der erforderliche Rechenaufwand kann beispielsweise erheblich sein, und Rechenressourcen müssen möglicherweise neu zugewiesen werden. Die meisten Algorithmen werden entweder vollständig ausgeführt oder liefern keine nützlichen Lösungsinformationen. Algorithmen können jedoch jederzeit eine Teilantwort zurückgeben, deren Qualität von dem Rechenaufwand abhängt, den sie ausführen konnten. Die Antwort, die von Algorithmen zu jeder Zeit generiert wird, ist eine Annäherung an die richtige Antwort.

Ein jederzeitiger Algorithmus kann auch als “unterbrechbarer Algorithmus” bezeichnet werden. Sie unterscheiden sich von Vertragsalgorithmen, bei denen eine Zeit im Voraus angegeben werden muss. In einem jederzeit verfügbaren Algorithmus kann ein Prozess nur ankündigen, dass er beendet wird.[1]

Das Ziel von Algorithmen ist es, intelligenten Systemen die Möglichkeit zu geben, im Gegenzug für die Bearbeitungszeit qualitativ bessere Ergebnisse zu erzielen.[2] Sie sollen auch zeitlich und ressourcenschonend sein.[3] Sie sind wichtig, da es lange dauern kann, bis künstliche Intelligenz oder KI-Algorithmen die Ergebnisse vervollständigen. Dieser Algorithmus wurde entwickelt, um in kürzerer Zeit abgeschlossen zu werden.[3] Diese sollen auch ein besseres Verständnis dafür vermitteln, dass das System von seinen Agenten abhängig und auf diese beschränkt ist und wie sie kooperativ arbeiten.[3] Ein Beispiel ist die Newton-Raphson-Iteration, mit der die Quadratwurzel einer Zahl ermittelt wird.[4] Ein weiteres Beispiel, das jederzeit Algorithmen verwendet, sind Flugbahnprobleme, wenn Sie auf ein Ziel zielen. Das Objekt bewegt sich durch den Raum, während es darauf wartet, dass der Algorithmus beendet ist, und selbst eine ungefähre Antwort kann seine Genauigkeit erheblich verbessern, wenn sie frühzeitig gegeben wird.[3]

Was Algorithmen jederzeit einzigartig macht, ist ihre Fähigkeit, viele mögliche Ergebnisse für eine bestimmte Eingabe zurückzugeben.[2] Ein jederzeit verwendbarer Algorithmus verwendet viele genau definierte Qualitätsmaßstäbe, um den Fortschritt bei der Problemlösung und bei verteilten Computerressourcen zu überwachen.[2] Es sucht ständig nach der bestmöglichen Antwort mit der Zeit, die es gibt.[5] Es wird möglicherweise erst nach Abschluss ausgeführt und kann die Antwort verbessern, wenn es länger ausgeführt werden darf.[6]

Dies wird häufig bei großen Entscheidungsproblemen verwendet.[7] Dies würde im Allgemeinen keine nützlichen Informationen liefern, es sei denn, es wird beendet.[8] Während dies ähnlich wie bei der dynamischen Programmierung klingt, besteht der Unterschied darin, dass die Feinabstimmung eher durch zufällige als durch sequentielle Anpassungen erfolgt.

Jederzeit sind Algorithmen so konzipiert, dass sie jederzeit angehalten werden können und das beste Ergebnis liefern, das sie bisher gefunden haben.[3] Aus diesem Grund wird es als unterbrechbarer Algorithmus bezeichnet. Bestimmte Algorithmen behalten jederzeit das letzte Ergebnis bei, sodass sie, wenn ihnen mehr Zeit gegeben wird, dort weitermachen können, wo sie aufgehört haben, um ein noch besseres Ergebnis zu erzielen.[3]

Entscheidungsbäume[edit]

Wenn der Entscheider handeln muss, muss es einige Unklarheiten geben. Es muss auch eine Idee geben, wie diese Mehrdeutigkeit gelöst werden kann. Diese Idee muss in ein State-to-Action-Diagramm übersetzbar sein.[7]

Leistungsprofil[edit]

Das Leistungsprofil schätzt die Qualität der Ergebnisse basierend auf der Eingabe und der Zeit, die dem Algorithmus zugewiesen ist.[3] Je besser die Schätzung, desto eher würde das Ergebnis gefunden werden.[3] Einige Systeme verfügen über eine größere Datenbank, die die Wahrscheinlichkeit angibt, dass die Ausgabe die erwartete Ausgabe ist.[3] Es ist wichtig zu beachten, dass ein Algorithmus mehrere Leistungsprofile haben kann.[9] Die meisten Zeitleistungsprofile werden unter Verwendung mathematischer Statistiken unter Verwendung repräsentativer Fälle erstellt. Beispielsweise wurde beim Problem mit reisenden Verkäufern das Leistungsprofil mithilfe eines benutzerdefinierten Spezialprogramms erstellt, um die erforderlichen Statistiken zu erstellen.[1] In diesem Beispiel ist das Leistungsprofil die Zuordnung der Zeit zu den erwarteten Ergebnissen.[1] Diese Qualität kann auf verschiedene Arten gemessen werden:

  • Gewissheit: Wo die Wahrscheinlichkeit der Korrektheit die Qualität bestimmt[1]
  • Genauigkeit: wobei die Fehlergrenze die Qualität bestimmt[1]
  • Spezifität: wobei die Anzahl der Angaben die Qualität bestimmt[1]

Algorithmusvoraussetzungen[edit]

Anfängliches Verhalten: Während einige Algorithmen mit sofortigen Vermutungen beginnen, verfolgen andere einen kalkulierten Ansatz und haben eine Startphase, bevor sie Vermutungen anstellen.[9]

  • Wachstumsrichtung: Wie sich die Qualität der “Ausgabe” oder des Ergebnisses des Programms in Abhängigkeit von der Zeitdauer (“Laufzeit”) ändert[9]
  • Wachstumsrate: Betrag der Erhöhung mit jedem Schritt. Ändert es sich ständig, beispielsweise bei einer Blasensorte, oder ändert es sich unvorhersehbar?
  • Endbedingung: Die benötigte Laufzeit[9]

Verweise[edit]

  1. ^ ein b c d e f Hendler, James A., Planungssysteme für künstliche Intelligenz1992
  2. ^ ein b c Zilberstein, Shlomo. “Verwenden von Anytime-Algorithmen in intelligenten Systemen”, 1996. http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf
  3. ^ ein b c d e f G h ich Gras, Joshua. “Argumentation zur rechnergestützten Ressourcenzuweisung.” http://www.acm.org/crossroads/xrds3-1/racra.html Archiviert 2007-12-12 an der Wayback Machine
  4. ^ jederzeit Algorithmus aus Free Free Dictionary of Computing (FOLDOC)
  5. ^ “Jederzeit Algorithmen”. Kognitive Architekturen. Labor für künstliche Intelligenz der Universität von Michigan. Archiviert von das Original am 13. Dezember 2013. CS1-Wartung: entmutigter Parameter (Link)
  6. ^ “Jederzeit Algorithmus – Rechenreferenz”. eLook.org. Archiviert von das Original am 12. Dezember 2013. CS1-Wartung: entmutigter Parameter (Link)
  7. ^ ein b Horsch, Michael C., Poole, David “Ein jederzeitiger Algorithmus zur Entscheidungsfindung unter Unsicherheit”, 2013, http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf
  8. ^ Bender, Edward A. Mathematische Methoden in der künstlichen Intelligenz, IEEE Computer Society Pres, 1996
  9. ^ ein b c d Teije, Annette Ten, Harmelen, Frank. “Beschreiben von Problemlösungsmethoden unter Verwendung von Leistungsprofilen zu jeder Zeit”, 2000.

Weiterführende Literatur[edit]

  • Boddy, M., Dean, T. 1989. Zeitabhängige Planungsprobleme lösen. Technischer Bericht: CS-89-03, Brown University
  • Grass, J. und Zilberstein, S. 1996. Anytime Algorithm Development Tools. SIGART Bulletin (Sonderheft zu beliebigen Algorithmen und zur Planung von Beratungen) 7 (2)
  • Michael C. Horsch und David Poole, Ein jederzeitiger Algorithmus zur Entscheidungsfindung unter Unsicherheit, In Proc. 14. Konferenz über Unsicherheit in der künstlichen Intelligenz (UAI-98), Madison, Wisconsin, USA, Juli 1998, Seiten 246-255.
  • EJ Horvitz. Argumentation über Inferenzkompromisse in einer Welt begrenzter Ressourcen. Technischer Bericht KSL-86-55, Medical Computer Science Group, Abteilung für Medizinische Informatik, Stanford University, Stanford, CA, März 1986
  • Wallace, R. und Freuder, E. 1995. Jederzeit Algorithmen für Constraint Satisfaction und SAT-Probleme. Vortrag gehalten auf dem IJCAI-95 Workshop zu Anytime Algorithms und Deliberation Scheduling am 20. August in Montreal, Kanada.
  • Zilberstein, S. 1993. Operative Rationalität durch Kompilierung von Algorithmen zu jeder Zeit. Ph.D. Diss., Abteilung Informatik, Universität von Kalifornien in Berkeley.
  • Shlomo Zilberstein, der jederzeit Algorithmen in intelligenten Systemen verwendet, AI Magazine17 (3), 73-83 (1996)


after-content-x4