Alles über informierte Suche in der künstlichen Intelligenz

Die informierte Suche ist eine Art von Suchalgorithmus, der domänenspezifisches Wissen verwendet, um seine Suche durch einen Problemraum zu führen. Von Navigationssystemen über Spiele, Verarbeitung natürlicher Sprache bis hin zu Lieferkettenmanagement und einer fundierteren Suche in der künstlichen Intelligenz hat die Menge an Zeit und Rechenressourcen, die zur Lösung verschiedener Probleme erforderlich sind, erheblich reduziert.

Durch die Verwendung von domänenspezifischem Wissen zur Steuerung der Suche können informierte Suchalgorithmen schnell irrelevante oder weniger vielversprechende Pfade eliminieren, sodass sich die Suche auf die vielversprechendsten Optionen konzentrieren kann. Zu diesem Zweck verwenden diese Arten von Suchalgorithmen in der KI Heuristiken, um die Effizienz und Geschwindigkeit der Suche zu verbessern.

Melden Sie sich für den Machine Learning-Kurs an den besten Universitäten der Welt an. Erwerben Sie Master-, Executive PGP- oder Advanced Certificate-Programme, um Ihre Karriere zu beschleunigen.

In diesem Artikel werden das Konzept der informierten Suche in der künstlichen Intelligenz, ihre heuristischen Funktionen, Beispiele für Algorithmen und ihre Vor- und Nachteile erörtert.

Heuristik-Funktion

Einfach ausgedrückt ist eine heuristische Funktion ein Problemlösungsansatz, der eine Faustregel oder eine „beste Schätzung“ verwendet, um die Entfernung oder die Kosten zu einem Zielzustand in einem Suchproblem abzuschätzen. Die heuristische Funktion schätzt, wie weit der Zielzustand vom aktuellen Zustand entfernt ist, was verwendet werden kann, um einen Suchalgorithmus zum Ziel zu führen.

Informierte Suchalgorithmen nutzen diese Funktionen als zusätzliche Informationsquelle, um fundierte Entscheidungen über den einzuschlagenden Weg zu treffen. Aus diesem Grund sind heuristische Funktionen in informierten Suchalgorithmen wesentlich.

Beispiele aus der Praxis für heuristische Funktionen

Um heuristische Funktionen besser zu verstehen, hier einige Beispiele aus der Praxis:

• Beim klassischen Spiel „Sliding Tile Puzzle“ könnte eine einfache heuristische Funktion darin bestehen, die Anzahl der Kacheln zu zählen, die in der aktuellen Konfiguration im Vergleich zur Zielkonfiguration fehl am Platz sind. Je mehr Kacheln fehl am Platz sind, desto weiter ist der aktuelle Zustand vom Zielzustand entfernt.
• Beim Schach könnte eine heuristische Funktion darin bestehen, jeder Figur auf dem Brett basierend auf ihrer relativen Stärke und Position einen Wert zuzuweisen und die Summe dieser Werte zu verwenden, um den Vorteil oder Nachteil des aktuellen Spielers abzuschätzen. Diese heuristische Funktion kann verwendet werden, um einen Suchalgorithmus zu Bewegungen zu führen, die wahrscheinlich zu einer besseren Position führen.

Lassen Sie uns nun fortfahren und einige der am häufigsten verwendeten Beispiele für informierte Suchalgorithmen in der künstlichen Intelligenz verstehen.

Beispiele für informierte Suchalgorithmen

Zwei der am häufigsten verwendeten informierten Suchalgorithmen sind die Best-First-Suche und die A*-Suche. Lassen Sie uns diese beiden Algorithmen zusammen mit einigen Beispielen, Vorteilen, Nachteilen und ihrer Python-Implementierung verstehen:

1. Beste erste Suche

Die Best-First-Suche ist ein Suchalgorithmus, der gemäß einer heuristischen Funktion zuerst den vielversprechendsten Knoten erweitert. Der Algorithmus beginnt am Anfangsknoten und untersucht alle seine untergeordneten Knoten, wobei er den untergeordneten Knoten mit dem niedrigsten heuristischen Wert als den nächsten zu untersuchenden Knoten auswählt. Dieser Prozess wird fortgesetzt, bis der Zielknoten gefunden ist oder alle Knoten untersucht wurden.

Beste erste Suche – ein illustriertes Beispiel

Hier ist ein einfaches Beispiel, um die beste erste Suche zu veranschaulichen:

