AI - Beliebte Suchalgorithmen

Suchen ist die universelle Technik zur Problemlösung in der KI. Es gibt einige Einzelspieler-Spiele wie Kachelspiele, Sudoku, Kreuzworträtsel usw. Die Suchalgorithmen helfen Ihnen bei der Suche nach einer bestimmten Position in solchen Spielen.

Probleme bei der Pfadfindung einzelner Agenten

Die Spiele wie 3X3 Acht-Kacheln, 4X4 Fünfzehn-Kacheln und 5X5 Vierundzwanzig-Kacheln sind Herausforderungen bei der Suche nach Pfaden für einzelne Agenten. Sie bestehen aus einer Matrix von Kacheln mit einer leeren Kachel. Der Spieler muss die Plättchen anordnen, indem er ein Plättchen entweder vertikal oder horizontal in eine leere Stelle schiebt, um ein bestimmtes Ziel zu erreichen.

Die anderen Beispiele für Probleme bei der Pfadfindung einzelner Agenten sind Travelling Salesman Problem, Rubik's Cube und Theorem Proving.

Suche Terminologie

Problem Space- Es ist die Umgebung, in der die Suche stattfindet. (Eine Reihe von Zuständen und Operatoren zum Ändern dieser Zustände)
Problem Instance - Es ist Ausgangszustand + Zielzustand.
Problem Space Graph- Es repräsentiert den Problemzustand. Zustände werden durch Knoten und Operatoren durch Kanten angezeigt.
Depth of a problem - Länge eines kürzesten Pfades oder einer kürzesten Folge von Operatoren vom Anfangszustand zum Zielzustand.
Space Complexity - Die maximale Anzahl von Knoten, die im Speicher gespeichert sind.
Time Complexity - Die maximale Anzahl der erstellten Knoten.
Admissibility - Eine Eigenschaft eines Algorithmus, um immer eine optimale Lösung zu finden.
Branching Factor - Die durchschnittliche Anzahl der untergeordneten Knoten im Problemraumdiagramm.
Depth - Länge des kürzesten Weges vom Ausgangszustand zum Zielzustand.

Brute-Force-Suchstrategien

Sie sind am einfachsten, da sie kein domänenspezifisches Wissen benötigen. Sie funktionieren gut mit einer kleinen Anzahl möglicher Zustände.

Anforderungen -

Zustandsbeschreibung
Eine Reihe gültiger Operatoren
Ausgangszustand
Beschreibung des Zielstatus

Breitensuche

Es beginnt am Wurzelknoten, erkundet zuerst die benachbarten Knoten und bewegt sich zu den Nachbarn der nächsten Ebene. Es wird jeweils ein Baum generiert, bis die Lösung gefunden ist. Es kann unter Verwendung der FIFO-Warteschlangendatenstruktur implementiert werden. Diese Methode bietet den kürzesten Weg zur Lösung.

Wenn branching factor(durchschnittliche Anzahl von untergeordneten Knoten für einen bestimmten Knoten) = b und Tiefe = d, dann Anzahl von Knoten auf Ebene d = b ^d .

Die Gesamtzahl der im schlimmsten Fall erstellten Knoten beträgt b + b ² + b ³ +… + b ^d .

Disadvantage- Da jede Knotenebene für die Erstellung der nächsten gespeichert wird, belegt sie viel Speicherplatz. Der Platzbedarf zum Speichern von Knoten ist exponentiell.

Ihre Komplexität hängt von der Anzahl der Knoten ab. Es kann doppelte Knoten überprüfen.

Tiefensuche

Es wird in Rekursion mit der LIFO-Stack-Datenstruktur implementiert. Es wird derselbe Satz von Knoten wie bei der Breadth-First-Methode erstellt, nur in der unterschiedlichen Reihenfolge.

Da die Knoten auf dem einzelnen Pfad in jeder Iteration von Wurzel zu Blattknoten gespeichert werden, ist der Platzbedarf zum Speichern von Knoten linear. Mit dem Verzweigungsfaktor b und der Tiefe als m beträgt der Speicherplatz bm.

