logo

A* Algoritmus vyhľadávania v umelej inteligencii

Úvod do A* vyhľadávacieho algoritmu v AI

A* (vyslovuje sa 'A-star') je výkonný algoritmus na prechádzanie grafov a hľadanie cesty, ktorý sa široko používa v umelej inteligencii a počítačovej vede. Používa sa hlavne na nájdenie najkratšej cesty medzi dvoma uzlami v grafe vzhľadom na odhadované náklady na prechod z aktuálneho uzla do cieľového uzla. Hlavnou výhodou algoritmu je jeho schopnosť poskytnúť optimálnu cestu skúmaním grafu informovanejším spôsobom v porovnaní s tradičnými vyhľadávacími algoritmami, ako je Dijkstrov algoritmus.

Algoritmus A* kombinuje výhody dvoch ďalších vyhľadávacích algoritmov: Dijkstrov algoritmus a Greedy Best-First Search. Podobne ako algoritmus Dijkstra, aj A* zaisťuje, že nájdená cesta je čo najkratšia, no robí to efektívnejšie tým, že svoje vyhľadávanie nasmeruje pomocou heuristiky podobnej vyhľadávaniu Greedy Best-First Search. Heuristická funkcia, označená h(n), odhaduje náklady na prechod z akéhokoľvek daného uzla n do cieľového uzla.

Hlavnou myšlienkou A* je vyhodnotiť každý uzol na základe dvoch parametrov:

plná forma
    g(n):skutočné náklady na prechod z počiatočného uzla do uzla n. Predstavuje súčet nákladov uzla n výstupných hrán.h(n):Heuristické náklady (známe aj ako „náklady na odhad“) z uzla n do cieľového uzla n. Táto heuristická funkcia špecifická pre daný problém musí byť prijateľná, čo znamená, že nikdy nepreceňuje skutočné náklady na dosiahnutie cieľa. Vyhodnocovacia funkcia uzla n je definovaná ako f(n) = g(n) h(n).

Algoritmus A* vyberá uzly, ktoré sa majú preskúmať, na základe najnižšej hodnoty f(n), pričom uprednostňuje uzly s najnižšími odhadovanými celkovými nákladmi na dosiahnutie cieľa. Algoritmus A* funguje:

  1. Vytvorte otvorený zoznam nájdených, ale nepreskúmaných uzlov.
  2. Vytvorte uzavretý zoznam, ktorý bude obsahovať už preskúmané uzly.
  3. Pridajte počiatočný uzol do otvoreného zoznamu s počiatočnou hodnotou g
  4. Opakujte nasledujúce kroky, kým nebude otvorený zoznam prázdny alebo kým nedosiahnete cieľový uzol:
    1. Nájdite uzol s najmenšou f-hodnotou (t. j. uzol s vedľajšou g(n) h(n)) v otvorenom zozname.
    2. Presuňte vybraný uzol z otvoreného zoznamu do zatvoreného zoznamu.
    3. Vytvorte všetkých platných potomkov vybratého uzla.
    4. Pre každého následníka vypočíta jeho g-hodnotu ako súčet g hodnoty aktuálneho uzla a nákladov na presun z aktuálneho uzla do nástupníckeho uzla. Aktualizujte g-hodnotu sledovača, keď sa nájde lepšia cesta.
    5. Ak nasledovník nie je v otvorenom zozname, pridajte ho k vypočítanej g-hodnote a vypočítajte jej h-hodnotu. Ak sa už nachádza v otvorenom zozname, aktualizujte jeho hodnotu g, ak je nová cesta lepšia.
    6. Opakujte cyklus. Algoritmus A* sa ukončí, keď sa dosiahne cieľový uzol alebo keď sa vyprázdni otvorený zoznam, čo neindikuje žiadne cesty od počiatočného uzla k cieľovému uzlu. Vyhľadávací algoritmus A* je široko používaný v rôznych oblastiach, ako je robotika, videohry, sieťové smerovanie a dizajnové problémy, pretože je efektívny a dokáže nájsť optimálne cesty v grafoch alebo sieťach.

Výber vhodnej a prijateľnej heuristickej funkcie je však nevyhnutný na to, aby algoritmus fungoval správne a poskytoval optimálne riešenie.

