Heuristik (Informatik)

Im Mathematische Optimierung und Informatik, Heuristik (Aus griechisch εὑρίσκω "Ich finde, entdecke") ist eine Technik, für die entwickelt wurde ein Problem lösen schneller, wenn klassische Methoden zu langsam sind oder eine ungefähre Lösung finden, wenn klassische Methoden keine genaue Lösung finden. Dies wird durch Handelsoptimalität, Vollständigkeit erreicht, Richtigkeit, oder Präzision für Geschwindigkeit. In gewisser Weise kann es als Abkürzung angesehen werden.

A Heuristische Funktion, auch einfach a genannt Heuristik, ist ein Funktion Das rangiert Alternativen in Suchalgorithmen Bei jedem Verzweigungsschritt basierend auf verfügbaren Informationen, um zu entscheiden, welcher Zweigstelle sie folgen sollen. Zum Beispiel kann es die genaue Lösung annähern.^[1]

Definition und Motivation

Das Ziel einer Heuristik ist es, eine Lösung in einem angemessenen Zeitrahmen zu erzeugen, der gut genug ist, um das vorliegende Problem zu lösen. Diese Lösung ist möglicherweise nicht die beste von allen Lösungen für dieses Problem, oder sie kann einfach die genaue Lösung annähern. Aber es ist immer noch wertvoll, weil es keine unerschwinglich lange Zeit erfordert.

Heuristiken können selbst Ergebnisse erzielen, oder sie können in Verbindung mit Optimierungsalgorithmen verwendet werden, um ihre Effizienz zu verbessern (z. B. können sie verwendet werden, um gute Saatgutwerte zu erzeugen).

Ergebnisse über NP-Hardness In der theoretischen Informatik machen die Heuristiken die einzig praktikable Option für eine Vielzahl komplexer Optimierungsprobleme, die in realen Anwendungen routinemäßig gelöst werden müssen.

Heuristiken liegen im gesamten Feld der künstlichen Intelligenz und der Computersimulation des Denkens zugrunde, wie sie in Situationen verwendet werden können, in denen es keine Bekannten gibt Algorithmen.^[2]

Abtausch

Die Kompromisskriterien für die Entscheidung, ob eine Heuristik zur Lösung eines bestimmten Problems verwendet werden soll, umfassen Folgendes:

Optimalität: Wenn für ein bestimmtes Problem mehrere Lösungen vorhanden sind, garantiert die heuristische Lösung, dass die beste Lösung gefunden wird? Ist es tatsächlich notwendig, die beste Lösung zu finden?
Vollständigkeit: Wenn für ein bestimmtes Problem mehrere Lösungen vorhanden sind, kann die Heuristik sie alle finden? Brauchen wir tatsächlich alle Lösungen? Viele Heuristiken sollen nur eine Lösung finden.
Genauigkeit und Präzision: Kann die Heuristik a liefern Konfidenzintervall Für die angebliche Lösung? Ist die Fehlerleiste der Lösung unangemessen groß?
Ausführungszeit: Ist dies die bekannteste Heuristik für die Lösung dieser Art von Problem? Einige Heuristiken konvergieren schneller als andere. Einige Heuristiken sind nur geringfügig schneller als klassische Methoden. In diesem Fall kann der „Overhead“ zur Berechnung der Heuristik negative Auswirkungen haben.

In einigen Fällen kann es schwierig sein zu entscheiden, ob die von der Heuristik gefundene Lösung gut genug ist, da die Theorie, die Heuristik zugrunde liegt, nicht sehr ausführlich ist.

Beispiele

Einfacheres Problem

Eine Möglichkeit, den Rechenleistungsertrag zu erreichen, der von einer Heuristik erwartet wird, besteht darin, ein einfacheres Problem zu lösen, dessen Lösung auch eine Lösung für das anfängliche Problem ist.

Problem mit reisenden Verkäufern

Ein Beispiel für Annäherungen wird durch beschrieben Jon Bentley für die Lösung der Problem mit reisenden Verkäufern (TSP):

"Was ist angesichts einer Liste von Städten und den Entfernungen zwischen jedem Städtepaar die kürzeste Route, die jede Stadt genau einmal besucht und in die Ursprungsstadt zurückkehrt?"

