logo

A* Iskalni algoritem v umetni inteligenci

Uvod v iskalni algoritem A* v AI

A* (izgovarja se 'A-star') je zmogljiv algoritem za prečkanje grafov in iskanje poti, ki se pogosto uporablja v umetni inteligenci in računalništvu. Uporablja se predvsem za iskanje najkrajše poti med dvema vozliščema v grafu glede na ocenjeno ceno poti od trenutnega vozlišča do ciljnega vozlišča. Glavna prednost algoritma je njegova sposobnost zagotavljanja optimalne poti z raziskovanjem grafa na bolj informiran način v primerjavi s tradicionalnimi iskalnimi algoritmi, kot je Dijkstrajev algoritem.

Algoritem A* združuje prednosti dveh drugih iskalnih algoritmov: Dijkstrinega algoritma in Greedy Best-First Search. Tako kot Dijkstrajev algoritem tudi A* zagotavlja, da je najdena pot čim krajša, vendar to počne učinkoviteje z usmerjanjem iskanja skozi hevristiko, ki je podobna Greedy Best-First Search. Hevristična funkcija, označena s h(n), oceni stroške poti od katerega koli danega vozlišča n do ciljnega vozlišča.

Glavna ideja A* je ovrednotiti vsako vozlišče na podlagi dveh parametrov:

c program za dvodimenzionalni niz
    g(n):dejanski strošek za prehod od začetnega vozlišča do vozlišča n. Predstavlja vsoto stroškov izhodnih robov vozlišča n.h(n):Hevristični stroški (znani tudi kot 'stroški ocene') od vozlišča n do ciljnega vozlišča n. Ta hevristična funkcija, specifična za problem, mora biti sprejemljiva, kar pomeni, da nikoli ne precenjuje dejanskih stroškov doseganja cilja. Funkcija vrednotenja vozlišča n je definirana kot f(n) = g(n) h(n).

Algoritem A* izbere vozlišča, ki jih je treba raziskati, na podlagi najnižje vrednosti f(n), pri čemer daje prednost vozliščem z najnižjimi ocenjenimi skupnimi stroški za doseganje cilja. Algoritem A* deluje:

  1. Ustvarite odprt seznam najdenih, vendar neraziskanih vozlišč.
  2. Ustvarite zaprt seznam za že raziskana vozlišča.
  3. Dodajte začetno vozlišče na odprt seznam z začetno vrednostjo g
  4. Ponavljajte naslednje korake, dokler odprti seznam ni prazen ali dokler ne dosežete ciljnega vozlišča:
    1. Poiščite vozlišče z najmanjšo f-vrednostjo (tj. vozlišče z manjšim g(n) h(n)) na odprtem seznamu.
    2. Premaknite izbrano vozlišče z odprtega seznama na zaprti seznam.
    3. Ustvarite vse veljavne potomce izbranega vozlišča.
    4. Za vsakega naslednika izračunajte njegovo vrednost g kot vsoto vrednosti g trenutnega vozlišča in stroškov premika od trenutnega vozlišča do vozlišča naslednika. Posodobite g-vrednost sledilnika, ko je najdena boljša pot.
    5. Če sledilca ni na odprtem seznamu, ga dodajte z izračunano g-vrednostjo in izračunajte njegovo h-vrednost. Če je že na odprtem seznamu, posodobite njegovo vrednost g, če je nova pot boljša.
    6. Ponovite cikel. Algoritem A* se zaključi, ko je doseženo ciljno vozlišče ali ko se odprti seznam izprazni, kar kaže, da ni poti od začetnega vozlišča do ciljnega vozlišča. Iskalni algoritem A* se široko uporablja na različnih področjih, kot so robotika, video igre, omrežno usmerjanje in težave pri načrtovanju, ker je učinkovit in lahko najde optimalne poti v grafih ali omrežjih.

Vendar pa je izbira primerne in sprejemljive hevristične funkcije bistvena, da algoritem deluje pravilno in zagotavlja optimalno rešitev.