Informované vyhľadávacie algoritmy

História vyhľadávacieho algoritmu A* v umelej inteligencii

Vyvinuli ho Peter Hart, Nils Nilsson a Bertram Raphael v Stanford Research Institute (teraz SRI International) ako rozšírenie Dijkstrovho algoritmu a iných vyhľadávacích algoritmov tej doby. A* bol prvýkrát publikovaný v roku 1968 a rýchlo si získal uznanie pre svoj význam a účinnosť v komunitách umelej inteligencie a informatiky. Tu je stručný prehľad najdôležitejších míľnikov v histórii vyhľadávacieho algoritmu A*:

    Skoré vyhľadávacie algoritmy:Pred vývojom A* existovali rôzne algoritmy na vyhľadávanie grafov, vrátane hĺbkového vyhľadávania (DFS) a šírky prvého vyhľadávania (BFS). Aj keď tieto algoritmy pomohli nájsť cesty, nezaručili optimálnosť a nezohľadnili heuristiku pri hľadaníDijkstrov algoritmus:V roku 1959 holandský počítačový vedec Edsger W. Dijkstra predstavil Dijkstrov algoritmus, ktorý našiel najkratšiu cestu vo váženom grafe s nezápornými váhami hrán. Dijkstrov algoritmus bol efektívny, ale pre svoju vyčerpávajúcu povahu mal obmedzenia pri použití na väčších grafoch resp.Informované vyhľadávanie:Znalostné vyhľadávacie algoritmy (tiež známe ako heuristické vyhľadávanie) boli vyvinuté na začlenenie heuristických informácií, ako sú odhadované náklady, na efektívne vedenie procesu vyhľadávania. Greedy Best-First Search bol jedným z takýchto algoritmov, ale nezaručoval optimálnosť na nájdenie najkratšej cesty.A* vývoj:V roku 1968 Peter Hart, Nils Nilsson a Bertram Raphael predstavili algoritmus A* ako kombináciu Dijkstrovho algoritmu a Greedy Best-First Search. A* použil heuristickú funkciu na odhadnutie nákladov z aktuálneho uzla do cieľového uzla ich kombináciou so skutočnými nákladmi na dosiahnutie aktuálneho uzla. To umožnilo A* preskúmať graf vedomejšie, vyhnúť sa zbytočným cestám a zaručiť optimálne riešenie.Spravodlivosť a dokonalosť:Autori A* ukázali, že algoritmus je dokonalý (vždy nájde riešenie, ak nejaké existuje) a optimálny (nájde najkratšiu cestu) za určitých podmienok.Široké prijatie a pokrok:A* si rýchlo získal popularitu v komunitách AI a IT vďaka svojej efektívnosti a výskumníci a vývojári rozšírili a aplikovali algoritmus A* na rôzne oblasti vrátane robotiky, videohier, inžinierstva a sieťového smerovania. V priebehu rokov bolo navrhnutých niekoľko variácií a optimalizácií A* algoritmu, ako napríklad Incremental A* a Parallel A*. Dnes je vyhľadávací algoritmus A* stále základným a široko používaným algoritmom v oblasti umelej inteligencie a prechodu grafov. Naďalej zohráva kľúčovú úlohu v rôznych aplikáciách a oblastiach výskumu. Jeho vplyv na umelú inteligenciu a jeho príspevok k problémom s hľadaním ciest a optimalizáciou z neho urobili základný kameň algoritmu vo výskume inteligentných systémov.

Ako funguje vyhľadávací algoritmus A* v umelej inteligencii?

Algoritmus vyhľadávania A* (vyslovuje sa ako „písmeno A“) je populárny a široko používaný algoritmus prechodu grafov v umelej inteligencii a počítačovej vede. Používa sa na nájdenie najkratšej cesty od počiatočného uzla do cieľového uzla vo váženom grafe. A* je informovaný vyhľadávací algoritmus, ktorý využíva heuristiku na efektívne vedenie vyhľadávania. Algoritmus vyhľadávania A* funguje takto:

