Suchalgorithmen sind einer der wichtigsten Bereiche der Künstlichen Intelligenz. In diesem Thema wird alles über die Suchalgorithmen in der KI erklärt.
Problemlöser:
In der Künstlichen Intelligenz sind Suchtechniken universelle Problemlösungsmethoden. Rationale Agenten oder Problemlösungsagenten In der KI werden diese Suchstrategien oder Algorithmen meist verwendet, um ein bestimmtes Problem zu lösen und das beste Ergebnis zu liefern. Problemlösungsagenten sind zielorientierte Agenten und verwenden eine atomare Darstellung. In diesem Thema lernen wir verschiedene Suchalgorithmen zur Problemlösung kennen.
Terminologien für Suchalgorithmen:
Eigenschaften von Suchalgorithmen:
Im Folgenden sind die vier wesentlichen Eigenschaften von Suchalgorithmen aufgeführt, um die Effizienz dieser Algorithmen zu vergleichen:
Vollständigkeit: Ein Suchalgorithmus wird als vollständig bezeichnet, wenn er garantiert, eine Lösung zurückzugeben, wenn für eine beliebige Zufallseingabe mindestens eine Lösung existiert.
Optimalität: Wenn eine für einen Algorithmus gefundene Lösung garantiert die beste Lösung (niedrigste Pfadkosten) unter allen anderen Lösungen ist, dann wird eine solche Lösung als optimale Lösung bezeichnet.
Zeitkomplexität: Zeitkomplexität ist ein Maß für die Zeit, die ein Algorithmus benötigt, um seine Aufgabe zu erledigen.
Raumkomplexität: Dabei handelt es sich um den maximalen Speicherplatz, der zu jedem Zeitpunkt der Suche benötigt wird, je nach Komplexität des Problems.
Arten von Suchalgorithmen
Basierend auf den Suchproblemen können wir die Suchalgorithmen in uninformierte (Blindsuche) Suchalgorithmen und informierte Suchalgorithmen (heuristische Suche) klassifizieren.
Uninformierte/blinde Suche:
Die uninformierte Suche enthält kein Domänenwissen wie Nähe, Ort des Ziels. Es funktioniert nach dem Brute-Force-Prinzip, da es nur Informationen darüber enthält, wie der Baum durchquert wird und wie Blatt- und Zielknoten identifiziert werden. Bei der uninformierten Suche wird ein Suchbaum ohne Informationen über den Suchraum wie Anfangszustandsoperatoren und Tests für das Ziel durchsucht. Sie wird daher auch als blinde Suche bezeichnet. Sie untersucht jeden Knoten des Baums, bis er den Zielknoten erreicht.
Es kann in fünf Haupttypen unterteilt werden:
- Breitensuche
- Einheitliche Kostensuche
- Tiefensuche
- Iterative vertiefende Tiefensuche
- Bidirektionale Suche
Informierte Suche
Informierte Suchalgorithmen nutzen Domänenwissen. Bei einer fundierten Suche stehen Probleminformationen zur Verfügung, die die Suche leiten können. Mit fundierten Suchstrategien kann eine Lösung effizienter gefunden werden als mit einer uninformierten Suchstrategie. Die informierte Suche wird auch als heuristische Suche bezeichnet.
Eine Heuristik ist ein Weg, der möglicherweise nicht immer die besten Lösungen garantiert, aber garantiert, dass in angemessener Zeit eine gute Lösung gefunden wird.
Eine fundierte Suche kann viele komplexe Probleme lösen, die auf andere Weise nicht gelöst werden könnten.
Ein Beispiel für informierte Suchalgorithmen ist das Problem des Handlungsreisenden.
- Gierige Suche
- Eine Suche