Informirani iskalni algoritmi

Zgodovina iskalnega algoritma A* v umetni inteligenci

Razvili so ga Peter Hart, Nils Nilsson in Bertram Raphael na raziskovalnem inštitutu Stanford (zdaj SRI International) kot razširitev Dijkstrinega algoritma in drugih iskalnih algoritmov tistega časa. A* je bil prvič objavljen leta 1968 in je hitro pridobil priznanje za svoj pomen in učinkovitost v skupnostih umetne inteligence in računalništva. Tukaj je kratek pregled najbolj kritičnih mejnikov v zgodovini iskalnega algoritma A*:

    Algoritmi zgodnjega iskanja:Pred razvojem A* so obstajali različni algoritmi iskanja po grafih, vključno z iskanjem najprej v globino (DFS) in iskanjem najprej v širino (BFS). Čeprav so ti algoritmi pomagali najti poti, niso zagotovili optimalnosti ali upoštevali hevristike za vodenje iskanjaDijkstrajev algoritem:Leta 1959 je nizozemski računalniški znanstvenik Edsger W. Dijkstra predstavil Dijkstrajev algoritem, ki je našel najkrajšo pot v uteženem grafu z nenegativnimi utežmi robov. Dijkstrajev algoritem je bil učinkovit, vendar je imel zaradi svoje izčrpne narave omejitve pri uporabi na večjih grafih oz.Informirano iskanje:Iskalni algoritmi, ki temeljijo na znanju (znani tudi kot hevristično iskanje), so bili razviti za vključitev hevrističnih informacij, kot so ocenjeni stroški, za učinkovito vodenje postopka iskanja. Greedy Best-First Search je bil en tak algoritem, vendar ni zagotovil optimalnosti za iskanje najkrajše poti.A* razvoj:Leta 1968 so Peter Hart, Nils Nilsson in Bertram Raphael predstavili algoritem A* kot kombinacijo Dijkstrinega algoritma in Greedy Best-First Search. A* je uporabil hevristično funkcijo za oceno stroškov od trenutnega vozlišča do ciljnega vozlišča tako, da jih je združil z dejanskimi stroški doseganja trenutnega vozlišča. To je A* omogočilo bolj zavestno raziskovanje grafa, izogibanje nepotrebnim potem in zagotavljanje optimalne rešitve.Pravičnost in popolnost:Avtorji A* so pokazali, da je algoritem popoln (vedno najde rešitev, če ta obstaja) in optimalen (najde najkrajšo pot) pod določenimi pogoji.Široko sprejetje in napredek:A* je zaradi svoje učinkovitosti hitro pridobil priljubljenost v skupnostih AI in IT. Raziskovalci in razvijalci so razširili in uporabili algoritem A* na različnih področjih, vključno z robotiko, video igrami, inženiringom in omrežnim usmerjanjem. V preteklih letih je bilo predlaganih več različic in optimizacij algoritma A*, kot sta inkrementalni A* in vzporedni A*. Danes je iskalni algoritem A* še vedno temeljni in pogosto uporabljen algoritem v umetni inteligenci in prečkanju grafov. Še naprej igra bistveno vlogo v različnih aplikacijah in raziskovalnih področjih. Zaradi njegovega vpliva na umetno inteligenco in njenega prispevka k težavam pri iskanju poti in optimizaciji je postal temeljni algoritem v raziskavah inteligentnih sistemov.

Kako deluje iskalni algoritem A* v umetni inteligenci?

Iskalni algoritem A* (izgovarja se 'črka A') je priljubljen in pogosto uporabljen algoritem za prečkanje grafov v umetni inteligenci in računalništvu. Uporablja se za iskanje najkrajše poti od začetnega vozlišča do ciljnega vozlišča v tehtanem grafu. A* je informiran iskalni algoritem, ki uporablja hevristiko za učinkovito vodenje iskanja. Iskalni algoritem A* deluje na naslednji način:

