En introduktion til A*-søgealgoritme i AI

A* (udtales 'A-stjerne') er en kraftfuld grafgennemgang og stifindende algoritme, der er meget udbredt inden for kunstig intelligens og datalogi. Det bruges hovedsageligt til at finde den korteste vej mellem to knudepunkter i en graf, givet de estimerede omkostninger ved at komme fra den aktuelle knude til destinationsknuden. Den største fordel ved algoritmen er dens evne til at give en optimal vej ved at udforske grafen på en mere informeret måde sammenlignet med traditionelle søgealgoritmer såsom Dijkstras algoritme.

Algoritme A* kombinerer fordelene ved to andre søgealgoritmer: Dijkstras algoritme og Greedy Best-First Search. Ligesom Dijkstras algoritme sikrer A*, at den fundne sti er så kort som muligt, men gør det mere effektivt ved at dirigere sin søgning gennem en heuristik svarende til Greedy Best-First Search. En heuristisk funktion, betegnet h(n), estimerer omkostningerne ved at komme fra en given node n til destinationsknuden.

Hovedideen med A* er at evaluere hver knude baseret på to parametre:

java webtjenester

g(n):de faktiske omkostninger for at komme fra den oprindelige node til node n. Det repræsenterer summen af ​​omkostningerne ved node n udgående kanter.h(n):Heuristiske omkostninger (også kendt som 'estimeringsomkostninger') fra node n til destinationsknude n. Denne problemspecifikke heuristiske funktion skal være acceptabel, hvilket betyder, at den aldrig overvurderer de faktiske omkostninger ved at nå målet. Evalueringsfunktionen af ​​node n er defineret som f(n) = g(n) h(n).

Algoritme A* udvælger de noder, der skal udforskes baseret på den laveste værdi af f(n), og foretrækker noderne med den laveste estimerede samlede omkostning for at nå målet. A*-algoritmen virker:

1. Opret en åben liste over fundne, men ikke udforskede noder.
2. Opret en lukket liste for at indeholde allerede udforskede noder.
3. Tilføj en startnode til den åbne liste med en startværdi på g
4. Gentag følgende trin, indtil den åbne liste er tom, eller du når målknuden:
   1. Find knudepunktet med den mindste f-værdi (dvs. knudepunktet med minor g(n) h(n)) i den åbne liste.
   2. Flyt den valgte node fra den åbne liste til den lukkede liste.
   3. Opret alle gyldige efterkommere af den valgte node.
   4. For hver efterfølger beregnes g-værdien som summen af ​​den aktuelle nodes g-værdi og omkostningerne ved at flytte fra den aktuelle node til efterfølgeren. Opdater trackerens g-værdi, når der er fundet en bedre sti.
   5. Hvis følgeren ikke er på den åbne liste, skal du tilføje den med den beregnede g-værdi og beregne dens h-værdi. Hvis den allerede er på den åbne liste, skal du opdatere dens g-værdi, hvis den nye sti er bedre.
   6. Gentag cyklussen. Algoritme A* afsluttes, når målknudepunktet nås, eller når den åbne liste tømmes, hvilket indikerer, at der ikke er nogen stier fra startknudepunktet til målknudepunktet. A*-søgealgoritmen er meget udbredt inden for forskellige områder såsom robotteknologi, videospil, netværksrouting og designproblemer, fordi den er effektiv og kan finde optimale stier i grafer eller netværk.

Valget af en passende og acceptabel heuristisk funktion er dog afgørende, så algoritmen fungerer korrekt og giver en optimal løsning.

Historien om A*-søgealgoritmen i kunstig intelligens

Den blev udviklet af Peter Hart, Nils Nilsson og Bertram Raphael ved Stanford Research Institute (nu SRI International) som en forlængelse af Dijkstras algoritme og andre søgealgoritmer fra tiden. A* blev første gang udgivet i 1968 og vandt hurtigt anerkendelse for sin betydning og effektivitet i kunstig intelligens og computervidenskabssamfund. Her er en kort oversigt over de mest kritiske milepæle i søgealgoritmen A*:s historie

