Empfohlen, 2019

Tipp Der Redaktion

Unterschied zwischen informierter und nichtinformierter Suche

Die Suche ist ein Prozess, bei dem Sie eine Abfolge von Schritten finden, die zur Lösung von Problemen erforderlich sind. Der vorherige Unterschied zwischen informierter und nicht infor- mierter Suche besteht darin, dass die informierte Suche Hinweise gibt, wo und wie die Lösung zu finden ist. Umgekehrt liefert die nicht informierte Suche außer der Spezifikation keine zusätzlichen Informationen zu dem Problem.

Die informierte Suche ist jedoch sowohl zwischen informierten als auch uninformierten Suchtechniken effizienter und kostengünstiger.

Vergleichstabelle

Basis zum VergleichInformierte SucheUninformierte Suche
Basic
Verwendet Wissen, um die Schritte zur Lösung zu finden.Kein Gebrauch von Wissen
Effizienz
Sehr effizient, da weniger Zeit und Kosten erforderlich sind.Effizienz ist vermittelnd
KostenNiedrigVergleichsweise hoch
PerformanceFindet die Lösung schnellerDie Geschwindigkeit ist langsamer als die informierte Suche
Algorithmen
Tiefensuche, Breitensuche und niedrigste KostenHeuristische Tiefensuche und Breitensuche und A * -Suche

Definition der informierten Suche

Die fundierte Suchmethode nutzt das problemspezifische Wissen, um einen Hinweis auf die Lösung des Problems zu geben. Diese Art der Suchstrategie verhindert tatsächlich, dass die Algorithmen über das Ziel und die Richtung zur Lösung stolpern. Eine informierte Suche kann hinsichtlich der Kosten vorteilhaft sein, wenn die Optimalität bei niedrigeren Suchkosten erreicht wird.

Um eine optimale Pfadkosten in einem Graphen zu suchen, indem eine fundierte Suchstrategie implementiert wird, werden die vielversprechendsten Knoten n in die Heuristikfunktion h (n) eingefügt. Dann gibt die Funktion eine nicht negative reelle Zahl zurück, bei der es sich um einen ungefähren Pfad handelt, der vom Knoten n zum Zielknoten berechnet wird.

Hier ist der wichtigste Teil der informierten Technik die heuristische Funktion, die es ermöglicht, dem Algorithmus die zusätzliche Kenntnis des Problems zu vermitteln. Dies hilft, den Weg zum Ziel durch die verschiedenen Nachbarknoten zu finden. Es gibt verschiedene Algorithmen, die auf der fundierten Suche basieren, wie heuristische Tiefensuche, heuristische Breitensuche, A * -Suche usw. Verstehen wir nun die heuristische Tiefensuche.

Heuristische Tiefensuche

Ähnlich wie bei der Tiefensuchmethode unterhalb der heuristischen Tiefensuche wird bei der ersten Suche ein Pfad ausgewählt, aber alle Pfade des ausgewählten Pfads werden durchlaufen, bevor ein anderer Pfad ausgewählt wird. Es wählt jedoch den besten Pfad vor Ort. In Fällen, in denen der kleinste heuristische Wert die Priorität für die Grenze ist, wird dies als beste erste Suche bezeichnet.

Ein weiterer fundierter Suchalgorithmus ist die A * -Suche, bei der das Konzept der kostengünstigsten ersten und der besten ersten Suche zusammengeführt wird. Diese Methode berücksichtigt sowohl Pfadkosten als auch heuristische Informationen beim Suchen und Auswählen des Pfads, der erweitert werden soll. Geschätzte Gesamtpfadkosten, die für jeden Pfad an der Grenze vom Start bis zum Zielknoten verwendet werden. Daher werden zwei Funktionen gleichzeitig verwendet - Kosten (p) sind die Kosten des erkannten Pfads und h (p) sind der geschätzte Wert der Pfadkosten vom Startknoten zum Zielknoten.

Definition der nicht informierten Suche

Die uninformierte Suche unterscheidet sich von der informierten Suche in der Art und Weise, dass sie nur die Problemdefinition bereitstellt, jedoch keinen weiteren Schritt zur Lösung des Problems. Das Hauptziel der nicht infor- mierten Suche besteht darin, zwischen dem Ziel- und dem Nicht-Zielzustand zu unterscheiden. Dabei wird das Ziel, auf das es sich im Pfad befindet, vollständig ignoriert, bis es das Ziel entdeckt und den Nachfolger meldet. Diese Strategie wird auch als blinde Suche bezeichnet.

Es gibt verschiedene Suchalgorithmen in dieser Kategorie, wie Tiefensuche, einheitliche Kostensuche, Breitensuche und so weiter. Lassen Sie uns nun das Konzept der nicht-informierten Suche mit Hilfe der Deep-First-Suche verstehen.

Tiefe erste Suche

Bei der eingehenden ersten Suche wird ein Last-in-First-Out-Stack zum Hinzufügen und Entfernen der Knoten verwendet. Es wird jeweils nur ein Knoten hinzugefügt oder entfernt, und das erste Element, das von der Grenze des Stapels entfernt wurde, wäre das letzte zum Stapel hinzugefügte Element. Durch die Verwendung von Stack in Frontier-Bereichen wird zunächst die Suche nach Pfaden eingehend vorangetrieben. Wenn ein kürzester und optimaler Pfad unter Verwendung der Tiefensuche gesucht wird, wird der von den benachbarten Knoten erzeugte Pfad zuerst vervollständigt, selbst wenn er nicht der gewünschte ist. Dann wird der alternative Pfad durch Rückverfolgung gesucht.

Mit anderen Worten, der Algorithmus wählt an jedem Knoten die erste Alternative und springt dann zu einer anderen Alternative zurück, bis er alle Pfade von der ersten Auswahl durchlaufen hat. Dies führt auch zu einem Problem, bei dem die Suche aufgrund von unendlichen Schleifen (Zyklen), die in der Grafik vorhanden sind, aufhört.

Hauptunterschiede zwischen informierter und nichtinformierter Suche

  1. Die frühere fundierte Suchtechnik verwendet Wissen, um die Lösung zu finden. Andererseits verwendet die letztere nichtinformierte Suchmethode kein Wissen. Einfacher ausgedrückt, werden keine weiteren Informationen über die Lösung bereitgestellt.
  2. Die Effizienz der informierten Suche ist besser als die nicht informierte Suche.
  3. Eine nicht informierte Suche kostet mehr Zeit und Kosten, da sie im Vergleich zu einer informierten Suche keine Ahnung von der Lösung hat.
  4. Tiefensuche, Breitensuche und niedrigste Kostensuche sind die Algorithmen, die unter die Kategorie der nicht informierten Suche fallen. Die fundierte Suche umfasst dagegen die Algorithmen wie heuristische Tiefensuche, heuristische Breitensuche und A * -Suche.

Fazit

Die informierte Suche gibt die Richtung für die Lösung vor, während bei der nicht informierten Suche keine Vorschläge zur Lösung gemacht werden. Dies macht die nicht informierte Suche länger, wenn der Algorithmus implementiert wird.

Top