Algoritem se začne s prednostno čakalno vrsto za shranjevanje vozlišč, ki jih je treba raziskati. Instancira tudi dve podatkovni strukturi g(n): strošek najkrajše poti doslej od začetnega vozlišča do vozlišča n in h(n), ocenjen strošek (hevristika) od vozlišča n do ciljnega vozlišča. Pogosto je razumna hevristika, kar pomeni, da nikoli ne preceni dejanskih stroškov doseganja cilja. Postavite začetno vozlišče v prednostno čakalno vrsto in nastavite njegov g(n) na 0. Če prednostna čakalna vrsta ni prazna, odstranite vozlišče z najnižjo vrednostjo f(n) iz prednostne čakalne vrste. f(n) = g(n) h(n). Če je izbrisano vozlišče ciljno vozlišče, se algoritem konča in pot je najdena. V nasprotnem primeru razširite vozlišče in ustvarite njegove sosede. Za vsako sosednje vozlišče izračunajte njegovo začetno vrednost g(n), ki je vsota vrednosti g trenutnega vozlišča in stroškov premika iz trenutnega vozlišča v sosednje vozlišče. Če sosednje vozlišče ni v prednostnem vrstnem redu ali je prvotna vrednost g(n) manjša od njegove trenutne vrednosti g, posodobite njegovo vrednost g in nastavite njegovo nadrejeno vozlišče na trenutno vozlišče. Izračunajte vrednost f(n) iz sosednjega vozlišča in jo dodajte v prednostno čakalno vrsto.

Če se cikel konča, ne da bi našli ciljno vozlišče, graf nima poti od začetka do konca. Ključ do učinkovitosti A* je njegova uporaba hevristične funkcije h(n), ki zagotavlja oceno preostalih stroškov za doseganje cilja katerega koli vozlišča. S kombiniranjem dejanskih stroškov g (n) s hevrističnimi stroški h (n) algoritem učinkovito raziskuje obetavne poti in daje prednost vozliščem, ki bodo verjetno vodila do najkrajše poti. Pomembno je omeniti, da je učinkovitost algoritma A* močno odvisna od izbire hevristične funkcije. Sprejemljiva hevristika zagotavlja, da algoritem vedno najde najkrajšo pot, vendar lahko bolj obveščena in natančna hevristika vodi do hitrejše konvergence in zmanjšanega iskalnega prostora.

Prednosti iskalnega algoritma A* v umetni inteligenci

Iskalni algoritem A* ponuja več prednosti v scenarijih umetne inteligence in reševanja problemov:

    Optimalna rešitev:A* zagotavlja iskanje optimalne (najkrajše) poti od začetnega vozlišča do ciljnega vozlišča v uteženem grafu glede na sprejemljivo hevristično funkcijo. Ta optimalnost je odločilna prednost v številnih aplikacijah, kjer je iskanje najkrajše poti bistveno.Popolnost:Če rešitev obstaja, jo bo A* našel, pod pogojem, da graf nima neskončne cene. Ta lastnost popolnosti zagotavlja, da lahko A* izkoristi rešitev, če obstaja.Učinkovitost:A* je učinkovit, če je uporabljena učinkovita in sprejemljiva hevristična funkcija. Hevristika vodi iskanje do cilja z osredotočanjem na obetavne poti in izogibanjem nepotrebnemu raziskovanju, zaradi česar je A* učinkovitejši od algoritmov nezavednega iskanja, kot sta iskanje v širino ali iskanje v globino.Vsestranskost:A* je široko uporaben za različna problematična področja, vključno z iskanjem poti, načrtovanjem poti, robotiko, razvojem iger itd. A* se lahko uporablja za učinkovito iskanje optimalnih rešitev, če je mogoče definirati smiselno hevristiko.Optimizirano iskanje:A* ohranja prednostni vrstni red za izbiro vozlišč z manjšo vrednostjo f(n) (g(n) in h(n)) za razširitev. To mu omogoča, da najprej razišče obetavne poti, kar zmanjša iskalni prostor in vodi do hitrejše konvergence.Učinkovitost pomnilnika:Za razliko od nekaterih drugih iskalnih algoritmov, kot je iskanje v širino, A* shrani le omejeno število vozlišč v prednostni čakalni vrsti, zaradi česar je učinkovit pri pomnilniku, zlasti pri velikih grafih.Nastavljiva hevristika:Delovanje A* je mogoče natančno prilagoditi z izbiro različnih hevrističnih funkcij. Bolj izobražena hevristika lahko vodi do hitrejše konvergence in manj razširjenih vozlišč.Obširno raziskano:A* je dobro uveljavljen algoritem z desetletji raziskav in praktičnih aplikacij. Razvitih je bilo veliko optimizacij in različic, zaradi česar je zanesljivo in dobro razumljivo orodje za odpravljanje težav.Spletno iskanje:A* se lahko uporablja za spletno iskanje poti, kjer algoritem nenehno posodablja pot glede na spremembe v okolju ali pojav novih. Omogoča sprejemanje odločitev v realnem času v dinamičnih scenarijih.