Tidlige søgealgoritmer:Før udviklingen af ​​A* eksisterede forskellige grafsøgealgoritmer, herunder Depth-First Search (DFS) og Breadth-First Search (BFS). Selvom disse algoritmer hjalp med at finde stier, garanterede de ikke optimalitet eller overvejede heuristik til at guide søgningenDijkstras algoritme:I 1959 introducerede den hollandske datalog Edsger W. Dijkstra Dijkstras algoritme, som fandt den korteste vej i en vægtet graf med ikke-negative kantvægte. Dijkstras algoritme var effektiv, men på grund af dens udtømmende karakter havde den begrænsninger, når den blev brugt på større grafer ellerOplyst søgning:Vidensbaserede søgealgoritmer (også kendt som heuristisk søgning) er blevet udviklet til at inkorporere heuristisk information, såsom estimerede omkostninger, for at guide søgeprocessen effektivt. Greedy Best-First Search var en sådan algoritme, men den garanterede ikke optimalitet til at finde den korteste vej.A* udvikling:I 1968 introducerede Peter Hart, Nils Nilsson og Bertram Raphael A*-algoritmen som en kombination af Dijkstras algoritme og Greedy Best-First Search. A* brugte en heuristisk funktion til at estimere omkostningerne fra den aktuelle knude til destinationsknuden ved at kombinere den med de faktiske omkostninger ved at nå den aktuelle knude. Dette gjorde det muligt for A* at udforske grafen mere bevidst, undgå unødvendige stier og garantere en optimal løsning.Retfærdighed og fuldkommenhed:Forfatterne af A* viste, at algoritmen er perfekt (finder altid en løsning, hvis en findes) og optimal (finder den korteste vej) under visse forhold.Udbredt adoption og fremskridt:A* vandt hurtigt popularitet i AI- og IT-samfundene på grund af dens effektivitet, og forskere og udviklere har udvidet og anvendt A*-algoritmen til forskellige områder, herunder robotteknologi, videospil, teknik og netværksrouting. Adskillige variationer og optimeringer af A*-algoritmen er blevet foreslået gennem årene, såsom Incremental A* og Parallel A*. I dag er A*-søgealgoritmen stadig en grundlæggende og meget brugt algoritme inden for kunstig intelligens og grafgennemgang. Det spiller fortsat en væsentlig rolle i forskellige applikationer og forskningsområder. Dens indvirkning på kunstig intelligens og dens bidrag til pathfinding og optimeringsproblemer har gjort den til en hjørnestensalgoritme i intelligent systemforskning.

Hvordan fungerer A*-søgealgoritmen i kunstig intelligens?

A* (udtales 'bogstav A') søgealgoritmen er en populær og meget brugt grafgennemløbsalgoritme inden for kunstig intelligens og datalogi. Det bruges til at finde den korteste vej fra en startknude til en destinationsknude i en vægtet graf. A* er en informeret søgealgoritme, der bruger heuristik til at guide søgningen effektivt. Søgealgoritmen A* fungerer som følger:

Algoritmen starter med en prioritetskø til at gemme de noder, der skal udforskes. Den instansierer også to datastrukturer g(n): Omkostningerne for den korteste vej hidtil fra startknudepunktet til knudepunktet n og h(n), de estimerede omkostninger (heuristisk) fra knudepunkt n til destinationsknudepunktet. Det er ofte en rimelig heuristik, hvilket betyder, at den aldrig overvurderer de faktiske omkostninger ved at nå et mål. Sæt den indledende node i prioritetskøen og indstil dens g(n) til 0. Hvis prioritetskøen ikke er tom, skal du fjerne noden med den laveste f(n) fra prioritetskøen. f(n) = g(n) h(n). Hvis den slettede node er destinationsknuden, slutter algoritmen, og stien findes. Ellers skal du udvide noden og oprette dens naboer. For hver naboknude beregnes dens initiale g(n)-værdi, som er summen af ​​g-værdien af ​​den aktuelle knude og omkostningerne ved at flytte fra den aktuelle knude til en naboknude. Hvis naboknuden ikke er i prioriteret rækkefølge, eller den oprindelige g(n)-værdi er mindre end dens aktuelle g-værdi, skal du opdatere dens g-værdi og indstille dens overordnede knude til den aktuelle knude. Beregn f(n)-værdien fra naboknuden og tilføj den til prioritetskøen.

Hvis cyklussen slutter uden at finde destinationsknuden, har grafen ingen sti fra start til slut. Nøglen til effektiviteten af ​​A* er dens brug af en heuristisk funktion h(n), der giver et estimat af de resterende omkostninger ved at nå målet for enhver node. Ved at kombinere den faktiske omkostning g(n) med den heuristiske omkostning h(n), udforsker algoritmen effektivt lovende veje og prioriterer noder, der sandsynligvis vil føre til den korteste vej. Det er vigtigt at bemærke, at effektiviteten af ​​A*-algoritmen er meget afhængig af valget af den heuristiske funktion. Acceptable heuristik sikrer, at algoritmen altid finder den korteste vej, men mere informeret og præcis heuristik kan føre til hurtigere konvergens og reduceret søgeplads.

