logo

A* Sökalgoritm i artificiell intelligens

En introduktion till A* sökalgoritm i AI

A* (uttalas 'A-stjärna') är en kraftfull grafövergångs- och sökvägsalgoritm som ofta används inom artificiell intelligens och datavetenskap. Det används främst för att hitta den kortaste vägen mellan två noder i en graf, givet den uppskattade kostnaden för att ta sig från den aktuella noden till destinationsnoden. Den främsta fördelen med algoritmen är dess förmåga att ge en optimal väg genom att utforska grafen på ett mer informerat sätt jämfört med traditionella sökalgoritmer som Dijkstras algoritm.

Algoritm A* kombinerar fördelarna med två andra sökalgoritmer: Dijkstras algoritm och Greedy Best-First Search. Liksom Dijkstras algoritm säkerställer A* att sökvägen som hittas är så kort som möjligt men gör det mer effektivt genom att rikta sin sökning genom en heuristik som liknar Greedy Best-First Search. En heuristisk funktion, betecknad h(n), uppskattar kostnaden för att ta sig från en given nod n till destinationsnoden.

Huvudidén med A* är att utvärdera varje nod baserat på två parametrar:

java struktur
    g(n):den faktiska kostnaden för att komma från den initiala noden till nod n. Det representerar summan av kostnaderna för nod n utgående kanter.h(n):Heuristisk kostnad (även känd som 'uppskattningskostnad') från nod n till destinationsnod n. Denna problemspecifika heuristiska funktion måste vara acceptabel, vilket innebär att den aldrig överskattar den faktiska kostnaden för att uppnå målet. Utvärderingsfunktionen för nod n definieras som f(n) = g(n) h(n).

Algoritm A* väljer noderna som ska utforskas baserat på det lägsta värdet på f(n), och föredrar noderna med den lägsta uppskattade totala kostnaden för att nå målet. A*-algoritmen fungerar:

  1. Skapa en öppen lista över hittade men inte utforskade noder.
  2. Skapa en stängd lista för att hålla redan utforskade noder.
  3. Lägg till en startnod till den öppna listan med ett initialt värde på g
  4. Upprepa följande steg tills den öppna listan är tom eller du når målnoden:
    1. Hitta noden med det minsta f-värdet (d.v.s. noden med minor g(n) h(n)) i den öppna listan.
    2. Flytta den valda noden från den öppna listan till den stängda listan.
    3. Skapa alla giltiga avkomlingar till den valda noden.
    4. För varje efterföljare, beräkna dess g-värde som summan av den nuvarande nodens g-värde och kostnaden för att flytta från den aktuella noden till efterföljaren. Uppdatera spårarens g-värde när en bättre väg hittas.
    5. Om följaren inte finns i den öppna listan, lägg till den med det beräknade g-värdet och beräkna dess h-värde. Om den redan finns i den öppna listan, uppdatera dess g-värde om den nya sökvägen är bättre.
    6. Upprepa cykeln. Algoritm A* avslutas när målnoden nås eller när den öppna listan töms, vilket indikerar inga vägar från startnoden till målnoden. A*-sökalgoritmen används flitigt inom olika områden som robotik, videospel, nätverksrouting och designproblem eftersom den är effektiv och kan hitta optimala vägar i grafer eller nätverk.

Det är dock viktigt att välja en lämplig och acceptabel heuristisk funktion så att algoritmen fungerar korrekt och ger en optimal lösning.

Informerade sökalgoritmer

Historien om A*-sökalgoritmen i artificiell intelligens