Um die Reihenfolge zu wählen, um mit a zu zeichnen Stiftplotter. TSP ist bekannt, dass es sich handelt Np-harte Eine optimale Lösung für selbst ein mittelschwerer Größe ist also schwer zu lösen. Stattdessen die Gieriger Algorithmus Kann verwendet werden, um eine gute, aber nicht optimale Lösung zu geben (es ist eine Annäherung an die optimale Antwort) in einigermaßen kurzer Zeit. Der gierige Algorithmus Heuristic sagt, er solle das derzeit der beste nächste Schritt auswählen, unabhängig davon, ob dies später gute Schritte verhindern (oder sogar unmöglich macht). Es ist eine Heuristik in dieser Praxis sagt, dass es eine gute Lösung ist, sagt Theorie, dass es bessere Lösungen gibt (und sogar in einigen Fällen sagen kann, wie viel besser).^[3]

Suche

Ein weiteres Beispiel dafür, dass Heuristik einen Algorithmus schneller macht, tritt bei bestimmten Suchproblemen auf. Zunächst versucht die Heuristik bei jedem Schritt jede Möglichkeit, wie der Vollraum-Suchalgorithmus. Aber es kann die Suche jederzeit stoppen, wenn die aktuelle Möglichkeit bereits schlechter ist als die beste Lösung, die bereits gefunden wurde. Bei solchen Suchproblemen kann eine Heuristik zuerst gute Entscheidungen ausprobieren, damit schlechte Wege frühzeitig beseitigt werden können (siehe Alpha-Beta-Schnitt). Im Falle des Best-First-Suche Algorithmen, wie z. Eine SucheDie Heuristik verbessert die Konvergenz des Algorithmus und behält ihre Richtigkeit bei, solange die Heuristik ist zulässig.

Newell und Simon: Heuristische Suchhypothese

In ihren Turing Award Akzeptanzrede, Allen Newell und Herbert A. Simon Diskutieren Sie die heuristische Suchhypothese: Ein physikalisches Symbolsystem erzeugt und modifiziert bekannte Symbolstrukturen wiederholt, bis die erstellte Struktur der Lösungsstruktur entspricht. Jeder folgende Schritt hängt vom Schritt vor ihm ab. Die heuristische Suche lernt, welche Möglichkeiten zu verfolgen sind und welche Missachtung durch Messen der Messung des aktuellen Schritts an der Lösung ist. Daher werden einige Möglichkeiten niemals erzeugt, da sie als weniger wahrscheinlich die Lösung abschließen.

Eine heuristische Methode kann ihre Aufgabe durch die Verwendung von Suchbäumen erfüllen. Anstatt jedoch alle möglichen Lösungszweige zu generieren, wählt eine Heuristik Zweige aus, die eher Ergebnisse erzielen als andere Zweige. Es ist an jedem Entscheidungspunkt selektiv und wählt Zweige aus, die eher Lösungen produzieren.^[4]

Antiviren Software

Antiviren Software Verwendet oft heuristische Regeln, um Viren und andere Malware -Formen zu erkennen. Heuristische Scan sucht nach Code- und/oder Verhaltensmustern, die einer Klasse oder einer Familie von Viren gemeinsam sind, mit unterschiedlichen Regeln für verschiedene Viren. Wenn festgestellt wird, dass ein Datei- oder Ausführungsvorgang übereinstimmende Codemuster und/oder diese Aktivitäten ausgeführt wird, ist der Scanner, dass die Datei infiziert ist. Der fortschrittlichste Teil des heuristischen Scannens verhaltensbasiert ist, dass es gegen stark randomisierte Selbstmodifizierung/Mutation wirken kann (polymorph) Viren, die durch einfachere String -Scan -Methoden nicht leicht erkannt werden können. Das Heuristische Scannen hat das Potenzial, zukünftige Viren zu erkennen, ohne dass das Virus zuerst irgendwo anders erkannt, dem Virus -Scanner -Entwickler, analysiert, und ein Erkennungsaktualisierung für den Scanner, das den Benutzern des Scanners zur Verfügung gestellt wurde, übermittelt wird.

Tücken

Einige Heuristiken haben eine stark zugrunde liegende Theorie; Sie werden entweder auf Top-Down-Weise aus der Theorie abgeleitet oder basierend auf experimentellen oder realen Daten angewiesen. Andere sind gerecht Faustregeln Basierend auf der realen Beobachtung oder Erfahrung ohne einen Blick auf die Theorie. Letztere sind einer größeren Anzahl von Fallstricken ausgesetzt.