Disadvantage- Dieser Algorithmus wird möglicherweise nicht beendet und auf einem Pfad unendlich fortgesetzt. Die Lösung für dieses Problem besteht darin, eine Schnitttiefe zu wählen. Wenn der ideale Grenzwert d ist und der gewählte Grenzwert kleiner als d ist , kann dieser Algorithmus fehlschlagen. Wenn der gewählte Grenzwert mehr als d beträgt , erhöht sich die Ausführungszeit.

Ihre Komplexität hängt von der Anzahl der Pfade ab. Es können keine doppelten Knoten überprüft werden.

Bidirektionale Suche

Es sucht vom Anfangszustand vorwärts und vom Zielzustand rückwärts, bis sich beide treffen, um einen gemeinsamen Zustand zu identifizieren.

Der Pfad vom Anfangszustand wird mit dem umgekehrten Pfad vom Zielzustand verkettet. Jede Suche wird nur bis zur Hälfte des gesamten Pfades durchgeführt.

Einheitliche Kostensuche

Das Sortieren erfolgt in steigenden Kosten des Pfades zu einem Knoten. Es erweitert immer den Knoten mit den geringsten Kosten. Es ist identisch mit der Breitensuche, wenn jeder Übergang die gleichen Kosten verursacht.

Es werden Wege in aufsteigender Reihenfolge der Kosten untersucht.

Disadvantage- Es kann mehrere lange Pfade mit Kosten ≤ C * geben. Die Suche nach einheitlichen Kosten muss sie alle untersuchen.

Iterative vertiefende Tiefensuche

Es führt eine Tiefensuche bis Stufe 1 durch, beginnt von vorne, führt eine vollständige Tiefensuche bis Stufe 2 durch und fährt auf diese Weise fort, bis die Lösung gefunden ist.

Es wird niemals ein Knoten erstellt, bis alle unteren Knoten generiert wurden. Es wird nur ein Stapel von Knoten gespeichert. Der Algorithmus endet, wenn er in der Tiefe d eine Lösung findet . Die Anzahl der in der Tiefe d erzeugten Knoten ist b ^d und in der Tiefe d-1 ist b ^d-1.

Vergleich verschiedener Algorithmuskomplexitäten

Lassen Sie uns die Leistung von Algorithmen anhand verschiedener Kriterien sehen -

Kriterium	Breite zuerst	Tiefe zuerst	Bidirektional	Einheitliche Kosten	Interaktive Vertiefung
Zeit	b ^d	b ^m	b ^{d / 2}	b ^d	b ^d
Raum	b ^d	b ^m	b ^{d / 2}	b ^d	b ^d
Optimalität	Ja	Nein	Ja	Ja	Ja
Vollständigkeit	Ja	Nein	Ja	Ja	Ja

Informierte (heuristische) Suchstrategien

Um große Probleme mit einer großen Anzahl möglicher Zustände zu lösen, muss problemspezifisches Wissen hinzugefügt werden, um die Effizienz von Suchalgorithmen zu erhöhen.

Heuristische Auswertungsfunktionen

Sie berechnen die Kosten für einen optimalen Pfad zwischen zwei Zuständen. Eine heuristische Funktion für Spiele mit Gleitplättchen wird berechnet, indem die Anzahl der Züge, die jedes Plättchen aus seinem Zielzustand ausführt, gezählt und diese Anzahl von Zügen für alle Plättchen addiert wird.

Reine heuristische Suche

Es erweitert Knoten in der Reihenfolge ihrer heuristischen Werte. Es werden zwei Listen erstellt, eine geschlossene Liste für die bereits erweiterten Knoten und eine offene Liste für die erstellten, aber nicht erweiterten Knoten.

In jeder Iteration wird ein Knoten mit einem minimalen heuristischen Wert erweitert, alle untergeordneten Knoten werden erstellt und in die geschlossene Liste eingefügt. Dann wird die heuristische Funktion auf die untergeordneten Knoten angewendet und sie werden entsprechend ihrem heuristischen Wert in die offene Liste aufgenommen. Die kürzeren Pfade werden gespeichert und die längeren entsorgt.

Eine Suche

