logo

A* Suchalgorithmus in der künstlichen Intelligenz

Eine Einführung in den A*-Suchalgorithmus in der KI

A* (ausgesprochen „A-Star“) ist ein leistungsstarker Graph-Traversal- und Pathfinding-Algorithmus, der in der künstlichen Intelligenz und Informatik weit verbreitet ist. Es wird hauptsächlich verwendet, um den kürzesten Weg zwischen zwei Knoten in einem Diagramm zu finden, wenn man die geschätzten Kosten für den Weg vom aktuellen Knoten zum Zielknoten berücksichtigt. Der Hauptvorteil des Algorithmus besteht darin, dass er im Vergleich zu herkömmlichen Suchalgorithmen wie dem Dijkstra-Algorithmus einen optimalen Pfad bereitstellen kann, indem er den Graphen auf fundiertere Weise untersucht.

Algorithmus A* kombiniert die Vorteile von zwei anderen Suchalgorithmen: dem Dijkstra-Algorithmus und der Greedy Best-First Search. Wie der Dijkstra-Algorithmus stellt A* sicher, dass der gefundene Pfad so kurz wie möglich ist, tut dies jedoch effizienter, indem er seine Suche durch eine Heuristik ähnlich der Greedy Best-First Search leitet. Eine heuristische Funktion mit der Bezeichnung h(n) schätzt die Kosten für den Weg von einem beliebigen Knoten n zum Zielknoten.

Die Hauptidee von A* besteht darin, jeden Knoten anhand von zwei Parametern zu bewerten:

Java-String formatieren
    g(n):die tatsächlichen Kosten, um vom Anfangsknoten zum Knoten n zu gelangen. Es stellt die Summe der Kosten von Knoten n ausgehenden Kanten dar.h(n):Heuristische Kosten (auch als „Schätzkosten“ bekannt) vom Knoten n zum Zielknoten n. Diese problemspezifische heuristische Funktion muss akzeptabel sein, d. h. sie überschätzt niemals die tatsächlichen Kosten zur Zielerreichung. Die Bewertungsfunktion des Knotens n ist definiert als f(n) = g(n) h(n).

Algorithmus A* wählt die zu untersuchenden Knoten basierend auf dem niedrigsten Wert von f(n) aus und bevorzugt die Knoten mit den niedrigsten geschätzten Gesamtkosten zum Erreichen des Ziels. Der A*-Algorithmus funktioniert:

  1. Erstellen Sie eine offene Liste gefundener, aber nicht erkundeter Knoten.
  2. Erstellen Sie eine geschlossene Liste, die bereits erkundete Knoten enthält.
  3. Fügen Sie der offenen Liste einen Startknoten mit dem Anfangswert g hinzu
  4. Wiederholen Sie die folgenden Schritte, bis die geöffnete Liste leer ist oder Sie den Zielknoten erreichen:
    1. Suchen Sie den Knoten mit dem kleinsten f-Wert (d. h. den Knoten mit dem kleineren g(n) h(n)) in der offenen Liste.
    2. Verschieben Sie den ausgewählten Knoten von der offenen Liste in die geschlossene Liste.
    3. Erstellt alle gültigen Nachkommen des ausgewählten Knotens.
    4. Berechnen Sie für jeden Nachfolger seinen g-Wert als Summe aus dem g-Wert des aktuellen Knotens und den Kosten für den Umzug vom aktuellen Knoten zum Nachfolgerknoten. Aktualisieren Sie den G-Wert des Trackers, wenn ein besserer Pfad gefunden wird.
    5. Wenn der Follower nicht in der offenen Liste ist, fügen Sie ihn mit dem berechneten g-Wert hinzu und berechnen Sie seinen h-Wert. Wenn es sich bereits in der offenen Liste befindet, aktualisieren Sie seinen g-Wert, wenn der neue Pfad besser ist.
    6. Wiederholen Sie den Zyklus. Algorithmus A* endet, wenn der Zielknoten erreicht ist oder wenn die offene Liste leer ist, was darauf hinweist, dass keine Pfade vom Startknoten zum Zielknoten vorhanden sind. Der A*-Suchalgorithmus wird häufig in verschiedenen Bereichen wie Robotik, Videospielen, Netzwerkrouting und Designproblemen verwendet, da er effizient ist und optimale Pfade in Diagrammen oder Netzwerken finden kann.

Die Auswahl einer geeigneten und akzeptablen heuristischen Funktion ist jedoch von entscheidender Bedeutung, damit der Algorithmus korrekt funktioniert und eine optimale Lösung liefert.

Informierte Suchalgorithmen

Geschichte des A*-Suchalgorithmus in der künstlichen Intelligenz