Algoritmus začína prioritným frontom na uloženie uzlov, ktoré sa majú preskúmať. Tiež vytvára inštanciu dvoch dátových štruktúr g(n): Cena doteraz najkratšej cesty od počiatočného uzla do uzla n a h(n), odhadovaná cena (heuristika) z uzla n do cieľového uzla. Často je to rozumná heuristika, čo znamená, že nikdy nepreceňuje skutočné náklady na dosiahnutie cieľa. Vložte počiatočný uzol do prioritného frontu a nastavte jeho g(n) na 0. Ak prioritný front nie je prázdny, odstráňte uzol s najnižšou f(n) z prioritného frontu. f(n) = g(n) h(n). Ak je odstránený uzol cieľovým uzlom, algoritmus sa skončí a nájde sa cesta. V opačnom prípade rozbaľte uzol a vytvorte jeho susedov. Pre každý susedný uzol vypočítajte jeho počiatočnú hodnotu g(n), ktorá je súčtom hodnoty g aktuálneho uzla a nákladov na presun z aktuálneho uzla do susedného uzla. Ak susedný uzol nie je v poradí priority alebo pôvodná hodnota g(n) je menšia ako jeho aktuálna hodnota g, aktualizujte jeho hodnotu g a nastavte jeho nadradený uzol na aktuálny uzol. Vypočítajte hodnotu f(n) zo susedného uzla a pridajte ju do prioritného frontu.

Ak sa cyklus skončí bez nájdenia cieľového uzla, graf nemá žiadnu cestu od začiatku do konca. Kľúčom k efektívnosti A* je použitie heuristickej funkcie h(n), ktorá poskytuje odhad zostávajúcich nákladov na dosiahnutie cieľa ktoréhokoľvek uzla. Kombináciou skutočných nákladov g (n) s heuristickými nákladmi h (n) algoritmus efektívne skúma sľubné cesty, pričom uprednostňuje uzly, ktoré pravdepodobne vedú k najkratšej ceste. Je dôležité poznamenať, že účinnosť algoritmu A* je veľmi závislá od výberu heuristickej funkcie. Prijateľná heuristika zaisťuje, že algoritmus vždy nájde najkratšiu cestu, ale informovanejšia a presnejšia heuristika môže viesť k rýchlejšej konvergencii a zmenšeniu priestoru na vyhľadávanie.

Výhody A* vyhľadávacieho algoritmu v umelej inteligencii

Algoritmus vyhľadávania A* ponúka niekoľko výhod v scenároch umelej inteligencie a riešenia problémov:

    Optimálne riešenie:A* zabezpečuje nájdenie optimálnej (najkratšej) cesty od počiatočného uzla do cieľového uzla vo váženom grafe s prijateľnou heuristickou funkciou. Táto optimalita je rozhodujúcou výhodou v mnohých aplikáciách, kde je nevyhnutné nájsť najkratšiu cestu.Úplnosť:Ak riešenie existuje, A* ho nájde za predpokladu, že graf nemá nekonečnú cenu Táto vlastnosť úplnosti zabezpečuje, že A* môže využiť riešenie, ak existuje.Účinnosť:A* je efektívne, ak sa používa efektívna a prijateľná heuristická funkcia. Heuristika vedie vyhľadávanie k cieľu tým, že sa zameriava na sľubné cesty a vyhýba sa zbytočnému skúmaniu, vďaka čomu je A* efektívnejšia ako nevedomé vyhľadávacie algoritmy, ako je vyhľadávanie do šírky alebo vyhľadávanie do hĺbky.Všestrannosť:A* je široko použiteľný v rôznych problémových oblastiach, vrátane hľadania cesty, plánovania trasy, robotiky, vývoja hier a ďalších. A* možno použiť na efektívne nájdenie optimálnych riešení, pokiaľ je možné definovať zmysluplnú heuristiku.Optimalizované vyhľadávanie:A* zachováva poradie priority na výber uzlov s menšou hodnotou f(n) (g(n) a h(n)) na expanziu. To mu umožňuje najskôr preskúmať sľubné cesty, čo znižuje priestor na vyhľadávanie a vedie k rýchlejšiemu zbližovaniu.Účinnosť pamäte:Na rozdiel od niektorých iných vyhľadávacích algoritmov, ako je vyhľadávanie do šírky, A* ukladá do prioritného frontu iba obmedzený počet uzlov, čo umožňuje efektívne využitie pamäte, najmä pri veľkých grafoch.Laditeľná heuristika:Výkon A* možno doladiť výberom rôznych heuristických funkcií. Vzdelanejšia heuristika môže viesť k rýchlejšej konvergencii a menej rozšíreným uzlom.Dôkladne preskúmané:A* je dobre zavedený algoritmus s desaťročiami výskumu a praktickými aplikáciami. Bolo vyvinutých mnoho optimalizácií a variácií, vďaka čomu je spoľahlivý a dobre pochopený nástroj na riešenie problémov.Vyhľadávanie na webe:A* je možné použiť na vyhľadávanie ciest na webe, kde algoritmus neustále aktualizuje cestu podľa zmien prostredia alebo vzhľadu nového Umožňuje rozhodovanie v reálnom čase v dynamických scenároch.