Es ist die bekannteste Form der Best First-Suche. Es vermeidet das Erweitern von Pfaden, die bereits teuer sind, erweitert jedoch zuerst die vielversprechendsten Pfade.

f (n) = g (n) + h (n), wobei

g (n) die Kosten (bisher), um den Knoten zu erreichen
h (n) geschätzte Kosten, um vom Knoten zum Ziel zu gelangen
f (n) geschätzte Gesamtkosten des Weges durch n zum Ziel. Es wird unter Verwendung der Prioritätswarteschlange durch Erhöhen von f (n) implementiert.

Gierige beste erste Suche

Es erweitert den Knoten, der dem Ziel am nächsten kommt. Es erweitert Knoten basierend auf f (n) = h (n). Es wird mithilfe der Prioritätswarteschlange implementiert.

Disadvantage- Es kann in Schleifen stecken bleiben. Es ist nicht optimal.

Lokale Suchalgorithmen

Sie gehen von einer prospektiven Lösung aus und wechseln dann zu einer benachbarten Lösung. Sie können eine gültige Lösung zurückgeben, auch wenn sie jederzeit vor ihrem Ende unterbrochen wird.

Bergsteigen Suche

Es ist ein iterativer Algorithmus, der mit einer beliebigen Lösung eines Problems beginnt und versucht, eine bessere Lösung zu finden, indem ein einzelnes Element der Lösung schrittweise geändert wird. Wenn die Änderung zu einer besseren Lösung führt, wird eine inkrementelle Änderung als neue Lösung verwendet. Dieser Vorgang wird wiederholt, bis keine weiteren Verbesserungen mehr vorliegen.

Funktion Hill-Climbing (Problem), gibt einen Zustand zurück, der ein lokales Maximum ist.

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

Disadvantage - Dieser Algorithmus ist weder vollständig noch optimal.

Lokale Strahlensuche

In diesem Algorithmus hält es k Anzahl von Zuständen zu einem bestimmten Zeitpunkt. Zu Beginn werden diese Zustände zufällig generiert. Die Nachfolger dieser k Zustände werden mit Hilfe der Zielfunktion berechnet. Wenn einer dieser Nachfolger der Maximalwert der Zielfunktion ist, stoppt der Algorithmus.

Andernfalls werden die Zustände (anfängliche k Zustände und k Anzahl der Nachfolger der Zustände = 2k) in einen Pool gestellt. Der Pool wird dann numerisch sortiert. Die höchsten k Zustände werden als neue Anfangszustände ausgewählt. Dieser Vorgang wird fortgesetzt, bis ein Maximalwert erreicht ist.

Die Funktion BeamSearch ( Problem, k ) gibt einen Lösungsstatus zurück.

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

Simuliertes Tempern

Beim Tempern wird ein Metall erhitzt und gekühlt, um seine innere Struktur zu ändern und seine physikalischen Eigenschaften zu ändern. Wenn das Metall abkühlt, wird seine neue Struktur erfasst und das Metall behält seine neu erhaltenen Eigenschaften. Beim simulierten Glühprozess wird die Temperatur variabel gehalten.

Wir stellen die Temperatur zunächst hoch ein und lassen sie dann im Verlauf des Algorithmus langsam abkühlen. Wenn die Temperatur hoch ist, kann der Algorithmus schlechtere Lösungen mit hoher Frequenz akzeptieren.

Start

Initialisiere k = 0; L = ganzzahlige Anzahl von Variablen;
Suchen Sie von i → j nach der Leistungsdifferenz Δ.
Wenn Δ <= 0, dann akzeptiere sonst wenn exp (-Δ / T (k))> zufällig (0,1) dann akzeptiere;
Wiederholen Sie die Schritte 1 und 2 für die Schritte L (k).
k = k + 1;

Wiederholen Sie die Schritte 1 bis 4, bis die Kriterien erfüllt sind.

Ende

Problem mit dem reisenden Verkäufer

Bei diesem Algorithmus besteht das Ziel darin, eine kostengünstige Tour zu finden, die von einer Stadt aus startet, alle Städte auf dem Weg genau einmal besucht und an derselben Startstadt endet.

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end