Angenommen, Sie versuchen, den kürzesten Weg von Ihrem Zuhause zu einem nahe gelegenen Lebensmittelgeschäft zu finden. Sie kennen die Entfernung zum Lebensmittelgeschäft von einigen Orten in der Nähe, aber Sie kennen nicht die genaue Route. Um dieses Problem mit der Best-First-Suche zu lösen, könnten Sie:

1. Beginnen Sie an Ihrem Wohnort und berechnen Sie den heuristischen Wert für jeden Standort in der Nähe basierend auf der Entfernung zum Lebensmittelgeschäft.
2. Wählen Sie den nahegelegenen Standort mit dem niedrigsten heuristischen Wert als nächsten zu untersuchenden Knoten aus.
3. Berechnen Sie den heuristischen Wert für jeden seiner untergeordneten Standorte von diesem nahe gelegenen Standort und wählen Sie den Knoten mit dem niedrigsten heuristischen Wert als nächsten zu untersuchenden Knoten aus.
4. Wiederholen Sie diesen Vorgang, bis Sie das Lebensmittelgeschäft erreichen.

Beste erste Suche – Python-Implementierung

So können Sie den besten ersten Suchalgorithmus in Python implementieren:

Heapq importieren

def best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# Initialisiere die Grenze und den erkundeten Satz

frontier = [(heuristic_func(start_state, goal_state), start_state)]

erkundet = gesetzt()

# Pfad und Kosten initialisieren

Pfad = {}

Kosten = {}

path[start_state] = Keine

Kosten[start_state] = 0

während Grenze:

# Holen Sie sich den Knoten mit dem niedrigsten heuristischen Wert von der Grenze

(h, aktueller_Status) = heapq.heappop(Grenze)

if aktueller_zustand == Zielzustand:

# gibt den Pfad zurück, wenn der Zielzustand erreicht ist

der Weg zurück

Erkundet.add (aktueller_Status)

# Mögliche Aktionen aus dem aktuellen Zustand generieren

für Aktion in actions_func(aktueller_Zustand):

next_state = Aktion (aktueller_Status)

# Berechnen Sie die Kosten des neuen Pfades

new_cost = cost[aktueller_Status] + cost_func(aktueller_Status, Aktion, nächster_Status)

if next_state nicht in explored und next_state nicht in [state for (h, state) in frontier]:

# füge den neuen Staat zur Grenze hinzu

heapq.heappush(Grenze, (heuristische_Funktion(nächster_Zustand, Ziel_Zustand), nächster_Zustand))

Pfad[nächster_Zustand] = aktueller_Zustand

kosten[nächster_zustand] = neue_kosten

# gebe None zurück, wenn der Zielzustand nicht erreichbar ist

Rückgabe Keine

Wie Sie sehen können, müssen Sie die folgenden Funktionen definieren:

• heuristic_func(current_state, goal_state): Diese Funktion nimmt den aktuellen Zustand und den Zielzustand als Eingaben und gibt eine Schätzung der Kosten zum Erreichen des Zielzustands aus dem aktuellen Zustand zurück.
• actions_func(current_state): Diese Funktion nimmt den aktuellen Status als Eingabe und gibt eine Liste von Aktionen zurück, die vom aktuellen Status aus ausgeführt werden können.
• cost_func(aktueller_Zustand, Aktion, nächster_Zustand): Diese Funktion nimmt den aktuellen Zustand, eine Aktion und den nächsten Zustand als Eingaben und gibt die Kosten für das Ergreifen von Maßnahmen vom aktuellen Zustand zum nächsten Zustand zurück.

Beispiel für die beste erste Suche

start_state = (0, 0)

Zielzustand = (4, 4)

def heuristic_func(aktueller_Zustand, Ziel_Zustand):

return abs(aktueller_Zustand[0] – Ziel_Zustand[0]) + abs(aktueller_Zustand[1] – Ziel_Zustand[1])

def actions_func(aktueller_Zustand):

Aktionen = []

wenn aktueller_zustand[0] > 0:

Aktionen.append (Lambda-Zustand: (Zustand[0]-1, Zustand[1]))

wenn aktueller_zustand[0] < 4:

Aktionen.append (Lambda-Zustand: (Zustand[0]+1, Zustand[1]))

wenn aktueller_zustand[1] > 0:

Aktionen.append (Lambda-Zustand: (Zustand[0], Zustand[1]-1))

wenn aktueller_zustand[1] < 4:

Aktionen.append (Lambda-Zustand: (Zustand[0], Zustand[1]+1))

Rückholaktionen

def cost_func(aktueller_Zustand, Aktion, nächster_Zustand):

Rückkehr 1

path = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

wenn Pfad:

# Den Pfad vom Startzustand zum Zielzustand konstruieren

aktueller_zustand = Zielzustand

while aktueller_zustand != start_zustand:

drucken (aktueller_zustand)

aktueller_zustand = pfad[aktueller_zustand]

print(start_state)

anders:

print("Zielzustand ist nicht erreichbar.")

Vorteile der besten ersten Suche

• Im Vergleich zur Breitensuche ist die zeitliche Komplexität der Best-First-Suche geringer.
• Die beste erste Suche erhält und implementiert die Vorteile sowohl des BFS- als auch des DFS-Algorithmus

Nachteile der Best First Search

• Es kann manchmal mehr Distanz zurücklegen als gedacht.
• Die Chancen, in einer Schleife stecken zu bleiben, sind sehr wahrscheinlich.

Eine Suche

Eine *-Suche ist ein Suchalgorithmus, der sowohl die Kosten zum Erreichen eines Knotens vom Startknoten als auch eine Schätzung der verbleibenden Kosten zum Erreichen des Zielknotens verwendet, um seine Suche zu leiten. Der Algorithmus beginnt am Anfangsknoten und untersucht alle seine untergeordneten Knoten, wobei er den untergeordneten Knoten mit den niedrigsten kombinierten Kosten und den geschätzten verbleibenden Kosten als nächsten zu untersuchenden Knoten auswählt. Dieser Prozess wird fortgesetzt, bis der Zielknoten gefunden ist oder alle Knoten untersucht wurden.

A*-Suche – ein illustriertes Beispiel

Betrachten wir noch einmal das vorherige Beispiel, in dem Sie versuchen, den kürzesten Weg von Ihrem Zuhause zu einem nahe gelegenen Lebensmittelgeschäft zu finden. Nun könnten Sie:

1. Beginnen Sie an Ihrem Wohnort und berechnen Sie die Gesamtkosten, um jeden Ort in der Nähe zu erreichen, als Summe der Entfernung von Ihrem Wohnort zu diesem Ort und den geschätzten verbleibenden Kosten, um das Lebensmittelgeschäft von diesem Ort aus zu erreichen.
2. Wählen Sie den nahe gelegenen Ort mit den niedrigsten Gesamtkosten als nächsten zu erkundenden Knoten aus.
3. Berechnen Sie von diesem nahe gelegenen Standort aus die Gesamtkosten für jeden seiner untergeordneten Standorte als Summe der Entfernung von diesem Standort zum untergeordneten Standort, den Kosten, um diesen Standort vom Startknoten aus zu erreichen, und den geschätzten verbleibenden Kosten, um das Lebensmittelgeschäft zu erreichen von diesem untergeordneten Standort. Wählen Sie den untergeordneten Standort mit den niedrigsten Gesamtkosten als nächsten zu erkundenden Knoten aus.
4. Wiederholen Sie diesen Vorgang, bis Sie das Lebensmittelgeschäft erreichen.

Wichtig dabei ist, dass A* Search ein optimaler Suchalgorithmus ist, der garantiert den kürzesten Weg zum Zielzustand findet. Es ist effizient bei Problemen mit einem großen Suchraum und wird häufig in Videospielen, Robotik und Routenplanung verwendet. Es erfordert jedoch eine gut definierte heuristische Funktion, um effektiv zu sein. Aus diesem Grund kann der Algorithmus speicherintensiv sein und bei komplexen Problemen mit vielen Knoten langsamer werden.

A*-Suche – Python-Implementierung

So können Sie den A*-Suchalgorithmus mithilfe der Python-Programmierung implementieren:

Heapq importieren

def astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# Initialisiere die Grenze und den erkundeten Satz

frontier = [(heuristic_func(start_state, goal_state), start_state)]

erkundet = gesetzt()

# Pfad und Kosten initialisieren

Pfad = {}

Kosten = {}

path[start_state] = Keine

Kosten[start_state] = 0

während Grenze:

# Holen Sie sich den Knoten mit dem niedrigsten f-Wert von der Grenze

(f, aktueller_Status) = heapq.heappop(Grenze)

if aktueller_zustand == Zielzustand:

# gibt den Pfad zurück, wenn der Zielzustand erreicht ist

der Weg zurück

Erkundet.add (aktueller_Status)

# Mögliche Aktionen aus dem aktuellen Zustand generieren

für Aktion in actions_func(aktueller_Zustand):

next_state = Aktion (aktueller_Status)

# Berechnen Sie die Kosten des neuen Pfades

new_cost = cost[aktueller_Status] + cost_func(aktueller_Status, Aktion, nächster_Status)