Slabosti iskalnega algoritma A* v umetni inteligenci

Čeprav je iskalni algoritem A* (črka A) široko uporabljena in zmogljiva tehnika za reševanje težav z iskanjem poti in prečkanjem grafov z umetno inteligenco, ima slabosti in omejitve. Tukaj je nekaj glavnih slabosti iskalnega algoritma:

    Hevristična natančnost:Delovanje algoritma A* je močno odvisno od točnosti hevristične funkcije, ki se uporablja za oceno stroškov od trenutnega vozlišča do vozlišča. Če je hevristika nesprejemljiva (nikoli ne preceni dejanskih stroškov) ali nedosledna (zadovoljuje neenakost trikotnika), morda ne najde optimalne poti ali razišče več vozlišč, kot je potrebno, kar vpliva na njegovo učinkovitost in natančnost.Poraba pomnilnika:A* zahteva, da se vsa obiskana vozlišča hranijo v pomnilniku, da se spremljajo raziskane poti. Uporaba pomnilnika lahko včasih postane pomembna težava, še posebej, če imamo opravka z dovolj prostora za iskanje ali omejenimi viri pomnilnika.Časovna zahtevnost:Čeprav je A* na splošno učinkovit, je njegova časovna zapletenost lahko zaskrbljujoča zaradi velikih iskalnih prostorov ali grafov. V najslabšem primeru lahko A* potrebuje eksponentno dlje, da najde optimalno pot, če hevristika ni primerna za težavo.Ozko grlo na cilju:V posebnih scenarijih mora algoritem A* raziskati vozlišča daleč od cilja, preden končno doseže ciljno regijo. Ta težava se pojavi, ko mora hevristika zgodaj učinkovito usmeriti iskanje k cilju.Vezava stroškov:A* se sooča s težavami, ko ima več vozlišč enako f-vrednost (vsota dejanskih stroškov in hevrističnih stroškov). Uporabljena strategija lahko vpliva na optimalnost in učinkovitost odkrite poti. Če z njim ne ravnate pravilno, lahko povzroči raziskovanje nepotrebnih vozlišč in upočasni algoritem.Kompleksnost v dinamičnih okoljih:V dinamičnih okoljih, kjer se lahko stroški robov ali vozlišč med iskanjem spreminjajo, A* morda ni primeren, ker se ne prilagaja dobro takim spremembam. Preoblikovanje iz nič je lahko računsko drago in algoritmi D* (Dynamic A*) so bili zasnovani za rešitev tegaPopolnost v neskončnem prostoru:A* morda ne bo našel rešitve v neskončnem prostoru stanj. V takih primerih lahko teče v nedogled in raziskuje vedno večje število vozlišč, ne da bi našel rešitev. Kljub tem pomanjkljivostim je A* še vedno robusten in pogosto uporabljen algoritem, saj lahko učinkovito najde optimalne poti v številnih praktičnih situacijah, če je hevristična funkcija dobro zasnovana in iskalni prostor obvladljiv. Za ublažitev nekaterih njegovih omejitev so bile predlagane različne različice in različice A*.

