Algorithmen: Rechenkosten und folgende Heuristiken - Dummys

Oft finden Sie einen heuristischen Ansatz, einen, der auf Selbstentdeckung und ausreichend nützliche Ergebnisse (nicht unbedingt optimal, aber gut genug) sind die Methode, die Sie zur Lösung eines Problems benötigen. Wenn Sie den Algorithmus veranlassen, einige der für Sie erforderlichen Arbeiten auszuführen, sparen Sie Zeit und Aufwand, da Sie Algorithmen erstellen können, die Muster besser erkennen als Menschen.

Folglich ist Self-Discovery der Prozess, bei dem der Algorithmus Ihnen einen potenziell nützlichen Pfad zu einer Lösung zeigt (aber Sie müssen trotzdem auf menschliche Intuition und Verständnis zählen, um zu wissen, ob die Lösung die richtige ist). In den folgenden Abschnitten werden Techniken beschrieben, mit denen Sie die Kosten eines Algorithmus mithilfe von Heuristiken berechnen können, um die tatsächliche Nützlichkeit einer Lösung zu ermitteln.

Darstellen des Problems als Raum

Ein Problemraum ist eine Umgebung, in der eine Suche nach einer Lösung stattfindet. Eine Reihe von Zuständen und die Operatoren, die zum Ändern dieser Zustände verwendet werden, repräsentieren den Problemraum. Betrachten Sie zum Beispiel ein Tilespiel, das acht Kacheln in einem 3-x-3-Frame hat. Jede Kachel zeigt einen Teil eines Bildes, und die Kacheln beginnen in einer zufälligen Reihenfolge, so dass das Bild verwürfelt wird. Das Ziel ist, eine Kachel auf einmal zu bewegen, um alle Kacheln in der richtigen Reihenfolge zu platzieren und das Bild freizulegen.

Die Kombination aus dem Startzustand, den zufälligen Kacheln und dem Zielstatus - den Kacheln in einer bestimmten Reihenfolge - ist die Probleminstanz. Sie können das Puzzle grafisch darstellen, indem Sie ein Problemraumdiagramm verwenden. Jeder Knoten des Problemraumdiagramms zeigt einen Zustand (die acht Kacheln in einer bestimmten Position). Die Kanten stellen Operationen dar, wie zum Beispiel das Verschieben der Kachel Nummer Acht. Wenn Sie Kachel 8 nach oben bewegen, ändert sich das Bild - es bewegt sich in einen anderen Zustand.

Es ist nicht die einzige Überlegung, das Spiel zu gewinnen, indem man vom Start- in den Zielzustand wechselt. Um das Spiel effizient zu lösen, müssen Sie die Aufgabe mit der geringstmöglichen Anzahl von Zügen ausführen, dh mit der geringsten Anzahl von Operatoren. Die minimale Anzahl von Zügen, die zum Lösen des Puzzles verwendet werden, ist die Problemtiefe.

Sie müssen mehrere Faktoren berücksichtigen, wenn Sie ein Problem als Leerzeichen darstellen. Beispielsweise müssen Sie die maximale Anzahl von Knoten berücksichtigen, die in den Arbeitsspeicher passen, was die Komplexität des -Raums darstellt. Wenn Sie nicht alle Knoten gleichzeitig in den Speicher einpassen können, muss der Computer einige Knoten an anderen Orten speichern, z. B. auf der Festplatte, wodurch der Algorithmus erheblich verlangsamt werden kann.Um festzustellen, ob die Knoten in den Speicher passen, müssen Sie die Zeitkomplexität berücksichtigen,. Dies ist die maximale Anzahl der Knoten, die zur Lösung des Problems erstellt wurden. Darüber hinaus ist es wichtig, den Verzweigungsfaktor zu berücksichtigen. Dies ist die durchschnittliche Anzahl der Knoten, die im Problemraumgraphen erstellt wurden, um ein Problem zu lösen.

Zufällig gehen und durch Glück gesegnet werden

Das Lösen eines Suchproblems mit Brute-Force-Techniken ist möglich. Der Vorteil dieses Ansatzes ist, dass Sie kein domänenspezifisches Wissen benötigen, um einen dieser Algorithmen zu verwenden. Ein Brute-Force-Algorithmus tendiert dazu, den einfachsten Ansatz zur Lösung des Problems zu verwenden. Der Nachteil ist, dass ein Brute-Force-Ansatz nur für eine kleine Anzahl von Knoten funktioniert. Hier sind einige der gebräuchlichen Brute-Force-Suchalgorithmen:

Breitensuche: Diese Technik beginnt am Wurzelknoten, erforscht zuerst jeden der untergeordneten Knoten und bewegt sich dann erst auf die nächste Ebene. Es schreitet Stufe um Stufe fort, bis es eine Lösung findet. Der Nachteil dieses Algorithmus besteht darin, dass er jeden Knoten im Speicher ablegen muss, was bedeutet, dass er eine beträchtliche Menge an Speicher für eine große Anzahl von Knoten verwendet. Diese Technik kann nach doppelten Knoten suchen, was Zeit spart, und es wird immer eine Lösung gefunden.
Tiefensuche: Diese Technik beginnt am Wurzelknoten und untersucht eine Reihe von verbundenen untergeordneten Knoten, bis sie einen Blattknoten erreichen. Es schreitet Zweig für Zweig fort, bis es eine Lösung findet. Der Nachteil dieses Algorithmus ist, dass er nicht nach doppelten Knoten suchen kann, was bedeutet, dass er die gleichen Knotenpfade mehr als einmal durchlaufen kann. In der Tat kann dieser Algorithmus überhaupt keine Lösung finden, was bedeutet, dass Sie einen Abschneidepunkt definieren müssen, um den Algorithmus davon abzuhalten, unendlich zu suchen. Ein Vorteil dieses Ansatzes ist, dass es speichereffizient ist.
Bidirektionale Suche: Diese Technik durchsucht gleichzeitig den Wurzelknoten und den Zielknoten, bis sich die beiden Suchpfade in der Mitte treffen. Ein Vorteil dieses Ansatzes ist, dass es zeiteffizient ist, weil es die Lösung schneller findet als viele andere Brute-Force-Lösungen. Darüber hinaus nutzt es Speicher effizienter als andere Ansätze und findet immer eine Lösung. Der Hauptnachteil ist die Komplexität der Implementierung, was sich in einem längeren Entwicklungszyklus niederschlägt.

Verwenden einer Heuristik und einer Kostenfunktion

Für manche Leute klingt das Wort heuristisch einfach kompliziert. Es wäre genauso einfach zu sagen, dass der Algorithmus eine fundierte Schätzung macht und dann erneut versucht, wenn er fehlschlägt. Im Gegensatz zu Brute-Force-Methoden lernen heuristische Algorithmen. Sie verwenden auch Kostenfunktionen, um bessere Entscheidungen zu treffen. Folglich sind heuristische Algorithmen komplexer, aber sie haben einen entscheidenden Vorteil bei der Lösung komplexer Probleme. Wie bei Brute-Force-Algorithmen gibt es viele heuristische Algorithmen, die jeweils ihre eigenen Vor- und Nachteile sowie spezielle Anforderungen mit sich bringen. Die folgende Liste beschreibt einige der gebräuchlichsten heuristischen Algorithmen:

Reinheuristische Suche: Der Algorithmus erweitert die Knoten in der Reihenfolge ihrer Kosten.Es verwaltet zwei Listen. Die geschlossene Liste enthält die Knoten, die bereits untersucht wurden. Die offene Liste enthält die Knoten, die noch erforscht werden müssen. In jeder Iteration erweitert der Algorithmus den Knoten mit den niedrigstmöglichen Kosten. Alle untergeordneten Knoten werden in die geschlossene Liste aufgenommen und die Kosten für die einzelnen untergeordneten Knoten werden berechnet. Der Algorithmus sendet die untergeordneten Knoten mit niedrigen Kosten zurück zur offenen Liste und löscht die untergeordneten Knoten mit hohen Kosten. Folglich führt der Algorithmus eine intelligente, kostenbasierte Suche nach der Lösung durch.
A * search: Der Algorithmus verfolgt die Kosten von Knoten, wenn er sie mit der folgenden Gleichung untersucht: f (n) = g (n) + h (n), wobei
- n die Knotenidentifizierung ist.
- g (n) sind die Kosten für das Erreichen des Knotens.
- h (n) sind die geschätzten Kosten, um das Ziel vom Knoten zu erreichen.
- f (n) sind die geschätzten Kosten des Pfades von n zum Ziel.

Die Idee ist, zuerst die aussichtsreichsten Pfade zu suchen und teure Pfade zu vermeiden.