Fordele ved A*-søgealgoritme i kunstig intelligens

A*-søgealgoritmen tilbyder flere fordele i kunstig intelligens og problemløsningsscenarier:

Optimal løsning:A* sikrer at finde den optimale (korteste) vej fra startknudepunktet til destinationsknudepunktet i den vægtede graf givet en acceptabel heuristisk funktion. Denne optimalitet er en afgørende fordel i mange applikationer, hvor det er vigtigt at finde den korteste vej.Fuldstændighed:Hvis der findes en løsning, vil A* finde den, forudsat at grafen ikke har en uendelig omkostning. Denne fuldstændighedsegenskab sikrer, at A* kan drage fordel af en løsning, hvis den findes.Effektivitet:A* er effektiv, hvis der anvendes en acceptabel heuristisk funktion. Heuristik guider søgningen til et mål ved at fokusere på lovende stier og undgå unødvendig udforskning, hvilket gør A* mere effektiv end ikke-bevidste søgealgoritmer såsom bredde-først-søgning eller dybde-først-søgning.Alsidighed:A* er bredt anvendelig til forskellige problemområder, herunder wayfinding, ruteplanlægning, robotteknologi, spiludvikling og mere. A* kan bruges til at finde optimale løsninger effektivt, så længe der kan defineres en meningsfuld heuristik.Optimeret søgning:A* bevarer en prioriteret rækkefølge for at vælge knudepunkterne med den mindre f(n)-værdi (g(n) og h(n)) til udvidelse. Dette giver den mulighed for at udforske lovende stier først, hvilket reducerer søgerummet og fører til hurtigere konvergens.Hukommelseseffektivitet:I modsætning til nogle andre søgealgoritmer, såsom bredde-først-søgning, gemmer A* kun et begrænset antal noder i prioritetskøen, hvilket gør den hukommelseseffektiv, især for store grafer.Afstembar heuristik:A*'s ydeevne kan finjusteres ved at vælge forskellige heuristiske funktioner. Mere uddannet heuristik kan føre til hurtigere konvergens og mindre udvidede noder.Omfattende undersøgt:A* er en veletableret algoritme med årtiers forskning og praktiske anvendelser. Der er udviklet mange optimeringer og variationer, hvilket gør det til et pålideligt og velforstået fejlfindingsværktøj.Websøgning:A* kan bruges til webbaseret stisøgning, hvor algoritmen konstant opdaterer stien i henhold til ændringer i miljøet eller udseendet af nye. Det muliggør beslutningstagning i realtid i dynamiske scenarier.

Ulemper ved A*-søgealgoritme i kunstig intelligens

Selvom A* (bogstav A) søgealgoritmen er en meget brugt og kraftfuld teknik til at løse AI pathfinding og grafgennemgang problemer, har den ulemper og begrænsninger. Her er nogle af de største ulemper ved søgealgoritmen:

Heuristisk nøjagtighed:Ydeevnen af ​​A*-algoritmen afhænger i høj grad af nøjagtigheden af ​​den heuristiske funktion, der bruges til at estimere omkostningerne fra den aktuelle node til Hvis heuristikken er uacceptabel (overvurderer aldrig de faktiske omkostninger) eller inkonsistent (opfylder trekantens ulighed), A* finder muligvis ikke en optimal sti eller kan udforske flere noder end nødvendigt, hvilket påvirker dens effektivitet og nøjagtighed.Hukommelsesbrug:A* kræver, at alle besøgte noder opbevares i hukommelsen for at holde styr på udforskede stier. Hukommelsesbrug kan nogle gange blive et betydeligt problem, især når man har at gøre med en rigelig søgeplads eller begrænsede hukommelsesressourcer.Tidskompleksitet:Selvom A* generelt er effektiv, kan dens tidskompleksitet være et problem for store søgerum eller grafer. I værste fald kan A* tage eksponentielt længere tid at finde den optimale vej, hvis heuristikken er upassende for problemet.Flaskehals på destinationen:I specifikke scenarier skal A*-algoritmen udforske noder langt fra destinationen, før den endelig når destinationsregionen. Dette er problemet, når heuristikken skal rette søgningen mod målet tidligt effektivt.Omkostningsbinding:A* står over for vanskeligheder, når flere noder har den samme f-værdi (summen af ​​de faktiske omkostninger og de heuristiske omkostninger). Den anvendte strategi kan påvirke optimaliteten og effektiviteten af ​​den opdagede vej. Hvis det ikke håndteres korrekt, kan det føre til, at unødvendige noder bliver udforsket og bremse algoritmen.Kompleksitet i dynamiske miljøer:I dynamiske miljøer, hvor omkostningerne ved kanter eller noder kan ændre sig under søgningen, er A* muligvis ikke egnet, fordi den ikke tilpasser sig godt til sådanne ændringer. Reformulering fra bunden kan være beregningsmæssigt dyrt, og D* (Dynamic A*) algoritmer blev designet til at løse dettePerfektion i uendeligt rum:A* finder muligvis ikke en løsning i uendeligt rum. I sådanne tilfælde kan den køre på ubestemt tid og udforske et stadigt stigende antal noder uden at finde en løsning. På trods af disse mangler er A* stadig en robust og meget brugt algoritme, fordi den effektivt kan finde optimale veje i mange praktiske situationer, hvis den heuristiske funktion er veldesignet og søgerummet er overskueligt. Forskellige variationer og varianter af A* er blevet foreslået for at lindre nogle af dets begrænsninger.

Anvendelser af A*-søgealgoritmen i kunstig intelligens

Søgealgoritmen A* (bogstav A) er en meget brugt og robust stifindingsalgoritme inden for kunstig intelligens og datalogi. Dens effektivitet og optimalitet gør den velegnet til forskellige applikationer. Her er nogle typiske anvendelser af A*-søgealgoritmen i kunstig intelligens:

python eller

