logo

A* Algoritm de căutare în inteligența artificială

O introducere în algoritmul de căutare A* în AI

A* (pronunțat „A-star”) este un algoritm puternic de parcurgere a graficului și de găsire a căii utilizat pe scară largă în inteligența artificială și informatică. Este folosit în principal pentru a găsi calea cea mai scurtă între două noduri dintr-un grafic, având în vedere costul estimat de a ajunge de la nodul curent la nodul de destinație. Principalul avantaj al algoritmului este capacitatea sa de a oferi o cale optimă prin explorarea graficului într-un mod mai informat în comparație cu algoritmii tradiționali de căutare, cum ar fi algoritmul lui Dijkstra.

Algoritmul A* combină avantajele altor doi algoritmi de căutare: algoritmul lui Dijkstra și Greedy Best-First Search. La fel ca algoritmul lui Dijkstra, A* se asigură că calea găsită este cât mai scurtă posibil, dar o face mai eficient prin direcționarea căutării sale printr-o euristică similară cu Greedy Best-First Search. O funcție euristică, notată h(n), estimează costul de a ajunge de la orice nod dat n la nodul destinație.

Ideea principală a lui A* este de a evalua fiecare nod pe baza a doi parametri:

încercați catch block în java
    g(n):costul real pentru a ajunge de la nodul inițial la nodul n. Reprezintă suma costurilor nodului n margini de ieșire.h(n):Costul euristic (cunoscut și ca „cost de estimare”) de la nodul n până la nodul de destinație n. Această funcție euristică specifică problemei trebuie să fie acceptabilă, ceea ce înseamnă că nu supraestimează niciodată costul real al atingerii obiectivului. Funcția de evaluare a nodului n este definită ca f(n) = g(n) h(n).

Algoritmul A* selectează nodurile de explorat pe baza celei mai mici valori a f(n), preferând nodurile cu cel mai mic cost total estimat pentru a atinge obiectivul. Algoritmul A* funcționează:

  1. Creați o listă deschisă de noduri găsite, dar nu explorate.
  2. Creați o listă închisă pentru a păstra nodurile deja explorate.
  3. Adăugați un nod de pornire la lista deschisă cu o valoare inițială de g
  4. Repetați următorii pași până când lista deschisă este goală sau ajungeți la nodul țintă:
    1. Găsiți nodul cu cea mai mică valoare f (adică nodul cu g(n) h(n) minor) în lista deschisă.
    2. Mutați nodul selectat din lista deschisă în lista închisă.
    3. Creați toți descendenții validi ai nodului selectat.
    4. Pentru fiecare succesor, își calculează valoarea g ca suma dintre valoarea g a nodului curent și costul deplasării de la nodul curent la nodul succesor. Actualizați valoarea g a trackerului atunci când este găsită o cale mai bună.
    5. Dacă următorul nu se află în lista deschisă, adăugați-l cu valoarea g calculată și calculați valoarea sa h. Dacă este deja în lista deschisă, actualizați valoarea sa g dacă noua cale este mai bună.
    6. Repetați ciclul. Algoritmul A* se termină când este atins nodul țintă sau când lista deschisă se golește, indicând că nu există căi de la nodul de pornire la nodul țintă. Algoritmul de căutare A* este utilizat pe scară largă în diverse domenii, cum ar fi robotica, jocurile video, rutarea rețelei și problemele de proiectare, deoarece este eficient și poate găsi căi optime în grafice sau rețele.

Cu toate acestea, alegerea unei funcții euristice adecvate și acceptabile este esențială pentru ca algoritmul să funcționeze corect și să ofere o soluție optimă.

Algoritmi de căutare informați

Istoria algoritmului de căutare A* în inteligența artificială