Den utvecklades av Peter Hart, Nils Nilsson och Bertram Raphael vid Stanford Research Institute (numera SRI International) som en förlängning av Dijkstras algoritm och andra dåtida sökalgoritmer. A* publicerades första gången 1968 och fick snabbt ett erkännande för sin betydelse och effektivitet inom artificiell intelligens och datavetenskap. Här är en kort översikt över de mest kritiska milstolparna i historien för sökalgoritmen A*:

    Tidiga sökalgoritmer:Innan utvecklingen av A* fanns olika grafsökningsalgoritmer, inklusive Depth-First Search (DFS) och Breadth-First Search (BFS). Även om dessa algoritmer hjälpte till att hitta vägar, garanterade de inte optimalitet eller övervägde heuristik för att vägleda sökningenDijkstras algoritm:1959 introducerade den holländska datavetaren Edsger W. Dijkstra Dijkstras algoritm, som hittade den kortaste vägen i en viktad graf med icke-negativa kantvikter. Dijkstras algoritm var effektiv, men på grund av sin uttömmande karaktär hade den begränsningar när den användes på större grafer ellerInformerad sökning:Kunskapsbaserade sökalgoritmer (även känd som heuristisk sökning) har utvecklats för att införliva heuristisk information, såsom uppskattade kostnader, för att vägleda sökprocessen på ett effektivt sätt. Greedy Best-First Search var en sådan algoritm, men den garanterade inte optimalitet för att hitta den kortaste vägen.A* utveckling:1968 introducerade Peter Hart, Nils Nilsson och Bertram Raphael A*-algoritmen som en kombination av Dijkstras algoritm och Greedy Best-First Search. A* använde en heuristisk funktion för att uppskatta kostnaden från den aktuella noden till destinationsnoden genom att kombinera den med den faktiska kostnaden för att nå den aktuella noden. Detta gjorde det möjligt för A* att utforska grafen mer medvetet, undvika onödiga vägar och garantera en optimal lösning.Rättfärdighet och fullkomlighet:Författarna till A* visade att algoritmen är perfekt (finner alltid en lösning om en finns) och optimal (hittar den kortaste vägen) under vissa förutsättningar.Utbredd adoption och framsteg:A* blev snabbt populär i AI- och IT-gemenskaperna på grund av dess effektivitet och forskare och utvecklare har utökat och tillämpat A*-algoritmen på olika områden, inklusive robotik, videospel, teknik och nätverksrouting. Flera variationer och optimeringar av A*-algoritmen har föreslagits under åren, såsom Incremental A* och Parallel A*. Idag är A*-sökalgoritmen fortfarande en grundläggande och allmänt använd algoritm för artificiell intelligens och graftraversering. Det fortsätter att spela en viktig roll inom olika tillämpningar och forskningsområden. Dess inverkan på artificiell intelligens och dess bidrag till sökvägs- och optimeringsproblem har gjort det till en hörnstensalgoritm i forskning om intelligenta system.

Hur fungerar A*-sökalgoritmen i artificiell intelligens?

Sökalgoritmen A* (uttalas 'bokstav A') är en populär och allmänt använd grafövergångsalgoritm inom artificiell intelligens och datavetenskap. Den används för att hitta den kortaste vägen från en startnod till en destinationsnod i en viktad graf. A* är en välgrundad sökalgoritm som använder heuristik för att styra sökningen effektivt. Sökalgoritmen A* fungerar enligt följande:

Algoritmen börjar med en prioritetskö för att lagra de noder som ska utforskas. Den instansierar också två datastrukturer g(n): Kostnaden för den kortaste vägen hittills från startnoden till noden n och h(n), den uppskattade kostnaden (heuristisk) från nod n till destinationsnoden. Det är ofta en rimlig heuristik, vilket innebär att den aldrig överskattar den faktiska kostnaden för att uppnå ett mål. Placera den initiala noden i prioritetskön och ställ in dess g(n) till 0. Om prioritetskön inte är tom, Ta bort noden med lägst f(n) från prioritetskön. f(n) = g(n) h(n). Om den borttagna noden är destinationsnoden avslutas algoritmen och sökvägen hittas. Expandera annars noden och skapa dess grannar. För varje angränsande nod, beräkna dess initiala g(n)-värde, vilket är summan av g-värdet för den aktuella noden och kostnaden för att flytta från den aktuella noden till en angränsande nod. Om grannoden inte är i prioritetsordning eller det ursprungliga g(n)-värdet är mindre än dess nuvarande g-värde, uppdatera dess g-värde och ställ in dess föräldernod till den aktuella noden. Beräkna f(n)-värdet från grannoden och lägg till det i prioritetskön.

Om cykeln slutar utan att hitta destinationsnoden, har grafen ingen väg från början till slut. Nyckeln till effektiviteten hos A* är dess användning av en heuristisk funktion h(n) som ger en uppskattning av den återstående kostnaden för att nå målet för vilken nod som helst. Genom att kombinera den faktiska kostnaden g(n) med den heuristiska kostnaden h(n), utforskar algoritmen effektivt lovande vägar och prioriterar noder som sannolikt leder till den kortaste vägen. Det är viktigt att notera att effektiviteten hos A*-algoritmen är starkt beroende av valet av den heuristiska funktionen. Acceptabel heuristik säkerställer att algoritmen alltid hittar den kortaste vägen, men mer informerad och korrekt heuristik kan leda till snabbare konvergens och minskat sökutrymme.