Nevýhody A* vyhľadávacieho algoritmu v umelej inteligencii

Aj keď je vyhľadávací algoritmus A* (písmeno A) široko používanou a výkonnou technikou na riešenie problémov s hľadaním cesty AI a prechodom grafov, má nevýhody a obmedzenia. Tu sú niektoré z hlavných nevýhod vyhľadávacieho algoritmu:

    Heuristická presnosť:Výkon algoritmu A* do značnej miery závisí od presnosti heuristickej funkcie použitej na odhadnutie nákladov od aktuálneho uzla po Ak je heuristika neprijateľná (nikdy neprehodnocuje skutočné náklady) alebo nekonzistentná (vyhovuje trojuholníkovej nerovnosti), A* nemusí nájsť optimálnu cestu alebo môže preskúmať viac uzlov, ako je potrebné, čo ovplyvňuje jeho účinnosť a presnosť.Využitie pamäte:A* vyžaduje, aby sa všetky navštívené uzly uchovávali v pamäti, aby bolo možné sledovať preskúmané cesty. Využitie pamäte sa môže niekedy stať závažným problémom, najmä ak máte dostatok miesta na vyhľadávanie alebo obmedzené pamäťové zdroje.Časová zložitosť:Hoci A* je vo všeobecnosti efektívny, jeho časová zložitosť môže byť problémom pre veľké vyhľadávacie priestory alebo grafy. V najhoršom prípade môže A* trvať exponenciálne dlhšie, kým nájde optimálnu cestu, ak je heuristika pre daný problém nevhodná.Úzke miesto v cieli:V špecifických scenároch musí algoritmus A* preskúmať uzly ďaleko od cieľa predtým, ako konečne dosiahne cieľovú oblasť. Tento problém nastáva, keď heuristika potrebuje včas efektívne nasmerovať vyhľadávanie k cieľu.Viazanie nákladov:A* čelí ťažkostiam, keď viaceré uzly majú rovnakú f-hodnotu (súčet skutočných nákladov a heuristických nákladov). Použitá stratégia môže ovplyvniť optimálnosť a efektivitu objavenej cesty. Ak sa nespracuje správne, môže to viesť k tomu, že sa budú skúmať zbytočné uzly a spomalí sa algoritmus.Zložitosť v dynamických prostrediach:V dynamických prostrediach, kde sa cena hrán alebo uzlov môže počas vyhľadávania meniť, nemusí byť A* vhodné, pretože sa takýmto zmenám dobre neprispôsobuje. Reformulácia od začiatku môže byť výpočtovo nákladná a algoritmy D* (Dynamic A*) boli navrhnuté tak, aby to vyriešiliDokonalosť v nekonečnom priestore:A* nemusí nájsť riešenie v nekonečnom stavovom priestore. V takýchto prípadoch môže bežať donekonečna a skúmať stále väčší počet uzlov bez nájdenia riešenia. Napriek týmto nedostatkom je A* stále robustným a široko používaným algoritmom, pretože dokáže efektívne nájsť optimálne cesty v mnohých praktických situáciách, ak je heuristická funkcia dobre navrhnutá a vyhľadávací priestor je zvládnuteľný. Boli navrhnuté rôzne variácie a varianty A* na zmiernenie niektorých jeho obmedzení.

Aplikácie A* vyhľadávacieho algoritmu v umelej inteligencii