A fost dezvoltat de Peter Hart, Nils Nilsson și Bertram Raphael la Institutul de Cercetare Stanford (acum SRI International) ca o extensie a algoritmului Dijkstra și a altor algoritmi de căutare ai vremii. A* a fost publicat pentru prima dată în 1968 și a câștigat rapid recunoașterea pentru importanța și eficacitatea sa în comunitățile de inteligență artificială și informatică. Iată o scurtă prezentare generală a celor mai critice repere din istoria algoritmului de căutare A*:

    Algoritmi de căutare timpurii:Înainte de dezvoltarea lui A*, existau diverși algoritmi de căutare în grafic, inclusiv Depth-First Search (DFS) și Breadth-First Search (BFS). Deși acești algoritmi au ajutat la găsirea căilor, ei nu au garantat optimitatea și nici nu au luat în considerare euristica pentru a ghida căutareaAlgoritmul lui Dijkstra:În 1959, informaticianul olandez Edsger W. Dijkstra a introdus algoritmul lui Dijkstra, care a găsit calea cea mai scurtă într-un grafic ponderat cu greutăți de margine nenegative. Algoritmul lui Dijkstra a fost eficient, dar datorită naturii sale exhaustive, avea limitări atunci când era utilizat pe grafice mai mari sauCăutare informată:Algoritmii de căutare bazați pe cunoștințe (cunoscuți și ca căutare euristică) au fost dezvoltați pentru a încorpora informații euristice, cum ar fi costurile estimate, pentru a ghida procesul de căutare în mod eficient. Greedy Best-First Search a fost un astfel de algoritm, dar nu a garantat optimitatea pentru găsirea celei mai scurte căi.A* dezvoltare:În 1968, Peter Hart, Nils Nilsson și Bertram Raphael au introdus algoritmul A* ca o combinație a algoritmului lui Dijkstra și Greedy Best-First Search. A* a folosit o funcție euristică pentru a estima costul de la nodul curent la nodul destinație, combinându-l cu costul real de a ajunge la nodul curent. Acest lucru a permis lui A* să exploreze graficul mai conștient, evitând căile inutile și garantând o soluție optimă.Dreptate și perfecțiune:Autorii lui A* au arătat că algoritmul este perfect (găsește întotdeauna o soluție dacă există) și optim (găsește calea cea mai scurtă) în anumite condiții.Adopție și progres pe scară largă:A* a câștigat rapid popularitate în comunitățile AI și IT datorită eficienței sale, iar Cercetătorii și dezvoltatorii au extins și aplicat algoritmul A* în diferite domenii, inclusiv robotică, jocuri video, inginerie și rutare a rețelei. De-a lungul anilor au fost propuse mai multe variații și optimizări ale algoritmului A*, cum ar fi A* incremental și A* paralel. Astăzi, algoritmul de căutare A* este încă un algoritm fundamental și utilizat pe scară largă în inteligența artificială și traversarea graficelor. Continuă să joace un rol esențial în diverse aplicații și domenii de cercetare. Impactul său asupra inteligenței artificiale și contribuția sa la problemele de căutare și optimizare au făcut din aceasta un algoritm de piatră de temelie în cercetarea sistemelor inteligente.

Cum funcționează algoritmul de căutare A* în inteligența artificială?

Algoritmul de căutare A* (pronunțat „litera A”) este un algoritm de traversare a graficelor popular și utilizat pe scară largă în inteligența artificială și informatică. Este folosit pentru a găsi calea cea mai scurtă de la un nod de pornire la un nod de destinație într-un grafic ponderat. A* este un algoritm de căutare informat care utilizează euristica pentru a ghida căutarea în mod eficient. Algoritmul de căutare A* funcționează după cum urmează:

Algoritmul începe cu o coadă de prioritate pentru a stoca nodurile de explorat. De asemenea, instanțiază două structuri de date g(n): costul celei mai scurte căi de până acum de la nodul de pornire la nodul n și h(n), costul estimat (euristic) de la nodul n la nodul de destinație. Este adesea o euristică rezonabilă, ceea ce înseamnă că nu supraestimează niciodată costul real al atingerii unui obiectiv. Puneți nodul inițial în coada de prioritate și setați-i g(n) la 0. Dacă coada de prioritate nu este goală, eliminați nodul cu cel mai mic f(n) din coada de prioritate. f(n) = g(n) h(n). Dacă nodul șters este nodul destinație, algoritmul se termină și calea este găsită. În caz contrar, extindeți nodul și creați-i vecinii. Pentru fiecare nod vecin, calculați valoarea sa inițială g(n), care este suma valorii g a nodului curent și costul deplasării de la nodul curent la un nod vecin. Dacă nodul vecin nu este în ordinea priorităților sau valoarea inițială g(n) este mai mică decât valoarea sa actuală g, actualizați valoarea sa g și setați nodul părinte la nodul curent. Calculați valoarea f(n) de la nodul vecin și adăugați-o la coada de prioritate.

Dacă ciclul se termină fără a găsi nodul destinație, graficul nu are o cale de la început până la sfârșit. Cheia eficienței lui A* este utilizarea unei funcții euristice h(n) care oferă o estimare a costului rămas pentru atingerea obiectivului oricărui nod. Combinând costul real g (n) cu costul euristic h (n), algoritmul explorează în mod eficient căi promițătoare, dând prioritate nodurilor care pot duce la calea cea mai scurtă. Este important de menționat că eficiența algoritmului A* depinde în mare măsură de alegerea funcției euristice. Euristice acceptabile asigură că algoritmul găsește întotdeauna calea cea mai scurtă, dar euristicile mai informate și mai precise pot duce la o convergență mai rapidă și la un spațiu de căutare redus.