Es wurde von Peter Hart, Nils Nilsson und Bertram Raphael am Stanford Research Institute (heute SRI International) als Erweiterung des Dijkstra-Algorithmus und anderer Suchalgorithmen der damaligen Zeit entwickelt. A* wurde erstmals 1968 veröffentlicht und erlangte schnell Anerkennung für seine Bedeutung und Wirksamkeit in den Bereichen künstliche Intelligenz und Informatik. Hier ein kurzer Überblick über die wichtigsten Meilensteine ​​in der Geschichte des Suchalgorithmus A*:

    Frühe Suchalgorithmen:Vor der Entwicklung von A* gab es verschiedene Graphsuchalgorithmen, darunter die Tiefensuche (DFS) und die Breitensuche (BFS). Obwohl diese Algorithmen dabei halfen, Pfade zu finden, garantierten sie weder die Optimalität noch berücksichtigten sie Heuristiken zur Steuerung der SucheDijkstras Algorithmus:1959 stellte der niederländische Informatiker Edsger W. Dijkstra den Dijkstra-Algorithmus vor, der den kürzesten Weg in einem gewichteten Diagramm mit nicht negativen Kantengewichten fand. Der Algorithmus von Dijkstra war effizient, aber aufgrund seiner erschöpfenden Natur hatte er Einschränkungen bei der Verwendung in größeren Diagrammen oderInformierte Suche:Wissensbasierte Suchalgorithmen (auch als heuristische Suche bekannt) wurden entwickelt, um heuristische Informationen, wie etwa geschätzte Kosten, einzubeziehen und den Suchprozess effizient zu steuern. Greedy Best-First Search war ein solcher Algorithmus, der jedoch nicht die optimale Suche nach dem kürzesten Weg garantierte.A*-Entwicklung:Im Jahr 1968 führten Peter Hart, Nils Nilsson und Bertram Raphael den A*-Algorithmus als Kombination aus Dijkstras Algorithmus und Greedy Best-First Search ein. A* verwendete eine heuristische Funktion, um die Kosten vom aktuellen Knoten zum Zielknoten zu schätzen, indem es diese mit den tatsächlichen Kosten für das Erreichen des aktuellen Knotens kombinierte. Dies ermöglichte es A*, den Graphen bewusster zu erkunden, unnötige Pfade zu vermeiden und eine optimale Lösung zu gewährleisten.Gerechtigkeit und Vollkommenheit:Die Autoren von A* haben gezeigt, dass der Algorithmus unter bestimmten Bedingungen perfekt (findet immer eine Lösung, falls vorhanden) und optimal (findet den kürzesten Weg) ist.Weit verbreitete Akzeptanz und Fortschritte:A* gewann aufgrund seiner Effizienz schnell an Popularität in der KI- und IT-Community. Forscher und Entwickler haben den A*-Algorithmus erweitert und auf verschiedene Bereiche angewendet, darunter Robotik, Videospiele, Ingenieurwesen und Netzwerkrouting. Im Laufe der Jahre wurden mehrere Variationen und Optimierungen des A*-Algorithmus vorgeschlagen, beispielsweise Inkremental A* und Parallel A*. Auch heute noch ist der A*-Suchalgorithmus ein grundlegender und weit verbreiteter Algorithmus in der künstlichen Intelligenz und beim Durchqueren von Graphen. Es spielt weiterhin eine wesentliche Rolle in verschiedenen Anwendungs- und Forschungsbereichen. Sein Einfluss auf die künstliche Intelligenz und sein Beitrag zu Wegfindungs- und Optimierungsproblemen haben ihn zu einem Eckpfeiler der intelligenten Systemforschung gemacht.

Wie funktioniert der A*-Suchalgorithmus in der künstlichen Intelligenz?

Der A*-Suchalgorithmus (ausgesprochen „Buchstabe A“) ist ein beliebter und weit verbreiteter Graph-Traversal-Algorithmus in der künstlichen Intelligenz und Informatik. Es wird verwendet, um den kürzesten Weg von einem Startknoten zu einem Zielknoten in einem gewichteten Diagramm zu finden. A* ist ein fundierter Suchalgorithmus, der Heuristiken verwendet, um die Suche effizient zu steuern. Der Suchalgorithmus A* funktioniert wie folgt:

Der Algorithmus beginnt mit einer Prioritätswarteschlange zum Speichern der zu erkundenden Knoten. Es instanziiert außerdem zwei Datenstrukturen g(n): Die Kosten des bisher kürzesten Pfades vom Startknoten zum Knoten n und h(n), die geschätzten Kosten (Heuristik) vom Knoten n zum Zielknoten. Dabei handelt es sich oft um eine vernünftige Heuristik, das heißt, sie überschätzt niemals die tatsächlichen Kosten für das Erreichen eines Ziels. Platzieren Sie den Anfangsknoten in der Prioritätswarteschlange und setzen Sie sein g(n) auf 0. Wenn die Prioritätswarteschlange nicht leer ist, entfernen Sie den Knoten mit dem niedrigsten f(n) aus der Prioritätswarteschlange. f(n) = g(n) h(n). Wenn der gelöschte Knoten der Zielknoten ist, endet der Algorithmus und der Pfad wird gefunden. Andernfalls erweitern Sie den Knoten und erstellen Sie seine Nachbarn. Berechnen Sie für jeden Nachbarknoten seinen anfänglichen g(n)-Wert, der die Summe aus dem g-Wert des aktuellen Knotens und den Kosten für den Umzug vom aktuellen Knoten zu einem Nachbarknoten ist. Wenn der Nachbarknoten nicht in der Prioritätsreihenfolge liegt oder der ursprüngliche g(n)-Wert kleiner als sein aktueller g-Wert ist, aktualisieren Sie seinen g-Wert und setzen Sie seinen übergeordneten Knoten auf den aktuellen Knoten. Berechnen Sie den f(n)-Wert vom Nachbarknoten und fügen Sie ihn der Prioritätswarteschlange hinzu.

Wenn der Zyklus endet, ohne dass der Zielknoten gefunden wird, hat der Graph keinen Pfad vom Anfang bis zum Ende. Der Schlüssel zur Effizienz von A* liegt in der Verwendung einer heuristischen Funktion h(n), die eine Schätzung der verbleibenden Kosten für das Erreichen des Ziels eines beliebigen Knotens liefert. Durch die Kombination der tatsächlichen Kosten g (n) mit den heuristischen Kosten h (n) erkundet der Algorithmus effektiv vielversprechende Pfade und priorisiert Knoten, die wahrscheinlich zum kürzesten Pfad führen. Es ist wichtig zu beachten, dass die Effizienz des A*-Algorithmus stark von der Wahl der heuristischen Funktion abhängt. Akzeptable Heuristiken stellen sicher, dass der Algorithmus immer den kürzesten Weg findet, aber fundiertere und genauere Heuristiken können zu einer schnelleren Konvergenz und einem geringeren Suchraum führen.

Vorteile des A*-Suchalgorithmus in der künstlichen Intelligenz