Fördelar med A* Search Algorithm i artificiell intelligens

A*-sökalgoritmen erbjuder flera fördelar i scenarier för artificiell intelligens och problemlösning:

    Optimal lösning:A* säkerställer att hitta den optimala (kortaste) vägen från startnoden till destinationsnoden i den viktade grafen givet en acceptabel heuristisk funktion. Denna optimalitet är en avgörande fördel i många applikationer där det är viktigt att hitta den kortaste vägen.Fullständighet:Om det finns en lösning kommer A* att hitta den, förutsatt att grafen inte har en oändlig kostnad. Denna fullständighetsegenskap säkerställer att A* kan dra fördel av en lösning om den finns.Effektivitet:A* är effektiv om en acceptabel heuristisk funktion används. Heuristik styr sökningen till ett mål genom att fokusera på lovande vägar och undvika onödig utforskning, vilket gör A* mer effektiv än icke-medvetna sökalgoritmer som bredd-först-sökning eller djup-först-sökning.Mångsidighet:A* är allmänt tillämpbar på olika problemområden, inklusive wayfinding, ruttplanering, robotik, spelutveckling och mer. A* kan användas för att hitta optimala lösningar effektivt så länge som en meningsfull heuristik kan definieras.Optimerad sökning:A* upprätthåller en prioritetsordning för att välja noderna med det mindre f(n)-värdet (g(n) och h(n)) för expansion. Detta gör att den kan utforska lovande vägar först, vilket minskar sökutrymmet och leder till snabbare konvergens.Minneseffektivitet:Till skillnad från vissa andra sökalgoritmer, såsom bredd-först-sökning, lagrar A* endast ett begränsat antal noder i prioritetskön, vilket gör den minneseffektiv, särskilt för stora grafer.Avstämbar heuristik:A*s prestanda kan finjusteras genom att välja olika heuristiska funktioner. Mer utbildad heuristik kan leda till snabbare konvergens och mindre utökade noder.Omfattande undersökt:A* är en väletablerad algoritm med årtionden av forskning och praktiska tillämpningar. Många optimeringar och variationer har utvecklats, vilket gör det till ett pålitligt och välförstått felsökningsverktyg.Webbsökning:A* kan användas för webbaserad sökvägssökning, där algoritmen ständigt uppdaterar sökvägen enligt förändringar i miljön eller utseendet på nya. Det möjliggör beslutsfattande i realtid i dynamiska scenarier.

Nackdelar med A* Search Algorithm i artificiell intelligens

Även om sökalgoritmen A* (bokstav A) är en allmänt använd och kraftfull teknik för att lösa AI-sökvägs- och grafövergångsproblem, har den nackdelar och begränsningar. Här är några av de största nackdelarna med sökalgoritmen:

    Heuristisk noggrannhet:A*-algoritmens prestanda beror mycket på noggrannheten hos den heuristiska funktion som används för att uppskatta kostnaden från den aktuella noden till om heuristiken är oacceptabel (överskattar aldrig den faktiska kostnaden) eller inkonsekvent (tillfredsställer triangelolikheten), A* kanske inte hittar en optimal väg eller kan utforska fler noder än nödvändigt, vilket påverkar dess effektivitet och noggrannhet.Minnesanvändning:A* kräver att alla besökta noder hålls i minnet för att hålla reda på utforskade vägar. Minnesanvändning kan ibland bli ett betydande problem, särskilt när man har att göra med ett stort sökutrymme eller begränsade minnesresurser.Tidskomplexitet:Även om A* generellt sett är effektiv, kan dess tidskomplexitet vara ett problem för stora sökutrymmen eller grafer. I värsta fall kan A* ta exponentiellt längre tid att hitta den optimala vägen om heuristiken är olämplig för problemet.Flaskhals vid destinationen:I specifika scenarier måste A*-algoritmen utforska noder långt från destinationen innan den slutligen når destinationsregionen. Detta problemet uppstår när heuristiken behöver rikta sökningen mot målet tidigt effektivt.Kostnadsbindande:A* möter svårigheter när flera noder har samma f-värde (summan av den faktiska kostnaden och den heuristiska kostnaden). Den strategi som används kan påverka den upptäckta vägens optimalitet och effektivitet. Om det inte hanteras på rätt sätt kan det leda till att onödiga noder utforskas och sakta ner algoritmen.Komplexitet i dynamiska miljöer:I dynamiska miljöer där kostnaden för kanter eller noder kan ändras under sökningen kanske A* inte är lämplig eftersom den inte anpassar sig väl till sådana förändringar. Omformulering från grunden kan vara beräkningsmässigt dyrt, och D* (Dynamic A*) algoritmer designades för att lösa dettaPerfektion i oändligt utrymme:A* kanske inte hittar en lösning i oändligt tillståndsutrymme. I sådana fall kan den köras på obestämd tid och utforska ett ständigt ökande antal noder utan att hitta en lösning. Trots dessa brister är A* fortfarande en robust och allmänt använd algoritm eftersom den effektivt kan hitta optimala vägar i många praktiska situationer om den heuristiska funktionen är väldesignad och sökutrymmet är hanterbart. Olika varianter och varianter av A* har föreslagits för att lindra några av dess begränsningar.