Wenn eine Heuristik in verschiedenen Kontexten wiederverwendet wird, weil es in einem Kontext "funktioniert", ohne mathematisch nachgewiesen wurde, dass sie einen bestimmten Anforderungen erfüllt, ist es möglich, dass der aktuelle Datensatz nicht unbedingt zukünftige Datensätze darstellt (( sehen: Überanpassung) und das hat sich als "Lösungen" als ähnlich wie Lärm heraus.

statistische Analyse Kann bei der Verwendung von Heuristiken durchgeführt werden, um die Wahrscheinlichkeit falscher Ergebnisse abzuschätzen. Eine Heuristik zur Lösung a verwenden Suchproblem oder ein RucksackproblemEs ist notwendig zu überprüfen, ob die Heuristik ist zulässig. Bei einer heuristischen Funktion ${\ displayStyle h (v_ {i}, v_ {g})}$ bestimmt, um den wahren optimalen Abstand zu approximieren ${\ displayStyle d^{\ star} (v_ {i}, v_ {g})}$ zum Torknoten ${\ displayStyle v_ {g}}$ in einer gerichteten Grafik ${\ displayStyle g}$ enthält ${\ displayStyle n}$ Gesamtknoten oder Scheitelpunkte beschriftet ${\ displayStyle v_ {0}, v_ {1}, \ cdots, v_ {n}}$ , "zulässig" bedeutet ungefähr, dass die heuristische die Kosten für das Ziel oder das formell unterschätzt ${\ displayStyle h (v_ {i}, v_ {g}) \ leq d^{\ star} (v_ {i}, v_ {g})}$ zum alle ${\ displayStyle (v_ {i}, v_ {g})}$ wo ${\ displayStyle {i, g} \ in [0,1, ..., n]}$ .

Wenn eine Heuristik nicht zulässig ist, kann es das Ziel nie finden, indem sie in einer Sackgasse der Grafik endet ${\ displayStyle g}$ oder indem Sie zwischen zwei Knoten hin und her überspringen ${\ displayStyle v_ {i}}$ und ${\ displayStyle v_ {j}}$ wo ${\ displayStyle {i, j} \ neq g}$ .

Etymologie

Das Wort "Heuristik" wurde im frühen 19. Jahrhundert verwendet. Es wird unregelmäßig aus dem gebildet griechisch Wort Heuriskein, bedeutet "zu finden".^[5]

Siehe auch

Algorithmus
Konstruktive Heuristik
Genetischen Algorithmus
Heuristik
Heuristische Routing
Heuristische Evaluation: Methode zur Identifizierung Benutzerfreundlichkeit Probleme in Benutzeroberflächen.
Metaheuristisch: Methoden zur Kontrolle und Abstimmung grundlegend heuristischer Algorithmen, normalerweise unter Verwendung von Gedächtnis und Lernen.
Mathieuristik: Optimierungsalgorithmen durch die Interoperation von Metaheuristik- und mathematischen Programmieren (MP).
Reaktive Suchoptimierung: Methoden online verwenden maschinelles Lernen Prinzipien für die Selbstabstimmung von Heuristiken.
Rekursion (Informatik)
Makro (Informatik)

Verweise

^ Pearl, Judäa (1984). Heuristik: Intelligente Suchstrategien zur Lösung von Computerproblemen. USA: Addison-Wesley Pub. Co., Inc., Reading, MA. p. 3. Osti 5127296.
^ Apter, Michael J. (1970). Die Computersimulation des Verhaltens. London: Hutchinson & Co. p. 83. ISBN 9781351021005.
^ Jon Louis Bentley (1982). Schreiben effizienter Programme. Prentice Hall. p.11.
^ Allen Newell und Herbert A. Simon (1976). "Informatik als empirische Anfrage: Symbole und Suche" (PDF). Comm. ACM. 19 (3): 113–126. doi:10.1145/360018.360022. S2CID 5581562.
^ "Definition von Heuristik auf Englisch". Oxford University Press. Archiviert Aus dem Original am 23. Oktober 2016. Abgerufen 22. Oktober 2016.

[1] Pearl, Judäa (1984). Heuristik: Intelligente Suchstrategien zur Lösung von Computerproblemen. USA: Addison-Wesley Pub. Co., Inc., Reading, MA. p. 3. Osti 5127296.

[2] Apter, Michael J. (1970). Die Computersimulation des Verhaltens. London: Hutchinson & Co. p. 83. ISBN 9781351021005.

[3] Jon Louis Bentley (1982). Schreiben effizienter Programme. Prentice Hall. p.11.

[4] Allen Newell und Herbert A. Simon (1976). "Informatik als empirische Anfrage: Symbole und Suche" (PDF). Comm. ACM. 19 (3): 113–126. doi:10.1145/360018.360022. S2CID 5581562.

[5] "Definition von Heuristik auf Englisch". Oxford University Press. Archiviert Aus dem Original am 23. Oktober 2016. Abgerufen 22. Oktober 2016.

[1]

[2]

[3]

[4]

[5]