Der A*-Suchalgorithmus bietet in Szenarien mit künstlicher Intelligenz und Problemlösung mehrere Vorteile:

    Optimale Lösung:A* stellt sicher, dass im gewichteten Diagramm bei einer akzeptablen heuristischen Funktion der optimale (kürzeste) Pfad vom Startknoten zum Zielknoten gefunden wird. Diese Optimalität ist ein entscheidender Vorteil in vielen Anwendungen, bei denen es darauf ankommt, den kürzesten Weg zu finden.Vollständigkeit:Wenn eine Lösung existiert, wird A* sie finden, vorausgesetzt, der Graph hat keine unendlichen Kosten. Diese Vollständigkeitseigenschaft stellt sicher, dass A* von einer Lösung profitieren kann, wenn sie existiert.Effizienz:A* ist effizient, wenn eine effiziente und akzeptable heuristische Funktion verwendet wird. Heuristiken führen die Suche zu einem Ziel, indem sie sich auf vielversprechende Pfade konzentrieren und unnötige Erkundungen vermeiden. Dadurch ist A* effizienter als nicht bewusste Suchalgorithmen wie Breitensuche oder Tiefensuche.Vielseitigkeit:A* ist auf verschiedene Problembereiche anwendbar, darunter Wegfindung, Routenplanung, Robotik, Spieleentwicklung und mehr. A* kann verwendet werden, um optimale Lösungen effizient zu finden, solange eine sinnvolle Heuristik definiert werden kann.Optimierte Suche:A* behält eine Prioritätsreihenfolge bei, um die Knoten mit dem kleineren f(n)-Wert (g(n) und h(n)) für die Erweiterung auszuwählen. Dies ermöglicht es, zuerst vielversprechende Pfade zu erkunden, was den Suchraum reduziert und zu einer schnelleren Konvergenz führt.Speichereffizienz:Im Gegensatz zu einigen anderen Suchalgorithmen, beispielsweise der Breitensuche, speichert A* nur eine begrenzte Anzahl von Knoten in der Prioritätswarteschlange, was den Speicher effizient macht, insbesondere bei großen Diagrammen.Abstimmbare Heuristiken:Die Leistung von A* kann durch die Auswahl verschiedener heuristischer Funktionen optimiert werden. Eine fundiertere Heuristik kann zu einer schnelleren Konvergenz und weniger erweiterten Knoten führen.Umfangreich recherchiert:A* ist ein gut etablierter Algorithmus mit jahrzehntelanger Forschung und praktischen Anwendungen. Es wurden viele Optimierungen und Variationen entwickelt, die es zu einem zuverlässigen und gut verständlichen Tool zur Fehlerbehebung machen.Web-Suche:A* kann für die webbasierte Pfadsuche verwendet werden, bei der der Algorithmus den Pfad ständig entsprechend Änderungen in der Umgebung oder dem Auftreten neuer Pfade aktualisiert. Dies ermöglicht eine Echtzeit-Entscheidungsfindung in dynamischen Szenarien.

Nachteile des A*-Suchalgorithmus in der künstlichen Intelligenz

Obwohl der A*-Suchalgorithmus (Buchstabe A) eine weit verbreitete und leistungsstarke Technik zur Lösung von KI-Pfadfindungs- und Graph-Traversal-Problemen ist, weist er Nachteile und Einschränkungen auf. Hier sind einige der Hauptnachteile des Suchalgorithmus:

Ist Kat Timpf eine Anwältin?
    Heuristische Genauigkeit:Die Leistung des A*-Algorithmus hängt stark von der Genauigkeit der heuristischen Funktion ab, die zur Schätzung der Kosten vom aktuellen Knoten zum Möglicherweise findet es keinen optimalen Pfad oder erkundet möglicherweise mehr Knoten als nötig, was sich auf seine Effizienz und Genauigkeit auswirkt.Speichernutzung:A* erfordert, dass alle besuchten Knoten im Speicher gehalten werden, um den Überblick über die erkundeten Pfade zu behalten. Die Speichernutzung kann manchmal zu einem erheblichen Problem werden, insbesondere wenn es um einen großen Suchraum oder begrenzte Speicherressourcen geht.Zeitkomplexität:Obwohl A* im Allgemeinen effizient ist, kann seine zeitliche Komplexität bei großen Suchräumen oder Diagrammen ein Problem darstellen. Im schlimmsten Fall kann es exponentiell länger dauern, bis A* den optimalen Pfad findet, wenn die Heuristik für das Problem ungeeignet ist.Engpass am Zielort:In bestimmten Szenarien muss der A*-Algorithmus Knoten weit vom Ziel entfernt erkunden, bevor er schließlich die Zielregion erreicht. Dieses Problem tritt auf, wenn die Heuristik die Suche frühzeitig und effektiv auf das Ziel lenken muss.Kostenbindung:A* stößt auf Schwierigkeiten, wenn mehrere Knoten denselben f-Wert haben (die Summe der tatsächlichen Kosten und der heuristischen Kosten). Die verwendete Strategie kann die Optimalität und Effizienz des entdeckten Pfades beeinflussen. Bei unsachgemäßer Handhabung kann es dazu führen, dass unnötige Knoten untersucht werden und der Algorithmus verlangsamt wird.Komplexität in dynamischen Umgebungen:In dynamischen Umgebungen, in denen sich die Kosten von Kanten oder Knoten während der Suche ändern können, ist A* möglicherweise nicht geeignet, da es sich nicht gut an solche Änderungen anpasst. Eine Neuformulierung von Grund auf kann rechenintensiv sein, und D*-Algorithmen (Dynamic A*) wurden entwickelt, um dieses Problem zu lösenPerfektion im unendlichen Raum:A* findet möglicherweise keine Lösung im unendlichen Zustandsraum. In solchen Fällen kann es auf unbestimmte Zeit laufen und eine immer größere Anzahl von Knoten erkunden, ohne eine Lösung zu finden. Trotz dieser Mängel ist A* immer noch ein robuster und weit verbreiteter Algorithmus, da er in vielen praktischen Situationen effektiv optimale Pfade finden kann, wenn die heuristische Funktion gut konzipiert und der Suchraum überschaubar ist. Verschiedene Variationen und Varianten von A* wurden vorgeschlagen, um einige seiner Einschränkungen zu mildern.

Anwendungen des A*-Suchalgorithmus in der künstlichen Intelligenz