Uporaba iskalnega algoritma A* v umetni inteligenci

Iskalni algoritem A* (črka A) je široko uporabljen in robusten algoritem za iskanje poti v umetni inteligenci in računalništvu. Zaradi svoje učinkovitosti in optimalnosti je primeren za različne aplikacije. Tukaj je nekaj tipičnih aplikacij iskalnega algoritma A* v umetni inteligenci:

    Iskanje poti v igrah:A* se pogosto uporablja v video igrah za premikanje likov, sovražnikovo navigacijo z umetno inteligenco in iskanje najkrajše poti od ene lokacije do druge na zemljevidu igre. Njegova zmožnost iskanja optimalne poti na podlagi stroškov in hevristike je idealna za aplikacije v realnem času, kot so igre.Robotika in avtonomna vozila:A* se uporablja v robotiki in avtonomni navigaciji vozil za načrtovanje neoptimalne poti za robote do cilja, izogibanje oviram in upoštevanje stroškov terena. To je ključnega pomena za učinkovito in varno gibanje v naravnem okolju.Reševanje labirinta:A* lahko učinkovito najde najkrajšo pot skozi labirint, zaradi česar je dragocen v številnih aplikacijah za reševanje labirintov, kot je reševanje ugank ali krmarjenje po kompleksnih strukturah.Načrtovanje poti in navigacija:V sistemih GPS in aplikacijah za kartiranje lahko A* uporabite za iskanje optimalne poti med dvema točkama na zemljevidu ob upoštevanju dejavnikov, kot so razdalja, prometne razmere in topologija cestnega omrežja.Reševanje ugank:A* lahko reši različne uganke z diagrami, kot so drseče uganke, sudoku in problem 8 ugank. Dodeljevanje virov: V scenarijih, kjer morajo biti viri optimalno dodeljeni, lahko A* pomaga najti najučinkovitejšo pot dodeljevanja, kar zmanjša stroške in poveča učinkovitost.Omrežno usmerjanje:A* se lahko uporablja v računalniških omrežjih za iskanje najučinkovitejše poti za podatkovne pakete od vira do ciljnega vozlišča.Obdelava naravnega jezika (NLP):Pri nekaterih nalogah NLP lahko A* ustvari koherentne in kontekstualne odzive z iskanjem možnih zaporedij besed na podlagi njihove verjetnosti in ustreznosti.Načrtovanje poti v robotiki:A* se lahko uporablja za načrtovanje poti robota od ene točke do druge ob upoštevanju različnih omejitev, kot je izogibanje oviram ali zmanjšanje porabe energije.Igra AI:A* se uporablja tudi za sprejemanje inteligentnih odločitev za like, ki niso igralci (NPC), kot je določanje najboljšega načina za doseganje cilja ali usklajevanje gibov v ekipni igri.

To je le nekaj primerov, kako iskalni algoritem A* najde aplikacije na različnih področjih umetne inteligence. Zaradi svoje prilagodljivosti, učinkovitosti in optimizacije je dragoceno orodje za številne težave.

primerjava v Javi

C program za iskalni algoritem A* v umetni inteligenci

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

Program C++ za iskalni algoritem A* v umetni inteligenci

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