Avantajele algoritmului de căutare A* în inteligența artificială

Algoritmul de căutare A* oferă mai multe avantaje în inteligența artificială și scenariile de rezolvare a problemelor:

    Soluție optimă:A* asigură găsirea căii optime (cea mai scurtă) de la nodul de pornire la nodul de destinație în graficul ponderat, având în vedere o funcție euristică acceptabilă. Această optimitate este un avantaj decisiv în multe aplicații în care găsirea căii celei mai scurte este esențială.Completitudine:Dacă există o soluție, A* o va găsi, cu condiția ca graficul să nu aibă un cost infinit. Această proprietate de completitudine asigură că A* poate profita de o soluție dacă aceasta există.Eficienţă:A* este eficient dacă se utilizează o funcție euristică eficientă și acceptabilă. Euristicile ghidează căutarea către un scop concentrându-se pe căi promițătoare și evitând explorările inutile, făcând A* mai eficient decât algoritmii de căutare neconștienți, cum ar fi căutarea pe lățime sau căutarea pe adâncime.Versatilitate:A* este aplicabil pe scară largă în diverse zone cu probleme, inclusiv orientare, planificare rută, robotică, dezvoltare de jocuri și multe altele. A* poate fi folosit pentru a găsi soluții optime în mod eficient, atâta timp cât poate fi definită o euristică semnificativă.Căutare optimizată:A* menține o ordine de prioritate pentru a selecta nodurile cu valoarea minoră f(n) (g(n) și h(n)) pentru expansiune. Acest lucru îi permite să exploreze mai întâi căi promițătoare, ceea ce reduce spațiul de căutare și duce la o convergență mai rapidă.Eficiența memoriei:Spre deosebire de alți algoritmi de căutare, cum ar fi căutarea pe lățime, A* stochează doar un număr limitat de noduri în coada de prioritate, ceea ce o face eficientă în memorie, în special pentru graficele mari.Euristică reglabilă:Performanța lui A* poate fi ajustată prin selectarea diferitelor funcții euristice. Euristice mai educate pot duce la o convergență mai rapidă și la noduri mai puțin extinse.Amplu cercetat:A* este un algoritm bine stabilit, cu zeci de ani de cercetare și aplicații practice. Au fost dezvoltate multe optimizări și variații, făcându-l un instrument de depanare fiabil și bine înțeles.Cautare pe internet:A* poate fi utilizat pentru căutarea căii bazată pe web, în ​​care algoritmul actualizează constant calea în funcție de schimbările din mediu sau de apariția noilor. Permite luarea de decizii în timp real în scenarii dinamice.

Dezavantajele algoritmului de căutare A* în inteligența artificială

Deși algoritmul de căutare A* (litera A) este o tehnică puternică și utilizată pe scară largă pentru rezolvarea problemelor de căutare a căii AI și de traversare a graficelor, are dezavantaje și limitări. Iată câteva dintre principalele dezavantaje ale algoritmului de căutare:

opacitatea tranziției css
    Precizie euristica:Performanța algoritmului A* depinde în mare măsură de acuratețea funcției euristice utilizată pentru a estima costul de la nodul curent la dacă euristica este inacceptabilă (nu supraestimează niciodată costul real) sau inconsecventă (satisfă inegalitatea triunghiului), A* este posibil să nu găsească o cale optimă sau să exploreze mai multe noduri decât este necesar, afectând eficiența și acuratețea acesteia.Folosirea memoriei:A* necesită ca toate nodurile vizitate să fie păstrate în memorie pentru a ține evidența căilor explorate. Utilizarea memoriei poate deveni uneori o problemă semnificativă, mai ales atunci când aveți de-a face cu un spațiu de căutare amplu sau cu resurse limitate de memorie.Complexitatea timpului:Deși A* este în general eficient, complexitatea sa de timp poate fi o preocupare pentru spații de căutare extinse sau grafice. În cel mai rău caz, A* poate dura exponențial mai mult pentru a găsi calea optimă dacă euristica este inadecvată pentru problemă.Gâtul de sticlă la destinație:În anumite scenarii, algoritmul A* trebuie să exploreze nodurile departe de destinație înainte de a ajunge în sfârșit în regiunea de destinație. Aceasta problema apare atunci când euristica trebuie să direcționeze eficient căutarea către obiectiv.Legarea costurilor:A* se confruntă cu dificultăți atunci când mai multe noduri au aceeași valoare f (suma costului real și a costului euristic). Strategia folosită poate afecta optimitatea și eficiența căii descoperite. Dacă nu este gestionat corect, poate duce la explorarea nodurilor inutile și la încetinirea algoritmului.Complexitatea în medii dinamice:În mediile dinamice în care costul marginilor sau nodurilor se poate modifica în timpul căutării, A* poate să nu fie potrivit, deoarece nu se adaptează bine la astfel de schimbări. Reformularea de la zero poate fi costisitoare din punct de vedere computațional, iar algoritmii D* (Dynamic A*) au fost proiectați pentru a rezolva acest lucru.Perfecțiunea în spațiu infinit:Este posibil ca A* să nu găsească o soluție în spațiul infinit de stări. În astfel de cazuri, poate rula pe termen nelimitat, explorând un număr din ce în ce mai mare de noduri fără a găsi o soluție. În ciuda acestor deficiențe, A* este încă un algoritm robust și utilizat pe scară largă, deoarece poate găsi în mod eficient căi optime în multe situații practice dacă funcția euristică este bine concepută și spațiul de căutare este gestionabil. Au fost propuse diverse variații și variante ale lui A* pentru a atenua unele dintre limitările sale.

Aplicații ale algoritmului de căutare A* în inteligența artificială

Algoritmul de căutare A* (litera A) este un algoritm de căutare robust și utilizat pe scară largă în inteligența artificială și informatică. Eficiența și optimitatea sa îl fac potrivit pentru diverse aplicații. Iată câteva aplicații tipice ale algoritmului de căutare A* în inteligența artificială:

    Pathfinding în jocuri:A* este adesea folosit în jocurile video pentru mișcarea personajelor, navigarea AI inamicului și găsirea celei mai scurte căi de la o locație la alta pe harta jocului. Capacitatea sa de a găsi calea optimă pe baza costurilor și euristicii îl face ideal pentru aplicații în timp real, cum ar fi jocurile.Robotică și vehicule autonome:A* este utilizat în robotică și navigație autonomă a vehiculelor pentru a planifica o rută optimă pentru roboții pentru a ajunge la o destinație, evitând obstacolele și luând în considerare costurile de teren. Acest lucru este crucial pentru o mișcare eficientă și sigură în mediile naturale.Rezolvarea labirintului:A* poate găsi în mod eficient calea cea mai scurtă printr-un labirint, făcându-l valoros în multe aplicații de rezolvare a labirintului, cum ar fi rezolvarea puzzle-urilor sau navigarea în structuri complexe.Planificarea rutei și navigarea:În sistemele GPS și aplicațiile de cartografiere, A* poate fi utilizat pentru a găsi ruta optimă între două puncte de pe o hartă, luând în considerare factori precum distanța, condițiile de trafic și topologia rețelei rutiere.Rezolvarea puzzle-ului:A* poate rezolva diverse puzzle-uri cu diagrame, cum ar fi puzzle-uri glisante, Sudoku și problema cu 8 puzzle-uri. Alocarea resurselor: În scenariile în care resursele trebuie alocate optim, A* poate ajuta la găsirea celei mai eficiente căi de alocare, minimizând costurile și maximizând eficiența.Rutare în rețea:A* poate fi folosit în rețelele de calculatoare pentru a găsi cea mai eficientă rută pentru pachetele de date de la o sursă la un nod de destinație.Procesarea limbajului natural (NLP):În unele sarcini NLP, A* poate genera răspunsuri coerente și contextuale prin căutarea unor posibile secvențe de cuvinte în funcție de probabilitatea și relevanța acestora.Planificarea traseului în robotică:A* poate fi folosit pentru a planifica traseul unui robot de la un punct la altul, luând în considerare diverse constrângeri, cum ar fi evitarea obstacolelor sau minimizarea consumului de energie.AI joc:A* este, de asemenea, folosit pentru a lua decizii inteligente pentru personajele non-jucatoare (NPC), cum ar fi determinarea celui mai bun mod de a atinge un obiectiv sau de a coordona mișcările într-un joc bazat pe echipă.

Acestea sunt doar câteva exemple despre modul în care algoritmul de căutare A* găsește aplicații în diverse domenii ale inteligenței artificiale. Flexibilitatea, eficiența și optimizarea acestuia îl fac un instrument valoros pentru multe probleme.