Der Suchalgorithmus A* (Buchstabe A) ist ein weit verbreiteter und robuster Pfadfindungsalgorithmus in der künstlichen Intelligenz und Informatik. Aufgrund seiner Effizienz und Optimalität eignet es sich für verschiedene Anwendungen. Hier sind einige typische Anwendungen des A*-Suchalgorithmus in der künstlichen Intelligenz:

    Wegfindung in Spielen:A* wird in Videospielen häufig für die Bewegung von Charakteren, die Navigation der feindlichen KI und die Suche nach dem kürzesten Weg von einem Ort zum anderen auf der Spielkarte verwendet. Seine Fähigkeit, den optimalen Pfad basierend auf Kosten und Heuristik zu finden, macht es ideal für Echtzeitanwendungen wie Spiele.Robotik und autonome Fahrzeuge:A* wird in der Robotik und autonomen Fahrzeugnavigation verwendet, um eine optimale Route für Roboter zu planen, um ein Ziel zu erreichen, wobei Hindernisse vermieden und Geländekosten berücksichtigt werden. Dies ist entscheidend für eine effiziente und sichere Fortbewegung in der Natur.Labyrinthlösung:A* kann effizient den kürzesten Weg durch ein Labyrinth finden, was es für viele Anwendungen zum Lösen von Labyrinthen wertvoll macht, etwa zum Lösen von Rätseln oder zum Navigieren in komplexen Strukturen.Routenplanung und Navigation:In GPS-Systemen und Kartenanwendungen kann A* verwendet werden, um die optimale Route zwischen zwei Punkten auf einer Karte zu finden und dabei Faktoren wie Entfernung, Verkehrsbedingungen und Straßennetztopologie zu berücksichtigen.Puzzle lösen:A* kann verschiedene Diagrammrätsel lösen, zum Beispiel Schieberätsel, Sudoku und das 8-Rätsel-Problem. Ressourcenzuweisung: In Szenarien, in denen Ressourcen optimal zugewiesen werden müssen, kann A* dabei helfen, den effizientesten Zuweisungspfad zu finden, wodurch Kosten minimiert und die Effizienz maximiert werden.Netzwerkrouting:A* kann in Computernetzwerken verwendet werden, um die effizienteste Route für Datenpakete von einem Quell- zu einem Zielknoten zu finden.Verarbeitung natürlicher Sprache (NLP):Bei einigen NLP-Aufgaben kann A* kohärente und kontextbezogene Antworten generieren, indem er nach möglichen Wortfolgen basierend auf ihrer Wahrscheinlichkeit und Relevanz sucht.Pfadplanung in der Robotik:A* kann verwendet werden, um den Weg eines Roboters von einem Punkt zum anderen zu planen und dabei verschiedene Einschränkungen zu berücksichtigen, z. B. das Vermeiden von Hindernissen oder die Minimierung des Energieverbrauchs.Spiel-KI:A* wird auch verwendet, um intelligente Entscheidungen für Nicht-Spieler-Charaktere (NPCs) zu treffen, beispielsweise um den besten Weg zum Erreichen eines Ziels zu bestimmen oder Bewegungen in einem Teamspiel zu koordinieren.

Dies sind nur einige Beispiele dafür, wie der A*-Suchalgorithmus in verschiedenen Bereichen der künstlichen Intelligenz Anwendung findet. Seine Flexibilität, Effizienz und Optimierung machen es zu einem wertvollen Werkzeug für viele Probleme.