Pathfinding i spil:A* bruges ofte i videospil til karakterbevægelser, fjendens AI-navigation og til at finde den korteste vej fra et sted til et andet på spilkortet. Dens evne til at finde den optimale vej baseret på omkostninger og heuristik gør den ideel til realtidsapplikationer såsom spil.Robotteknologi og autonome køretøjer:A* bruges i robotteknologi og autonom køretøjsnavigation til at planlægge en optimal rute for robotter til at nå en destination, undgå forhindringer og tage terrænomkostninger i betragtning. Dette er afgørende for effektiv og sikker bevægelse i naturlige miljøer.Labyrint løsning:A* kan effektivt finde den korteste vej gennem en labyrint, hvilket gør den værdifuld i mange labyrintløsningsapplikationer, såsom at løse gåder eller navigere i komplekse strukturer.Ruteplanlægning og navigation:I GPS-systemer og kortapplikationer kan A* bruges til at finde den optimale rute mellem to punkter på et kort under hensyntagen til faktorer som afstand, trafikforhold og vejnetstopologi.Løsning af gåder:A* kan løse forskellige diagramgåder, såsom glidende gåder, Sudoku og 8-puslespilsproblemet. Ressourceallokering: I scenarier, hvor ressourcer skal allokeres optimalt, kan A* hjælpe med at finde den mest effektive allokeringsvej, minimere omkostningerne og maksimere effektiviteten.Netværksrouting:A* kan bruges i computernetværk til at finde den mest effektive rute for datapakker fra en kilde til en destinationsknude.Natural Language Processing (NLP):I nogle NLP-opgaver kan A* generere sammenhængende og kontekstuelle svar ved at søge efter mulige ordsekvenser baseret på deres sandsynlighed og relevans.Stiplanlægning i robotteknologi:A* kan bruges til at planlægge en robots vej fra et punkt til et andet under hensyntagen til forskellige begrænsninger, såsom at undgå forhindringer eller minimere energiforbruget.Spil AI:A* bruges også til at træffe intelligente beslutninger for ikke-spillerfigurer (NPC'er), såsom at bestemme den bedste måde at nå et mål på eller koordinere bevægelser i et holdbaseret spil.

Dette er blot nogle få eksempler på, hvordan A*-søgealgoritmen finder applikationer inden for forskellige områder af kunstig intelligens. Dens fleksibilitet, effektivitet og optimering gør det til et værdifuldt værktøj til mange problemer.

C-program til A*-søgealgoritme i kunstig 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 til A* Search Algorithm in Artificial Intelligence

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

Forklaring:

Strukturknude:Dette definerer en nodestruktur, der repræsenterer en gittercelle. Den indeholder x- og y-koordinaterne for knudepunktet, prisen g fra startknuden til den pågældende knude, den heuristiske værdi h (estimerede omkostninger fra den knude til destinationsknuden) og en pegepind til
1. startknudepunktet for stien.
Beregn heuristik:Denne funktion beregner en heuristik ved hjælp af den euklidiske afstand mellem en knude og målet AStarSearch: Denne funktion kører A*-søgealgoritmen. Den tager start- og destinationskoordinaterne, et gitter og returnerer en vektor af par, der repræsenterer koordinaterne for den korteste vej fra start til slut.Primær:Programmets hovedfunktion tager inputgitter, oprindelse og målkoordinater fra brugeren. Den kalder derefter AStarSearch for at finde den korteste vej og udskriver resultatet. Strukturnode: Dette definerer en nodestruktur, der repræsenterer en gittercelle. Den indeholder x- og y-koordinaterne for knudepunktet, prisen g fra startknudepunktet til det knudepunkt, den heuristiske værdi h (estimeret pris fra den knude til destinationsknuden) og en pegepind til stiens startknudepunkt.Beregn heuristik:Denne funktion beregner heuristik ved hjælp af den euklidiske afstand mellem en knude og målet AStarSearch: Denne funktion kører A*-søgealgoritmen. Den tager start- og destinationskoordinaterne, et gitter og returnerer en vektor af par, der repræsenterer koordinaterne for den korteste vej fra start til slut.

Prøve output

 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 til A* Search Algorithm in Artificial Intelligence

 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øgealgoritmekompleksitet i kunstig intelligens

A*-søgealgoritmen (udtales 'A-stjerne') er en populær og meget brugt grafgennemgang og stisøgningsalgoritme inden for kunstig intelligens. At finde den korteste vej mellem to noder i et graf- eller gitterbaseret miljø er normalt almindeligt. Algoritmen kombinerer Dijkstras og grådige best-first søgeelementer for at udforske søgerummet og samtidig sikre optimalitet effektivt. Adskillige faktorer bestemmer kompleksiteten af ​​A*-søgealgoritmen. Grafstørrelse (knudepunkter og kanter): En grafs antal af noder og kanter påvirker i høj grad algoritmens kompleksitet. Flere noder og kanter betyder flere mulige muligheder at udforske, hvilket kan øge algoritmens udførelsestid.

Heuristisk funktion: A* bruger en heuristisk funktion (ofte betegnet h(n)) til at estimere omkostningerne fra den aktuelle knude til destinationsknuden. Præcisionen af ​​denne heuristik påvirker i høj grad effektiviteten af ​​A*-søgningen. En god heuristik kan hjælpe med at guide søgningen til et mål hurtigere, mens en dårlig heuristik kan føre til unødvendig søgning.

Datastrukturer:A* opretholder to hoveddatastrukturer: en åben liste (prioritetskø) og en lukket liste (eller besøgt pulje). Effektiviteten af ​​disse datastrukturer, sammen med den valgte implementering (f.eks. prioritetskø binære dynger), påvirker algoritmens ydeevne.Filialfaktor:Det gennemsnitlige antal følgere for hver node påvirker antallet af noder, der udvides under søgningen. En højere forgreningsfaktor kan føre til mere udforskning, hvilket øgesOptimalitet og fuldstændighed:A* garanterer både optimalitet (finde den korteste vej) og fuldstændighed (finde en løsning, der findes). Denne garanti kommer dog med en afvejning med hensyn til beregningsmæssig kompleksitet, da algoritmen skal udforske forskellige veje for optimal ydeevne. Vedrørende tidskompleksitet påvirker den valgte heuristiske funktion A* i værste fald. Med en accepteret heuristik (som aldrig overvurderer de sande omkostninger ved at nå målet), udvider A* de færreste noder blandt optimeringsalgoritmerne. Worst-case tidskompleksiteten af ​​A * er eksponentiel i worst-case O(b ^ d), hvor 'b' er den effektive forgreningsfaktor (gennemsnitligt antal følgere pr. node) og 'd' er den optimale

I praksis klarer A* sig dog ofte væsentligt bedre på grund af indflydelsen fra en heuristisk funktion, der hjælper med at guide algoritmen til lovende veje. I tilfælde af en veldesignet heuristik er den effektive forgreningsfaktor meget mindre, hvilket fører til en hurtigere tilgang til den optimale løsning.