Vyhľadávací algoritmus A* (písmeno A) je široko používaný a robustný algoritmus na vyhľadávanie ciest v umelej inteligencii a počítačovej vede. Vďaka svojej účinnosti a optimálnosti je vhodný pre rôzne aplikácie. Tu je niekoľko typických aplikácií vyhľadávacieho algoritmu A* v umelej inteligencii:

    Hľadanie cesty v hrách:A* sa často používa vo videohrách na pohyb postáv, nepriateľskú AI navigáciu a nájdenie najkratšej cesty z jedného miesta na druhé na hernej mape. Jeho schopnosť nájsť optimálnu cestu na základe nákladov a heuristiky ho robí ideálnym pre aplikácie v reálnom čase, ako sú hry.Robotika a autonómne vozidlá:A* sa používa v robotike a navigácii autonómnych vozidiel na plánovanie optimálnej trasy pre roboty na dosiahnutie cieľa, vyhýbanie sa prekážkam a zvažovanie nákladov na terén. To je kľúčové pre efektívny a bezpečný pohyb v prírodnom prostredí.Riešenie bludiska:A* dokáže efektívne nájsť najkratšiu cestu cez bludisko, vďaka čomu je cenný v mnohých aplikáciách na riešenie bludísk, ako je riešenie hádaniek alebo navigácia v zložitých štruktúrach.Plánovanie trasy a navigácia:V systémoch GPS a mapových aplikáciách možno A* použiť na nájdenie optimálnej trasy medzi dvoma bodmi na mape, berúc do úvahy faktory, ako je vzdialenosť, dopravné podmienky a topológia cestnej siete.Riešenie hádaniek:A* dokáže vyriešiť rôzne rébusy, ako sú posuvné rébusy, sudoku a problém s 8 rébusmi. Alokácia zdrojov: V scenároch, kde musia byť zdroje optimálne alokované, môže A* pomôcť nájsť najefektívnejšiu alokáciu, minimalizovať náklady a maximalizovať efektivitu.Smerovanie siete:A* možno použiť v počítačových sieťach na nájdenie najefektívnejšej trasy pre dátové pakety zo zdroja do cieľového uzla.Spracovanie prirodzeného jazyka (NLP):V niektorých úlohách NLP môže A* generovať koherentné a kontextové odpovede hľadaním možných sekvencií slov na základe ich pravdepodobnosti a relevantnosti.Plánovanie cesty v robotike:A* možno použiť na plánovanie cesty robota z jedného bodu do druhého, pričom sa berú do úvahy rôzne obmedzenia, ako je vyhýbanie sa prekážkam alebo minimalizácia spotreby energie.AI hry:A* sa tiež používa na inteligentné rozhodnutia pre postavy, ktoré nie sú hráčmi (NPC), ako napríklad určenie najlepšieho spôsobu dosiahnutia cieľa alebo koordinácie pohybov v tímovej hre.

Toto je len niekoľko príkladov toho, ako vyhľadávací algoritmus A* nachádza uplatnenie v rôznych oblastiach umelej inteligencie. Jeho flexibilita, efektívnosť a optimalizácia z neho robia cenný nástroj na riešenie mnohých problémov.

C program pre A* vyhľadávací algoritmus v umelej inteligencii

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

C++ program pre A* vyhľadávací algoritmus v umelej inteligencii

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

Vysvetlenie:

xor v jazyku Java
    Uzol štruktúry:Toto definuje štruktúru uzla, ktorá predstavuje bunku mriežky. Obsahuje súradnice x a y uzla, cenu g od počiatočného uzla do tohto uzla, heuristickú hodnotu h (odhadované náklady z tohto uzla do cieľového uzla) a ukazovateľ na
  1. počiatočný uzol cesty.
  2. Vypočítajte heuristiku:Táto funkcia vypočíta heuristiku pomocou euklidovskej vzdialenosti medzi uzlom a cieľom AStarSearch: Táto funkcia spúšťa algoritmus vyhľadávania A*. Berie počiatočné a cieľové súradnice, mriežku a vracia vektor párov reprezentujúcich súradnice najkratšej cesty od začiatku do konca.Primárny:Hlavná funkcia programu preberá vstupné mriežky, počiatočné a cieľové súradnice od používateľa. Potom zavolá AStarSearch, aby našiel najkratšiu cestu a vytlačí výsledok. Struct Node: Definuje štruktúru uzla, ktorá predstavuje bunku mriežky. Obsahuje súradnice x a y uzla, cenu g od počiatočného uzla k tomuto uzlu, heuristickú hodnotu h (odhadovaná cena z tohto uzla do cieľového uzla) a ukazovateľ na počiatočný uzol cesty.Vypočítajte heuristiku:Táto funkcia vypočítava heuristiku pomocou euklidovskej vzdialenosti medzi uzlom a cieľom AStarSearch: Táto funkcia spúšťa vyhľadávací algoritmus A*. Berie počiatočné a cieľové súradnice, mriežku a vracia vektor párov reprezentujúcich súradnice najkratšej cesty od začiatku do konca.

Ukážkový výstup

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

Java program pre A* vyhľadávací algoritmus v umelej inteligencii

 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* Zložitosť vyhľadávacieho algoritmu v umelej inteligencii

Algoritmus vyhľadávania A* (vyslovuje sa ako „A-star“) je populárny a široko používaný algoritmus prechádzania grafov a vyhľadávania ciest v umelej inteligencii. Nájdenie najkratšej cesty medzi dvoma uzlami v prostredí grafu alebo mriežky je zvyčajne bežné. Algoritmus kombinuje prvky vyhľadávania Dijkstra a nenásytné prvky best-first, aby preskúmal priestor vyhľadávania a zároveň efektívne zabezpečil optimálnosť. Zložitosť vyhľadávacieho algoritmu A* určuje niekoľko faktorov. Veľkosť grafu (uzly a hrany): Počet uzlov a hrán grafu výrazne ovplyvňuje zložitosť algoritmu. Viac uzlov a hrán znamená viac možností na preskúmanie, čo môže predĺžiť čas vykonania algoritmu.

Heuristická funkcia: A* používa heuristickú funkciu (často označovanú h(n)) na odhadnutie nákladov z aktuálneho uzla do cieľového uzla. Presnosť tejto heuristiky výrazne ovplyvňuje účinnosť vyhľadávania A*. Dobrá heuristika môže pomôcť rýchlejšie nasmerovať vyhľadávanie k cieľu, zatiaľ čo zlá heuristika môže viesť k zbytočnému hľadaniu.

    Dátové štruktúry:A* udržiava dve štruktúry hlavných údajov: otvorený zoznam (prioritný front) a uzavretý zoznam (alebo navštívená oblasť). Efektívnosť týchto dátových štruktúr spolu so zvolenou implementáciou (napr. binárne haldy prioritného frontu) ovplyvňuje výkon algoritmu.Faktor pobočky:Priemerný počet sledovateľov pre každý uzol ovplyvňuje počet uzlov rozšírených počas vyhľadávania. Vyšší faktor vetvenia môže viesť k väčšiemu prieskumu, ktorý sa zvyšujeOptimálnosť a úplnosť:A* zaručuje optimálnosť (nájdenie najkratšej cesty) aj úplnosť (nájdenie existujúceho riešenia). Táto záruka však prichádza s kompromisom v oblasti výpočtovej zložitosti, pretože algoritmus musí preskúmať rôzne cesty pre optimálny výkon. Čo sa týka časovej zložitosti, zvolená heuristická funkcia ovplyvňuje A* v najhoršom prípade. S akceptovanou heuristikou (ktorá nikdy nepreceňuje skutočné náklady na dosiahnutie cieľa), A* rozširuje najmenší počet uzlov medzi optimalizačnými algoritmami. Časová zložitosť A * v najhoršom prípade je exponenciálna v najhoršom prípade O(b ^ d), kde „b“ je efektívny faktor vetvenia (priemerný počet nasledovníkov na uzol) a „d“ je optimálny

V praxi však A* často funguje výrazne lepšie vďaka vplyvu heuristickej funkcie, ktorá pomáha viesť algoritmus sľubnými cestami. V prípade dobre navrhnutej heuristiky je efektívny faktor vetvenia oveľa menší, čo vedie k rýchlejšiemu prístupu k optimálnemu riešeniu.