C-Programm für A*-Suchalgorithmus in der künstlichen Intelligenz

 #include #include #define ROWS 5 #define COLS 5 // Define a structure for a grid cell typedef struct { int row, col; } Cell; // Define a structure for a node in the A* algorithm typedef struct { Cell position; int g, h, f; struct Node* parent; } Node; // Function to calculate the Manhattan distance between two cells int heuristic(Cell current, Cell goal) { return abs(current.row - goal.row) + abs(current.col - goal.col); } // Function to check if a cell is valid (within the grid and not an obstacle) int isValid(int row, int col, int grid[ROWS][COLS]) { return (row &gt;= 0) &amp;&amp; (row = 0) &amp;&amp; (col <cols) && (grid[row][col]="=" 0); } function to check if a cell is the goal int isgoal(cell cell, goal) { return (cell.row="=" goal.row) (cell.col="=" goal.col); perform a* search algorithm void astarsearch(int grid[rows][cols], start, todo: implement here main() grid[rows][cols]="{" {0, 1, 0, 0}, 0} }; start="{0," 0}; - cols 1}; astarsearch (grid, goal); 0; < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Data Structures:</td> A cell structure represents a grid cell with a row and a column. The node structure stores information about a cell during an A* lookup, including its location, cost (g, h, f), and a reference to its parent. </tr><tr><td>Heuristic function (heuristic):</td> This function calculates the Manhattan distance (also known as a &apos;cab ride&apos;) between two cells. It is used as a heuristic to estimate the cost from the current cell to the target cell. The Manhattan distance is the sum of the absolute differences between rows and columns. </tr><tr><td>Validation function (isValid):</td> This function checks if the given cell is valid, i.e., whether it is within the grid boundaries and is not an obstacle (indicated by a grid value of 1). </tr><tr><td>Goal check function (isGoal):</td> This function checks if the given cell is a target cell, i.e., does it match the coordinates of the target cell. </tr><tr><td>Search function* (AStarSearch):</td> This is the main function where the A* search algorithm should be applied. It takes a grid, a source cell, and a target cell as inputs. This activity aims to find the shortest path from the beginning to the end, avoiding the obstacles on the grid. The main function initializes a grid representing the environment, a start, and a target cell. It then calls the AStarSearch function with those inputs. </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> (0, 0) (1, 0) (2, 0) (3, 0) (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) </pre> <h3>C++ program for A* Search Algorithm in Artificial Intelligence</h3> <pre> #include #include #include using namespace std; struct Node { int x, y; // Coordinates of the node int g; // Cost from the start node to this node int h; // Heuristic value (estimated cost from this node to the goal node) Node* parent; // Parent node in the path Node (int x, int y): x(x), y(y), g(0), h(0), parent(nullptr) {} // Calculate the total cost (f = g + h) int f () const { return g + h; } }; // Heuristic function (Euclidean distance) int calculateHeuristic (int x, int y, int goals, int goal) { return static cast (sqrt (pow (goals - x, 2) + pow (goal - y, 2))); } // A* search algorithm vector<pair> AStarSearch (int startX, int startY, int goals, int goal, vector<vector>&amp; grid) { vector<pair> path; int rows = grid. size (); int cols = grid [0].size (); // Create the open and closed lists Priority queue <node*, vector, function> open List([](Node* lhs, Node* rhs) { return lhs-&gt;f() &gt; rhs-&gt;f(); }); vector<vector> closed List (rows, vector (cols, false)); // Push the start node to the open list openList.push(start Node); // Main A* search loop while (! Open-list. Empty ()) { // Get the node with the lowest f value from the open list Node* current = open-list. Top (); openest. pop (); // Check if the current node is the goal node if (current-&gt;x == goals &amp;&amp; current-&gt;y == goal) { // Reconstruct the path while (current! = nullptr) { path. push_back(make_pair(current-&gt;x, current-&gt;y)); current = current-&gt;parent; } Reverse (path. Begin(), path.end ()); break; } // Mark the current node as visited (in the closed list) Closed-list [current-&gt;x] [current-&gt;y] = true; // Generate successors (adjacent nodes) int dx [] = {1, 0, -1, 0}; int dy [] = {0, 1, 0, -1}; for (int i = 0; i x + dx [i]; int new Y = current-&gt;y + dy [i]; } break; } successor-&gt;parent = current; open List.push(successor); } // Cleanup memory for (Node* node: open List) { delete node; } return path; } int main () { int rows, cols; cout &lt;&gt; rows; cout &lt;&gt; cols; vector<vector> grid (rows, vector(cols)); cout &lt;&lt; &apos;Enter the grid (0 for empty, 1 for obstacle):&apos; &lt;&lt; endl; for (int i = 0; i &lt; rows; i++) { for (int j = 0; j&gt; grid[i][j]; } } int startX, startY, goalX, goalY; cout &lt;&gt; startX &gt;&gt; start; cout &lt;&gt; goals &gt;&gt; goals; vector<pair> path = AStarSearch (startX, startY, goal, goal, grid); if (! path. Empty ()) { cout &lt;&lt; &apos;Shortest path from (&apos; &lt;&lt; startX &lt;&lt; &apos;,&apos; &lt;&lt; start &lt;&lt; &apos;) to (&apos; &lt;&lt; goal &lt;&lt; &apos;,&apos; &lt;&lt; goal &lt;&lt; &apos;):&apos; &lt;&lt; endl; for (const auto&amp; point: path) { cout &lt;&lt; &apos;(&apos; &lt;&lt; point. first &lt;&lt; &apos;,&apos; &lt;&lt; point. second &lt;&lt; &apos;) &apos;; } cout &lt;&lt; endl; } else { cout &lt;&lt; &apos;No path found!&apos; &lt;&lt; endl; } return 0; } </pair></vector></vector></node*,></pair></vector></pair></pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Struct Node:</td> This defines a nodestructure that represents a grid cell. It contains the x and y coordinates of the node, the cost g from the starting node to that node, the heuristic value h (estimated cost from that node to the destination node), and a pointer to the <li>starting node of the path.</li> </tr><tr><td>Calculate heuristic:</td> This function calculates a heuristic using the Euclidean distance between a node and the target AStarSearch: This function runs the A* search algorithm. It takes the start and destination coordinates, a grid, and returns a vector of pairs representing the coordinates of the shortest path from start to finish. </tr><tr><td>Primary:</td> The program&apos;s main function takes input grids, origin, and target coordinates from the user. It then calls AStarSearch to find the shortest path and prints the result. Struct Node: This defines a node structure that represents a grid cell. It contains the x and y coordinates of the node, the cost g from the starting node to that node, the heuristic value h (estimated cost from that node to the destination node), and a pointer to the starting node of the path. </tr><tr><td>Calculate heuristic:</td> This function calculates heuristics using the Euclidean distance between a node and the target AStarSearch: This function runs the A* search algorithm. It takes the start and destination coordinates, a grid, and returns a vector of pairs representing the coordinates of the shortest path from start to finish. </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Enter the number of rows: 5 Enter the number of columns: 5 Enter the grid (0 for empty, 1 for obstacle): 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 Enter the start coordinates (x y): 0 0 Enter the goal coordinates (x y): 4 4 </pre> <h3>Java program for A* Search Algorithm in Artificial Intelligence</h3> <pre> import java. util.*; class Node { int x, y; // Coordinates of the node int g; // Cost from the start node to the current node int h; // Heuristic value (estimated cost from the current node to goal node) int f; // Total cost f = g + h Node parent; // Parent node in the path public Node (int x, int y) { this. g = x; this. f = y; this. Parent = null; } } public class AStarSearch { // Heuristic function (Manhattan distance) private static int heuristic (Node current, Node goal) { return Math. Abs (current.x - goal.x) + Math. Abs(current.y - goal.y); } // A* search algorithm public static List aStarSearch(int [][] grid, Node start, Node goal) { int rows = grid. Length; int cols = grid [0].length; // Add the start node to the open set opened.add(start); while (! openSet.isEmpty()) { // Get the node with the lowest f value from the open set Node current = openSet.poll(); // If the current node is the goal node, reconstruct the path and return it if (current == goal) { List path = new ArrayList(); while (current != null) { path.add(0, current); current = current.parent; } return path; } // Move the current node from the open set to the closed set closedSet.add(current); // Generate neighbors of the current node int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; for (int i = 0; i = 0 &amp;&amp; nx = 0 &amp;&amp; ny = neighbor.g) { // Skip this neighbor as it is already in the closed set with a lower or equal g value continue; } if (!openSet.contains(neighbor) || tentativeG <neighbor.g) { update the neighbor's values neighbor.g="tentativeG;" neighbor.h="heuristic(neighbor," goal); neighbor.f="neighbor.g" + neighbor.h; neighbor.parent="current;" if (!openset.contains(neighbor)) add neighbor to open set not already present openset.add(neighbor); } is empty and goal reached, there no path return null; public static void main(string[] args) int[][] grid="{" {0, 0, 0}, 1, 0} }; node start="new" node(0, 0); node(4, 4); list start, (path !="null)" system.out.println('path found:'); for (node : path) system.out.println('(' node.x ', ' node.y ')'); else system.out.println('no found.'); < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Node Class:</td> We start by defining a nodeclass representing each grid cell. Each node contains coordinates (x, y), an initial node cost (g), a heuristic value (h), a total cost (f = g h), and a reference to the parent node of the path. </tr><tr><td>Heuristicfunction:</td> The heuristic function calculates the Manhattan distance between a node and a destination The Manhattan distance is a heuristic used to estimate the cost from the current node to the destination node. </tr><tr><td>Search algorithm* function:</td> A Star Search is the primary implementation of the search algorithm A*. It takes a 2D grid, a start node, and a destination node as inputs and returns a list of nodes representing the path from the start to the destination node. </tr><tr><td>Priority Queue and Closed Set:</td> The algorithm uses a priority queue (open Set) to track thenodes to be explored. The queue is ordered by total cost f, so the node with the lowest f value is examined The algorithm also uses a set (closed set) to track the explored nodes. </tr><tr><td>The main loop of the algorithm:</td> The main loop of the A* algorithm repeats until there are no more nodes to explore in the open Set. In each iteration, the node f with the lowest total cost is removed from the opener, and its neighbors are created. </tr><tr><td>Creating neighbors:</td> The algorithm creates four neighbors (up, down, left, right) for each node and verifies that each neighbor is valid (within the network boundaries and not as an obstacle). If the neighbor is valid, it calculates the initial value g from the source node to that neighbor and the heuristic value h from that neighbor to the destination The total cost is then calculated as the sum of f, g, and h. </tr><tr><td>Node evaluation:</td> The algorithm checks whether the neighbor is already in the closed set and, if so, whether the initial cost g is greater than or equal to the existing cost of the neighbor If true, the neighbor is omitted. Otherwise, the neighbor values are updated and added to the open Set if it is not already there. </tr><tr><td>Pathreconstruction:</td> When the destination node is reached, the algorithm reconstructs the path from the start node to the destination node following the main links from the destination node back to the start node. The path is returned as a list of nodes </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Path found: (0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (4, 2) (4, 3) (4, 4) </pre> <h2>A* Search Algorithm Complexity in Artificial Intelligence</h2> <p>The A* (pronounced &apos;A-star&apos;) search algorithm is a popular and widely used graph traversal and path search algorithm in artificial intelligence. Finding the shortest path between two nodes in a graph or grid-based environment is usually common. The algorithm combines Dijkstra&apos;s and greedy best-first search elements to explore the search space while ensuring optimality efficiently. Several factors determine the complexity of the A* search algorithm. Graph size (nodes and edges): A graph&apos;s number of nodes and edges greatly affects the algorithm&apos;s complexity. More nodes and edges mean more possible options to explore, which can increase the execution time of the algorithm.</p> <p>Heuristic function: A* uses a heuristic function (often denoted h(n)) to estimate the cost from the current node to the destination node. The precision of this heuristic greatly affects the efficiency of the A* search. A good heuristic can help guide the search to a goal more quickly, while a bad heuristic can lead to unnecessary searching.</p> <ol class="points"> <tr><td>Data Structures:</td> A* maintains two maindata structures: an open list (priority queue) and a closed list (or visited pool). The efficiency of these data structures, along with the chosen implementation (e.g., priority queue binary heaps), affects the algorithm&apos;s performance. </tr><tr><td>Branch factor:</td> The average number of followers for each node affects the number of nodes expanded during the search. A higher branching factor can lead to more exploration, which increases </tr><tr><td>Optimality and completeness:</td> A* guarantees both optimality (finding the shortest path) and completeness (finding a solution that exists). However, this guarantee comes with a trade-off in terms of computational complexity, as the algorithm must explore different paths for optimal performance. Regarding time complexity, the chosen heuristic function affects A* in the worst case. With an accepted heuristic (which never overestimates the true cost of reaching the goal), A* expands the fewest nodes among the optimization algorithms. The worst-case time complexity of A * is exponential in the worst-case O(b ^ d), where &apos;b&apos; is the effective branching factor (average number of followers per node) and &apos;d&apos; is the optimal </tr></ol> <p>In practice, however, A* often performs significantly better due to the influence of a heuristic function that helps guide the algorithm to promising paths. In the case of a well-designed heuristic, the effective branching factor is much smaller, which leads to a faster approach to the optimal solution.</p> <hr></neighbor.g)></pre></cols)>