if next_state nicht in explored und next_state nicht in [state for (f, state) in frontier]:

# füge den neuen Staat zur Grenze hinzu

heapq.heappush(frontier, (new_cost + heuristic_func(next_state, goal_state), next_state))

Pfad[nächster_Zustand] = aktueller_Zustand

kosten[nächster_zustand] = neue_kosten

elif next_state in [state for (f, state) in frontier] und new_cost < cost[next_state]:

# Aktualisiere die Kosten des bestehenden Staates an der Grenze

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

frontier[index] = (new_cost + heuristic_func(next_state, goal_state), next_state)

Pfad[nächster_Zustand] = aktueller_Zustand

kosten[nächster_zustand] = neue_kosten

# gebe None zurück, wenn der Zielzustand nicht erreichbar ist

Rückgabe Keine

Top-Kurse für maschinelles Lernen und KI-Online-Kurse

Beispiel für A*-Suche

Hier ist ein Beispiel dafür, wie Sie die Funktion astar_search mit diesen Funktionen verwenden können:

start_state = (0, 0)

Zielzustand = (4, 4)

def heuristic_func(aktueller_Zustand, Ziel_Zustand):

return abs(aktueller_Zustand[0] – Ziel_Zustand[0]) + abs(aktueller_Zustand[1] – Ziel_Zustand[1])

def actions_func(aktueller_Zustand):

Aktionen = []

wenn aktueller_zustand[0] > 0:

Aktionen.append (Lambda-Zustand: (Zustand[0]-1, Zustand[1]))

wenn aktueller_zustand[0] < 4:

Aktionen.append (Lambda-Zustand: (Zustand[0]+1, Zustand[1]))

wenn aktueller_zustand[1] > 0:

Aktionen.append (Lambda-Zustand: (Zustand[0], Zustand[1]-1))

wenn aktueller_zustand[1] < 4:

Aktionen.append (Lambda-Zustand: (Zustand[0], Zustand[1]+1))

Rückholaktionen

def cost_func(aktueller_Zustand, Aktion, nächster_Zustand):

Rückkehr 1

path = astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

wenn Pfad:

# Den Pfad vom Startzustand zum Zielzustand konstruieren

aktueller_zustand = Zielzustand

while aktueller_zustand != start_zustand:

drucken (aktueller_zustand)

aktueller_zustand = pfad[aktueller_zustand]

print(start_state)

anders:

print("Zielzustand ist nicht erreichbar.")

Vorteile der A*-Suche

• Es ist eine der führenden heuristischen Techniken.
• Die A*-Suche kann genutzt werden, um komplexe Suchprobleme zu lösen

Trendige maschinelle Lernfähigkeiten

Nachteile der A*-Suche

• Die A*-Suchleistung hängt stark von der Genauigkeit heuristischer Algorithmen ab.
• Hat eine geringe Sucheffizienz.

Beliebte KI- und ML-Blogs und kostenlose Kurse

Wegbringen

Informierte Suchalgorithmen sind in der künstlichen Intelligenz unerlässlich, da sie es dem Computer ermöglichen, effizient und effektiv nach einem Zielzustand zu suchen. Diese Algorithmen verwenden heuristische Funktionen, um die Kosten jeder möglichen Bewegung abzuschätzen und den Suchprozess in Richtung des Zielzustands zu führen. Best First Search und A* Search sind Beispiele für informierte Suchalgorithmen, die in verschiedenen Bereichen weit verbreitet sind. Eine gut definierte heuristische Funktion ist jedoch entscheidend für den Erfolg informierter Suchalgorithmen.

Wenn Sie mehr über künstliche Intelligenz und maschinelles Lernen erfahren möchten, besuchen Sie das von der Liverpool John Moores University angebotene Programm „Masters in Machine Learning & Artificial Intelligence“ von upGrad . Dieses Programm behandelt verschiedene maschinelle Lern- und KI-Themen, einschließlich Algorithmen wie informierte Suche. Durch die Teilnahme an diesem Programm können Sie die Fähigkeiten und Kenntnisse erwerben, die Sie benötigen, um in einer Vielzahl von KI-bezogenen Karrieren erfolgreich zu sein.

Sie können sich auch unserekostenlosen Kurseansehen,die von upGrad in Management, Datenwissenschaft, maschinellem Lernen, digitalem Marketing und Technologie angeboten werden.Alle diese Kurse verfügen über erstklassige Lernressourcen, wöchentliche Live-Vorträge, Branchenaufgaben und ein Kursabschlusszertifikat – alles kostenlos!