Tillämpningar av A*-sökalgoritmen i artificiell intelligens

Sökalgoritmen A* (bokstav A) är en allmänt använd och robust sökalgoritm inom artificiell intelligens och datavetenskap. Dess effektivitet och optimalitet gör den lämplig för olika applikationer. Här är några typiska tillämpningar av A*-sökalgoritmen inom artificiell intelligens:

    Pathfinding i spel:A* används ofta i videospel för karaktärsrörelser, fiendens AI-navigering och för att hitta den kortaste vägen från en plats till en annan på spelkartan. Dess förmåga att hitta den optimala vägen baserat på kostnad och heuristik gör den idealisk för realtidsapplikationer som spel.Robotik och autonoma fordon:A* används inom robotteknik och autonom fordonsnavigering för att planera en optimal rutt för robotar att nå en destination, undvika hinder och ta hänsyn till terrängkostnader. Detta är avgörande för effektiv och säker rörelse i naturliga miljöer.Labyrintlösning:A* kan effektivt hitta den kortaste vägen genom en labyrint, vilket gör den värdefull i många labyrintlösningstillämpningar, som att lösa pussel eller navigera i komplexa strukturer.Ruttplanering och navigering:I GPS-system och kartapplikationer kan A* användas för att hitta den optimala rutten mellan två punkter på en karta, med hänsyn till faktorer som avstånd, trafikförhållanden och vägnätstopologi.Pussellösning:A* kan lösa olika diagrampussel, som glidpussel, Sudoku och 8-pusselproblemet. Resursallokering: I scenarier där resurser måste allokeras optimalt kan A* hjälpa till att hitta den mest effektiva allokeringsvägen, minimera kostnaden och maximera effektiviteten.Nätverksrouting:A* kan användas i datornätverk för att hitta den mest effektiva vägen för datapaket från en källa till en destinationsnod.Natural Language Processing (NLP):I vissa NLP-uppgifter kan A* generera sammanhängande och kontextuella svar genom att söka efter möjliga ordsekvenser baserat på deras sannolikhet och relevans.Vägplanering i robotik:A* kan användas för att planera vägen för en robot från en punkt till en annan, med hänsyn till olika begränsningar, som att undvika hinder eller minimera energiförbrukningen.Spel AI:A* används också för att fatta intelligenta beslut för icke-spelare karaktärer (NPCs), som att bestämma det bästa sättet att nå ett mål eller koordinera rörelser i ett lagbaserat spel.

Det här är bara några exempel på hur A*-sökalgoritmen hittar tillämpningar inom olika områden av artificiell intelligens. Dess flexibilitet, effektivitet och optimering gör det till ett värdefullt verktyg för många problem.

C-program för A* Search Algorithm in Artificiell Intelligens

 #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++-program för A* Search Algorithm in Artificiell Intelligens

 #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>