C++-Programm für A*-Suchalgorithmus in der künstlichen Intelligenz

 #include #include #include using namespace std; struct Node { int x, y; // Coordinates of the node int g; // Cost from the start node to this node int h; // Heuristic value (estimated cost from this node to the goal node) Node* parent; // Parent node in the path Node (int x, int y): x(x), y(y), g(0), h(0), parent(nullptr) {} // Calculate the total cost (f = g + h) int f () const { return g + h; } }; // Heuristic function (Euclidean distance) int calculateHeuristic (int x, int y, int goals, int goal) { return static cast (sqrt (pow (goals - x, 2) + pow (goal - y, 2))); } // A* search algorithm vector<pair> AStarSearch (int startX, int startY, int goals, int goal, vector<vector>&amp; grid) { vector<pair> path; int rows = grid. size (); int cols = grid [0].size (); // Create the open and closed lists Priority queue <node*, vector, function> open List([](Node* lhs, Node* rhs) { return lhs-&gt;f() &gt; rhs-&gt;f(); }); vector<vector> closed List (rows, vector (cols, false)); // Push the start node to the open list openList.push(start Node); // Main A* search loop while (! Open-list. Empty ()) { // Get the node with the lowest f value from the open list Node* current = open-list. Top (); openest. pop (); // Check if the current node is the goal node if (current-&gt;x == goals &amp;&amp; current-&gt;y == goal) { // Reconstruct the path while (current! = nullptr) { path. push_back(make_pair(current-&gt;x, current-&gt;y)); current = current-&gt;parent; } Reverse (path. Begin(), path.end ()); break; } // Mark the current node as visited (in the closed list) Closed-list [current-&gt;x] [current-&gt;y] = true; // Generate successors (adjacent nodes) int dx [] = {1, 0, -1, 0}; int dy [] = {0, 1, 0, -1}; for (int i = 0; i x + dx [i]; int new Y = current-&gt;y + dy [i]; } break; } successor-&gt;parent = current; open List.push(successor); } // Cleanup memory for (Node* node: open List) { delete node; } return path; } int main () { int rows, cols; cout &lt;&gt; rows; cout &lt;&gt; cols; vector<vector> grid (rows, vector(cols)); cout &lt;&lt; &apos;Enter the grid (0 for empty, 1 for obstacle):&apos; &lt;&lt; endl; for (int i = 0; i &lt; rows; i++) { for (int j = 0; j&gt; grid[i][j]; } } int startX, startY, goalX, goalY; cout &lt;&gt; startX &gt;&gt; start; cout &lt;&gt; goals &gt;&gt; goals; vector<pair> path = AStarSearch (startX, startY, goal, goal, grid); if (! path. Empty ()) { cout &lt;&lt; &apos;Shortest path from (&apos; &lt;&lt; startX &lt;&lt; &apos;,&apos; &lt;&lt; start &lt;&lt; &apos;) to (&apos; &lt;&lt; goal &lt;&lt; &apos;,&apos; &lt;&lt; goal &lt;&lt; &apos;):&apos; &lt;&lt; endl; for (const auto&amp; point: path) { cout &lt;&lt; &apos;(&apos; &lt;&lt; point. first &lt;&lt; &apos;,&apos; &lt;&lt; point. second &lt;&lt; &apos;) &apos;; } cout &lt;&lt; endl; } else { cout &lt;&lt; &apos;No path found!&apos; &lt;&lt; endl; } return 0; } </pair></vector></vector></node*,></pair></vector></pair>