Pojasnilo:

    Strukturno vozlišče:To definira strukturo vozlišča, ki predstavlja celico mreže. Vsebuje koordinate x in y vozlišča, ceno g od začetnega vozlišča do tega vozlišča, hevristično vrednost h (ocenjena cena od tega vozlišča do ciljnega vozlišča) in kazalec na
  1. začetno vozlišče poti.
  2. Izračunaj hevristiko:Ta funkcija izračuna hevristiko z uporabo evklidske razdalje med vozliščem in ciljem AStarSearch: Ta funkcija zažene iskalni algoritem A*. Vzame začetne in ciljne koordinate, mrežo, in vrne vektor parov, ki predstavljajo koordinate najkrajše poti od začetka do cilja.Primarni:Glavna funkcija programa od uporabnika vzame vhodne mreže, izvorne in ciljne koordinate. Nato pokliče AStarSearch, da poišče najkrajšo pot in natisne rezultat. Strukturno vozlišče: To definira strukturo vozlišča, ki predstavlja mrežno celico. Vsebuje koordinate x in y vozlišča, ceno g od začetnega vozlišča do tega vozlišča, hevristično vrednost h (ocenjeni stroški od tega vozlišča do ciljnega vozlišča) in kazalec na začetno vozlišče poti.Izračunaj hevristiko:Ta funkcija izračuna hevristiko z uporabo evklidske razdalje med vozliščem in ciljem AStarSearch: Ta funkcija zažene iskalni algoritem A*. Vzame začetne in ciljne koordinate, mrežo, in vrne vektor parov, ki predstavljajo koordinate najkrajše poti od začetka do cilja.

Vzorec izhoda

 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 

Program Java za iskalni algoritem A* v umetni inteligenci

 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* Kompleksnost iskalnega algoritma v umetni inteligenci

Iskalni algoritem A* (izgovarja se 'A-zvezda') je priljubljen in široko uporabljen algoritem za prečkanje grafov in iskanje poti v umetni inteligenci. Iskanje najkrajše poti med dvema vozliščema v okolju, ki temelji na grafu ali mreži, je običajno običajno. Algoritem združuje Dijkstrove in požrešne iskalne elemente najboljšega prvega za raziskovanje iskalnega prostora, hkrati pa zagotavlja učinkovito optimalnost. Kompleksnost iskalnega algoritma A* določa več dejavnikov. Velikost grafa (vozlišča in robovi): število vozlišč in robov grafa močno vpliva na kompleksnost algoritma. Več vozlišč in robov pomeni več možnih možnosti za raziskovanje, kar lahko podaljša čas izvajanja algoritma.

Hevristična funkcija: A* uporablja hevristično funkcijo (pogosto označeno kot h(n)) za oceno stroškov od trenutnega vozlišča do ciljnega vozlišča. Natančnost te hevristike močno vpliva na učinkovitost iskanja A*. Dobra hevristika lahko pripomore k hitrejšemu vodenju iskanja do cilja, medtem ko lahko slaba hevristika privede do nepotrebnega iskanja.

    Podatkovne strukture:A* vzdržuje dve strukturi glavnih podatkov: odprt seznam (prednostna čakalna vrsta) in zaprt seznam (ali obiskano skupino). Učinkovitost teh podatkovnih struktur skupaj z izbrano izvedbo (npr. binarne kopice prednostne čakalne vrste) vpliva na delovanje algoritma.Faktor veje:Povprečno število sledilcev za vsako vozlišče vpliva na število vozlišč, razširjenih med iskanjem. Višji faktor razvejanja lahko privede do večjega raziskovanja, kar se povečaOptimalnost in popolnost:A* zagotavlja tako optimalnost (iskanje najkrajše poti) kot popolnost (iskanje rešitve, ki obstaja). Vendar pa to jamstvo vključuje kompromis v smislu računske kompleksnosti, saj mora algoritem raziskati različne poti za optimalno delovanje. Kar zadeva časovno kompleksnost, izbrana hevristična funkcija v najslabšem primeru vpliva na A*. S sprejeto hevristiko (ki nikoli ne preceni resničnih stroškov doseganja cilja) A* razširi najmanjše število vozlišč med optimizacijskimi algoritmi. Časovna kompleksnost A * v najslabšem primeru je eksponentna v najslabšem primeru O(b ^ d), kjer je 'b' efektivni faktor razvejanja (povprečno število sledilcev na vozlišče) in 'd' optimalen

V praksi pa A* pogosto deluje bistveno bolje zaradi vpliva hevristične funkcije, ki pomaga voditi algoritem na obetavne poti. V primeru dobro zasnovane hevristike je efektivni faktor razvejanja veliko manjši, kar vodi do hitrejšega približevanja optimalni rešitvi.