Program C pentru algoritmul de căutare A* în inteligența artificială

 #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++ pentru algoritmul de căutare A* în inteligența artificială

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

Explicaţie:

    Struct Node:Aceasta definește o structură de noduri care reprezintă o celulă grilă. Conține coordonatele x și y ale nodului, costul g de la nodul de pornire la acel nod, valoarea euristică h (costul estimat de la acel nod la nodul de destinație) și un pointer către
  1. nodul de pornire al căii.
  2. Calculați euristic:Această funcție calculează o euristică folosind distanța euclidiană dintre un nod și țintă AStarSearch: Această funcție rulează algoritmul de căutare A*. Acesta ia coordonatele de început și de destinație, o grilă și returnează un vector de perechi reprezentând coordonatele celei mai scurte căi de la început până la sfârșit.Primar:Funcția principală a programului preia de la utilizator grilele de intrare, originea și coordonatele țintă. Apoi apelează AStarSearch pentru a găsi calea cea mai scurtă și tipărește rezultatul. Struct Node: Aceasta definește o structură de nod care reprezintă o celulă grilă. Conține coordonatele x și y ale nodului, costul g de la nodul de pornire la acel nod, valoarea euristică h (costul estimat de la acel nod la nodul de destinație) și un pointer către nodul de pornire al căii.Calculați euristic:Această funcție calculează euristica folosind distanța euclidiană dintre un nod și țintă AStarSearch: Această funcție rulează algoritmul de căutare A*. Ia coordonatele de început și de destinație, o grilă și returnează un vector de perechi reprezentând coordonatele celei mai scurte căi de la început până la sfârșit.

Ieșire eșantion

 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 pentru algoritmul de căutare A* în inteligența artificială

 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* Complexitatea algoritmului de căutare în inteligența artificială

Algoritmul de căutare A* (pronunțat „A-star”) este un algoritm popular și utilizat pe scară largă de parcurgere a graficelor și de căutare a căilor în inteligența artificială. Găsirea celei mai scurte căi între două noduri într-un mediu bazat pe grafic sau grilă este de obicei obișnuită. Algoritmul combină elementele de căutare ale lui Dijkstra și cele mai lacome pentru a explora spațiul de căutare, asigurând în același timp optimitatea în mod eficient. Mai mulți factori determină complexitatea algoritmului de căutare A*. Dimensiunea graficului (noduri și margini): numărul de noduri și margini ale unui grafic afectează foarte mult complexitatea algoritmului. Mai multe noduri și margini înseamnă mai multe opțiuni posibile de explorat, ceea ce poate crește timpul de execuție al algoritmului.

Funcția euristică: A* folosește o funcție euristică (deseori desemnată h(n)) pentru a estima costul de la nodul curent la nodul destinație. Precizia acestei euristice afectează foarte mult eficiența căutării A*. O euristică bună poate ajuta la ghidarea căutării către un scop mai rapid, în timp ce o euristică proastă poate duce la căutări inutile.

    Structuri de date:A* menține două structuri de date principale: o listă deschisă (coadă de prioritate) și o listă închisă (sau grup vizitat). Eficiența acestor structuri de date, împreună cu implementarea aleasă (de exemplu, grămezi binare de coadă prioritară), afectează performanța algoritmului.Factorul de ramură:Numărul mediu de urmăritori pentru fiecare nod afectează numărul de noduri extinse în timpul căutării. Un factor de ramificare mai mare poate duce la mai multă explorare, care creșteOptimalitate și completitudine:A* garantează atât optimitatea (găsirea celei mai scurte căi), cât și completitudinea (găsirea unei soluții care există). Cu toate acestea, această garanție vine cu un compromis în ceea ce privește complexitatea computațională, deoarece algoritmul trebuie să exploreze căi diferite pentru o performanță optimă. În ceea ce privește complexitatea timpului, funcția euristică aleasă afectează A* în cel mai rău caz. Cu o euristică acceptată (care nu supraestimează niciodată costul real al atingerii obiectivului), A* extinde cele mai puține noduri dintre algoritmii de optimizare. Complexitatea timpului în cel mai rău caz a lui A * este exponențială în cel mai rău caz O(b ^ d), unde „b” este factorul de ramificare efectiv (numărul mediu de adepți pe nod) și „d” este optimul

În practică, totuși, A* are adesea performanțe semnificativ mai bune datorită influenței unei funcții euristice care ajută la ghidarea algoritmului către căi promițătoare. În cazul unei euristice bine concepute, factorul efectiv de ramificare este mult mai mic, ceea ce duce la o abordare mai rapidă a soluției optime.