Erläuterung:

    Strukturknoten:Dies definiert eine Knotenstruktur, die eine Gitterzelle darstellt. Es enthält die x- und y-Koordinaten des Knotens, die Kosten g vom Startknoten zu diesem Knoten, den heuristischen Wert h (geschätzte Kosten von diesem Knoten zum Zielknoten) und einen Zeiger auf den
  1. Startknoten des Pfades.
  2. Heuristik berechnen:Diese Funktion berechnet eine Heuristik anhand des euklidischen Abstands zwischen einem Knoten und dem Ziel. AStarSearch: Diese Funktion führt den A*-Suchalgorithmus aus. Es nimmt die Start- und Zielkoordinaten sowie ein Gitter und gibt einen Vektor von Paaren zurück, die die Koordinaten des kürzesten Weges vom Start bis zum Ziel darstellen.Primär:Die Hauptfunktion des Programms übernimmt Eingabegitter, Ursprung und Zielkoordinaten vom Benutzer. Anschließend ruft es AStarSearch auf, um den kürzesten Pfad zu finden, und gibt das Ergebnis aus. Strukturknoten: Dies definiert eine Knotenstruktur, die eine Gitterzelle darstellt. Es enthält die x- und y-Koordinaten des Knotens, die Kosten g vom Startknoten zu diesem Knoten, den heuristischen Wert h (geschätzte Kosten von diesem Knoten zum Zielknoten) und einen Zeiger auf den Startknoten des Pfads.Heuristik berechnen:Diese Funktion berechnet Heuristiken anhand des euklidischen Abstands zwischen einem Knoten und dem Ziel. AStarSearch: Diese Funktion führt den A*-Suchalgorithmus aus. Es nimmt die Start- und Zielkoordinaten sowie ein Gitter und gibt einen Vektor von Paaren zurück, die die Koordinaten des kürzesten Weges vom Start bis zum Ziel darstellen.

Beispielausgabe

 Enter the number of rows: 5 Enter the number of columns: 5 Enter the grid (0 for empty, 1 for obstacle): 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 Enter the start coordinates (x y): 0 0 Enter the goal coordinates (x y): 4 4 