Förklaring:

    Strukturnod:Detta definierar en nodstruktur som representerar en rutnätscell. Den innehåller x- och y-koordinaterna för noden, kostnaden g från startnoden till den noden, det heuristiska värdet h (uppskattad kostnad från den noden till destinationsnoden) och en pekare till
  1. startnod för banan.
  2. Beräkna heuristik:Denna funktion beräknar en heuristik med hjälp av det euklidiska avståndet mellan en nod och målet AStarSearch: Denna funktion kör A*-sökalgoritmen. Den tar start- och destinationskoordinaterna, ett rutnät, och returnerar en vektor av par som representerar koordinaterna för den kortaste vägen från start till mål.Primär:Programmets huvudfunktion tar inmatningsrutnät, ursprung och målkoordinater från användaren. Den anropar sedan AStarSearch för att hitta den kortaste vägen och skriver ut resultatet. Strukturnod: Detta definierar en nodstruktur som representerar en rutnätscell. Den innehåller x- och y-koordinaterna för noden, kostnaden g från startnoden till den noden, det heuristiska värdet h (uppskattad kostnad från den noden till destinationsnoden) och en pekare till startnoden för vägen.Beräkna heuristik:Den här funktionen beräknar heuristik med hjälp av det euklidiska avståndet mellan en nod och målet AStarSearch: Denna funktion kör A*-sökalgoritmen. Den tar start- och destinationskoordinaterna, ett rutnät, och returnerar en vektor av par som representerar koordinaterna för den kortaste vägen från start till mål.

Provutgång

 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-program för A* Search Algorithm in Artificiell Intelligens

 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* Sökalgoritms komplexitet i artificiell intelligens

Sökalgoritmen A* (uttalas 'A-stjärna') är en populär och allmänt använd algoritm för sökning av grafer och sökvägar inom artificiell intelligens. Att hitta den kortaste vägen mellan två noder i en graf- eller rutnätsbaserad miljö är vanligtvis vanligt. Algoritmen kombinerar Dijkstras och giriga best-first-sökelement för att utforska sökutrymmet samtidigt som den säkerställer optimalitet effektivt. Flera faktorer bestämmer komplexiteten hos A*-sökalgoritmen. Grafstorlek (noder och kanter): En grafs antal noder och kanter påverkar i hög grad algoritmens komplexitet. Fler noder och kanter innebär fler möjliga alternativ att utforska, vilket kan öka exekveringstiden för algoritmen.

Heuristisk funktion: A* använder en heuristisk funktion (ofta betecknad h(n)) för att uppskatta kostnaden från den aktuella noden till destinationsnoden. Precisionen i denna heuristik påverkar i hög grad effektiviteten av A*-sökningen. En bra heuristik kan hjälpa sökningen till ett mål snabbare, medan en dålig heuristik kan leda till onödig sökning.

    Data struktur:A* upprätthåller två huvuddatastrukturer: en öppen lista (prioritetskö) och en stängd lista (eller besökt pool). Effektiviteten hos dessa datastrukturer, tillsammans med den valda implementeringen (t.ex. binära högar av prioriterade köer), påverkar algoritmens prestanda.Grenfaktor:Det genomsnittliga antalet följare för varje nod påverkar antalet noder som utökas under sökningen. En högre förgreningsfaktor kan leda till mer prospektering, vilket ökarOptimalitet och fullständighet:A* garanterar både optimalitet (att hitta den kortaste vägen) och fullständighet (att hitta en lösning som finns). Denna garanti kommer dock med en avvägning när det gäller beräkningskomplexitet, eftersom algoritmen måste utforska olika vägar för optimal prestanda. Beträffande tidskomplexitet påverkar den valda heuristiska funktionen A* i värsta fall. Med en accepterad heuristik (som aldrig överskattar den verkliga kostnaden för att nå målet), utökar A* de minsta noderna bland optimeringsalgoritmerna. Tidskomplexiteten i värsta fall för A * är exponentiell i det värsta fallet O(b ^ d), där 'b' är den effektiva förgreningsfaktorn (genomsnittligt antal följare per nod) och 'd' är den optimala

I praktiken presterar dock A* ofta betydligt bättre på grund av påverkan av en heuristisk funktion som hjälper till att styra algoritmen till lovande vägar. I fallet med en väldesignad heuristik är den effektiva förgreningsfaktorn mycket mindre, vilket leder till en snabbare inställning till den optimala lösningen.

sträng till itn