Java-Programm für A*-Suchalgorithmus in der künstlichen Intelligenz

 import java. util.*; class Node { int x, y; // Coordinates of the node int g; // Cost from the start node to the current node int h; // Heuristic value (estimated cost from the current node to goal node) int f; // Total cost f = g + h Node parent; // Parent node in the path public Node (int x, int y) { this. g = x; this. f = y; this. Parent = null; } } public class AStarSearch { // Heuristic function (Manhattan distance) private static int heuristic (Node current, Node goal) { return Math. Abs (current.x - goal.x) + Math. Abs(current.y - goal.y); } // A* search algorithm public static List aStarSearch(int [][] grid, Node start, Node goal) { int rows = grid. Length; int cols = grid [0].length; // Add the start node to the open set opened.add(start); while (! openSet.isEmpty()) { // Get the node with the lowest f value from the open set Node current = openSet.poll(); // If the current node is the goal node, reconstruct the path and return it if (current == goal) { List path = new ArrayList(); while (current != null) { path.add(0, current); current = current.parent; } return path; } // Move the current node from the open set to the closed set closedSet.add(current); // Generate neighbors of the current node int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; for (int i = 0; i = 0 &amp;&amp; nx = 0 &amp;&amp; ny = neighbor.g) { // Skip this neighbor as it is already in the closed set with a lower or equal g value continue; } if (!openSet.contains(neighbor) || tentativeG <neighbor.g) { update the neighbor\'s values neighbor.g="tentativeG;" neighbor.h="heuristic(neighbor," goal); neighbor.f="neighbor.g" + neighbor.h; neighbor.parent="current;" if (!openset.contains(neighbor)) add neighbor to open set not already present openset.add(neighbor); } is empty and goal reached, there no path return null; public static void main(string[] args) int[][] grid="{" {0, 0, 0}, 1, 0} }; node start="new" node(0, 0); node(4, 4); list start, (path !="null)" system.out.println(\'path found:\'); for (node : path) system.out.println(\'(\' node.x \', \' node.y \')\'); else system.out.println(\'no found.\'); < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Node Class:</td> We start by defining a nodeclass representing each grid cell. Each node contains coordinates (x, y), an initial node cost (g), a heuristic value (h), a total cost (f = g h), and a reference to the parent node of the path. </tr><tr><td>Heuristicfunction:</td> The heuristic function calculates the Manhattan distance between a node and a destination The Manhattan distance is a heuristic used to estimate the cost from the current node to the destination node. </tr><tr><td>Search algorithm* function:</td> A Star Search is the primary implementation of the search algorithm A*. It takes a 2D grid, a start node, and a destination node as inputs and returns a list of nodes representing the path from the start to the destination node. </tr><tr><td>Priority Queue and Closed Set:</td> The algorithm uses a priority queue (open Set) to track thenodes to be explored. The queue is ordered by total cost f, so the node with the lowest f value is examined The algorithm also uses a set (closed set) to track the explored nodes. </tr><tr><td>The main loop of the algorithm:</td> The main loop of the A* algorithm repeats until there are no more nodes to explore in the open Set. In each iteration, the node f with the lowest total cost is removed from the opener, and its neighbors are created. </tr><tr><td>Creating neighbors:</td> The algorithm creates four neighbors (up, down, left, right) for each node and verifies that each neighbor is valid (within the network boundaries and not as an obstacle). If the neighbor is valid, it calculates the initial value g from the source node to that neighbor and the heuristic value h from that neighbor to the destination The total cost is then calculated as the sum of f, g, and h. </tr><tr><td>Node evaluation:</td> The algorithm checks whether the neighbor is already in the closed set and, if so, whether the initial cost g is greater than or equal to the existing cost of the neighbor If true, the neighbor is omitted. Otherwise, the neighbor values are updated and added to the open Set if it is not already there. </tr><tr><td>Pathreconstruction:</td> When the destination node is reached, the algorithm reconstructs the path from the start node to the destination node following the main links from the destination node back to the start node. The path is returned as a list of nodes </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Path found: (0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (4, 2) (4, 3) (4, 4) </pre> <h2>A* Search Algorithm Complexity in Artificial Intelligence</h2> <p>The A* (pronounced &apos;A-star&apos;) search algorithm is a popular and widely used graph traversal and path search algorithm in artificial intelligence. Finding the shortest path between two nodes in a graph or grid-based environment is usually common. The algorithm combines Dijkstra&apos;s and greedy best-first search elements to explore the search space while ensuring optimality efficiently. Several factors determine the complexity of the A* search algorithm. Graph size (nodes and edges): A graph&apos;s number of nodes and edges greatly affects the algorithm&apos;s complexity. More nodes and edges mean more possible options to explore, which can increase the execution time of the algorithm.</p> <p>Heuristic function: A* uses a heuristic function (often denoted h(n)) to estimate the cost from the current node to the destination node. The precision of this heuristic greatly affects the efficiency of the A* search. A good heuristic can help guide the search to a goal more quickly, while a bad heuristic can lead to unnecessary searching.</p> <ol class="points"> <tr><td>Data Structures:</td> A* maintains two maindata structures: an open list (priority queue) and a closed list (or visited pool). The efficiency of these data structures, along with the chosen implementation (e.g., priority queue binary heaps), affects the algorithm&apos;s performance. </tr><tr><td>Branch factor:</td> The average number of followers for each node affects the number of nodes expanded during the search. A higher branching factor can lead to more exploration, which increases </tr><tr><td>Optimality and completeness:</td> A* guarantees both optimality (finding the shortest path) and completeness (finding a solution that exists). However, this guarantee comes with a trade-off in terms of computational complexity, as the algorithm must explore different paths for optimal performance. Regarding time complexity, the chosen heuristic function affects A* in the worst case. With an accepted heuristic (which never overestimates the true cost of reaching the goal), A* expands the fewest nodes among the optimization algorithms. The worst-case time complexity of A * is exponential in the worst-case O(b ^ d), where &apos;b&apos; is the effective branching factor (average number of followers per node) and &apos;d&apos; is the optimal </tr></ol> <p>In practice, however, A* often performs significantly better due to the influence of a heuristic function that helps guide the algorithm to promising paths. In the case of a well-designed heuristic, the effective branching factor is much smaller, which leads to a faster approach to the optimal solution.</p> <hr></neighbor.g)>

A* Komplexität von Suchalgorithmen in der künstlichen Intelligenz

Der A*-Suchalgorithmus (ausgesprochen „A-Star“) ist ein beliebter und weit verbreiteter Graphtraversal- und Pfadsuchalgorithmus in der künstlichen Intelligenz. Das Finden des kürzesten Pfads zwischen zwei Knoten in einer diagramm- oder gitterbasierten Umgebung ist normalerweise üblich. Der Algorithmus kombiniert Dijkstra- und Greedy-Best-First-Suchelemente, um den Suchraum zu erkunden und gleichzeitig die Optimalität effizient sicherzustellen. Mehrere Faktoren bestimmen die Komplexität des A*-Suchalgorithmus. Diagrammgröße (Knoten und Kanten): Die Anzahl der Knoten und Kanten eines Diagramms hat großen Einfluss auf die Komplexität des Algorithmus. Mehr Knoten und Kanten bedeuten mehr mögliche Optionen zum Erkunden, was die Ausführungszeit des Algorithmus verlängern kann.

Heuristische Funktion: A* verwendet eine heuristische Funktion (oft als h(n) bezeichnet), um die Kosten vom aktuellen Knoten zum Zielknoten zu schätzen. Die Präzision dieser Heuristik hat großen Einfluss auf die Effizienz der A*-Suche. Eine gute Heuristik kann dazu beitragen, die Suche schneller zum Ziel zu führen, während eine schlechte Heuristik zu unnötiger Suche führen kann.

    Datenstrukturen:A* verwaltet zwei Hauptdatenstrukturen: eine offene Liste (Prioritätswarteschlange) und eine geschlossene Liste (oder besuchter Pool). Die Effizienz dieser Datenstrukturen wirkt sich zusammen mit der gewählten Implementierung (z. B. binäre Heaps mit Prioritätswarteschlange) auf die Leistung des Algorithmus aus.Zweigfaktor:Die durchschnittliche Anzahl der Follower für jeden Knoten beeinflusst die Anzahl der während der Suche erweiterten Knoten. Ein höherer Verzweigungsfaktor kann zu mehr Exploration führen, was zunimmtOptimalität und Vollständigkeit:A* garantiert sowohl Optimalität (Finden des kürzesten Weges) als auch Vollständigkeit (Finden einer existierenden Lösung). Diese Garantie geht jedoch mit einem Kompromiss hinsichtlich der Rechenkomplexität einher, da der Algorithmus für eine optimale Leistung verschiedene Pfade erkunden muss. Bezüglich der Zeitkomplexität wirkt sich die gewählte heuristische Funktion im schlimmsten Fall auf A* aus. Mit einer akzeptierten Heuristik (die die wahren Kosten für das Erreichen des Ziels niemals überschätzt) erweitert A* die wenigsten Knoten unter den Optimierungsalgorithmen. Die zeitliche Komplexität von A * im schlimmsten Fall ist im schlimmsten Fall O(b ^ d) exponentiell, wobei „b“ der effektive Verzweigungsfaktor (durchschnittliche Anzahl von Followern pro Knoten) und „d“ der optimale ist

In der Praxis schneidet A* aufgrund des Einflusses einer heuristischen Funktion, die den Algorithmus auf vielversprechende Pfade führt, jedoch oft deutlich besser ab. Bei einer gut konzipierten Heuristik ist der effektive Verzweigungsfaktor deutlich kleiner, was zu einer schnelleren Annäherung an die optimale Lösung führt.