logo

A* Algoritam pretraživanja u umjetnoj inteligenciji

Uvod u A* algoritam pretraživanja u AI

A* (izgovara se 'A-zvijezda') moćan je algoritam za obilaženje grafa i pronalaženje puta koji se široko koristi u umjetnoj inteligenciji i računalnim znanostima. Uglavnom se koristi za pronalaženje najkraćeg puta između dva čvora u grafu, s obzirom na procijenjeni trošak dolaska od trenutnog čvora do odredišnog čvora. Glavna prednost algoritma je njegova sposobnost pružanja optimalnog puta istraživanjem grafa na informiraniji način u usporedbi s tradicionalnim algoritmima pretraživanja kao što je Dijkstrin algoritam.

Algoritam A* kombinira prednosti dva druga algoritma pretraživanja: Dijkstrinog algoritma i Greedy Best-First Search. Poput Dijkstrinog algoritma, A* osigurava da je pronađeni put što kraći, ali to čini učinkovitije usmjeravanjem svoje pretrage kroz heuristiku sličnu Greedy Best-First Search. Heuristička funkcija, označena h(n), procjenjuje trošak dolaska od bilo kojeg danog čvora n do odredišnog čvora.

Glavna ideja A* je procijeniti svaki čvor na temelju dva parametra:

pokušaj catch blok u Javi
    g(n):stvarni trošak od početnog čvora do čvora n. Predstavlja zbroj troškova izlaznih rubova čvora n.h(n):Heuristički trošak (također poznat kao 'trošak procjene') od čvora n do odredišnog čvora n. Ova heuristička funkcija specifična za problem mora biti prihvatljiva, što znači da nikada ne precjenjuje stvarnu cijenu postizanja cilja. Funkcija evaluacije čvora n definirana je kao f(n) = g(n) h(n).

Algoritam A* odabire čvorove koje treba istražiti na temelju najniže vrijednosti f(n), dajući prednost čvorovima s najnižim procijenjenim ukupnim troškom za postizanje cilja. Algoritam A* radi:

  1. Napravite otvoreni popis pronađenih, ali neistraženih čvorova.
  2. Napravite zatvoreni popis za već istražene čvorove.
  3. Dodajte početni čvor na otvorenu listu s početnom vrijednošću g
  4. Ponavljajte sljedeće korake dok otvoreni popis ne bude prazan ili dok ne dođete do ciljnog čvora:
    1. Na otvorenom popisu pronađite čvor s najmanjom f-vrijednošću (tj. čvor s manjim g(n) h(n)).
    2. Premjesti odabrani čvor s otvorenog popisa na zatvoreni popis.
    3. Stvorite sve valjane potomke odabranog čvora.
    4. Za svakog nasljednika izračunajte njegovu g-vrijednost kao zbroj g vrijednosti trenutnog čvora i troška premještanja od trenutnog čvora do čvora nasljednika. Ažurirajte g-vrijednost alata za praćenje kada se pronađe bolji put.
    5. Ako sljedbenik nije na otvorenom popisu, dodajte ga s izračunatom g-vrijednošću i izračunajte njegovu h-vrijednost. Ako je već na otvorenom popisu, ažurirajte njegovu g vrijednost ako je novi put bolji.
    6. Ponovite ciklus. Algoritam A* završava kada se dosegne ciljni čvor ili kada se otvorena lista isprazni, pokazujući da nema puta od početnog čvora do ciljnog čvora. Algoritam pretraživanja A* naširoko se koristi u raznim područjima kao što su robotika, video igre, mrežno usmjeravanje i problemi dizajna jer je učinkovit i može pronaći optimalne staze u grafikonima ili mrežama.

Međutim, bitan je odabir prikladne i prihvatljive heurističke funkcije kako bi algoritam ispravno radio i pružio optimalno rješenje.

Informirani algoritmi pretraživanja

Povijest A* algoritma pretraživanja u umjetnoj inteligenciji

Razvili su ga Peter Hart, Nils Nilsson i Bertram Raphael na Stanford Research Institute (sada SRI International) kao proširenje Dijkstrinog algoritma i drugih algoritama pretraživanja tog vremena. A* je prvi put objavljen 1968. i brzo je stekao priznanje za svoju važnost i učinkovitost u zajednicama umjetne inteligencije i računalnih znanosti. Evo kratkog pregleda najkritičnijih prekretnica u povijesti algoritma pretraživanja A*:

    Algoritmi ranog pretraživanja:Prije razvoja A* postojali su različiti algoritmi pretraživanja grafova, uključujući pretraživanje prvo u dubinu (DFS) i pretraživanje prvo u širinu (BFS). Iako su ti algoritmi pomogli u pronalaženju putova, nisu jamčili optimalnost niti uzimali u obzir heuristiku za vođenje pretraživanjaDijkstrin algoritam:Godine 1959. nizozemski računalni znanstvenik Edsger W. Dijkstra predstavio je Dijkstrin algoritam, koji je pronašao najkraći put u težinskom grafu s nenegativnim težinama rubova. Dijkstrin algoritam bio je učinkovit, ali je zbog svoje iscrpne prirode imao ograničenja kada se koristio na većim grafovima iliInformirana pretraga:Algoritmi pretraživanja temeljeni na znanju (također poznati kao heurističko pretraživanje) razvijeni su za uključivanje heurističkih informacija, kao što su procijenjeni troškovi, za učinkovito vođenje procesa pretraživanja. Greedy Best-First Search bio je jedan takav algoritam, ali nije jamčio optimalnost za pronalaženje najkraćeg puta.A* razvoj:Godine 1968. Peter Hart, Nils Nilsson i Bertram Raphael predstavili su algoritam A* kao kombinaciju Dijkstrinog algoritma i Greedy Best-First Search. A* je koristio heurističku funkciju za procjenu troška od trenutnog čvora do odredišnog čvora kombinirajući ga sa stvarnim troškom dosezanja trenutnog čvora. To je A* omogućilo da svjesnije istraži graf, izbjegavajući nepotrebne staze i jamčeći optimalno rješenje.Ispravnost i savršenstvo:Autori A* su pokazali da je algoritam savršen (uvijek pronalazi rješenje ako ono postoji) i optimalan (pronalazi najkraći put) pod određenim uvjetima.Široko usvajanje i napredak:A* je brzo stekao popularnost u AI i IT zajednicama zbog svoje učinkovitosti, a istraživači i programeri su proširili i primijenili algoritam A* na razna područja, uključujući robotiku, video igre, inženjering i mrežno usmjeravanje. Tijekom godina predloženo je nekoliko varijacija i optimizacija algoritma A*, kao što su Inkrementalni A* i Paralelni A*. Danas je algoritam pretraživanja A* još uvijek temeljni i široko korišten algoritam u umjetnoj inteligenciji i obilasku grafova. I dalje igra bitnu ulogu u raznim primjenama i istraživačkim poljima. Njegov utjecaj na umjetnu inteligenciju i njegov doprinos pronalaženju puta i problemima optimizacije učinili su ga algoritmom temeljcem u istraživanju inteligentnih sustava.

Kako algoritam pretraživanja A* radi u umjetnoj inteligenciji?

Algoritam pretraživanja A* (izgovara se 'slovo A') popularan je i široko korišten algoritam za obilaženje grafova u umjetnoj inteligenciji i računalnim znanostima. Koristi se za pronalaženje najkraćeg puta od početnog čvora do odredišnog čvora u ponderiranom grafu. A* je informirani algoritam pretraživanja koji koristi heuristiku za učinkovito vođenje pretraživanja. Algoritam pretraživanja A* radi na sljedeći način:

Algoritam počinje s prioritetnim redom za pohranjivanje čvorova koje treba istražiti. Također instancira dvije podatkovne strukture g(n): trošak najkraćeg puta do sada od početnog čvora do čvora n i h(n), procijenjeni trošak (heuristika) od čvora n do odredišnog čvora. Često je to razumna heuristika, što znači da nikada ne precjenjuje stvarnu cijenu postizanja cilja. Stavite početni čvor u red čekanja prioriteta i postavite njegov g(n) na 0. Ako red čekanja prioriteta nije prazan, uklonite čvor s najnižim f(n) iz reda čekanja prioriteta. f(n) = g(n) h(n). Ako je izbrisani čvor odredišni čvor, algoritam završava i put se pronalazi. U suprotnom, proširite čvor i stvorite njegove susjede. Za svaki susjedni čvor izračunajte njegovu početnu g(n) vrijednost, koja je zbroj g vrijednosti trenutnog čvora i troška premještanja od trenutnog čvora do susjednog čvora. Ako susjedni čvor nije u redoslijedu prioriteta ili je originalna g(n) vrijednost manja od trenutne g vrijednosti, ažurirajte njegovu g vrijednost i postavite njegov nadređeni čvor na trenutni čvor. Izračunajte vrijednost f(n) iz susjednog čvora i dodajte je u red prioriteta.

Ako ciklus završi bez pronalaženja odredišnog čvora, graf nema putanju od početka do kraja. Ključ učinkovitosti A* je njegova upotreba heurističke funkcije h(n) koja daje procjenu preostalih troškova postizanja cilja bilo kojeg čvora. Kombinirajući stvarni trošak g (n) s heurističkim troškom h (n), algoritam učinkovito istražuje obećavajuće putove, dajući prioritet čvorovima koji će vjerojatno dovesti do najkraćeg puta. Važno je napomenuti da učinkovitost A* algoritma uvelike ovisi o izboru heurističke funkcije. Prihvatljive heuristike osiguravaju da algoritam uvijek pronađe najkraći put, ali informiranija i preciznija heuristika može dovesti do brže konvergencije i smanjenog prostora za pretraživanje.

Prednosti A* algoritma pretraživanja u umjetnoj inteligenciji

Algoritam pretraživanja A* nudi nekoliko prednosti u scenarijima umjetne inteligencije i rješavanja problema:

    Optimalno rješenje:A* osigurava pronalaženje optimalnog (najkraćeg) puta od početnog čvora do odredišnog čvora u ponderiranom grafu s obzirom na prihvatljivu heurističku funkciju. Ova optimalnost je odlučujuća prednost u mnogim primjenama gdje je pronalaženje najkraćeg puta bitno.Potpunost:Ako rješenje postoji, A* će ga pronaći, pod uvjetom da graf nema beskonačnu cijenu. Ovo svojstvo potpunosti osigurava da A* može iskoristiti rješenje ako ono postoji.Učinkovitost:A* je učinkovit ako se koristi učinkovita i prihvatljiva heuristička funkcija. Heuristika vodi pretragu do cilja usredotočujući se na obećavajuće putove i izbjegavajući nepotrebno istraživanje, čineći A* učinkovitijim od algoritama nesvjesnog pretraživanja kao što je pretraživanje u širinu ili pretraživanje u dubinu.Svestranost:A* je široko primjenjiv na razna problematična područja, uključujući pronalaženje puta, planiranje rute, robotiku, razvoj igara i još mnogo toga. A* se može koristiti za učinkovito pronalaženje optimalnih rješenja sve dok se može definirati smislena heuristika.Optimizirano pretraživanje:A* održava redoslijed prioriteta za odabir čvorova s ​​manjom f(n) vrijednošću (g(n) i h(n)) za proširenje. To mu omogućuje da prvo istraži obećavajuće putove, što smanjuje prostor za pretraživanje i dovodi do brže konvergencije.Učinkovitost memorije:Za razliku od nekih drugih algoritama pretraživanja, kao što je pretraživanje u širinu, A* pohranjuje samo ograničen broj čvorova u prioritetnom redu čekanja, što ga čini memorijski učinkovitim, posebno za velike grafove.Podesiva heuristika:Izvedba A* može se fino podesiti odabirom različitih heurističkih funkcija. Obrazovanija heuristika može dovesti do brže konvergencije i manje proširenih čvorova.Opsežno istraženo:A* je dobro uspostavljen algoritam s desetljećima istraživanja i praktičnih primjena. Razvijene su mnoge optimizacije i varijacije, što ga čini pouzdanim i dobro razumljivim alatom za rješavanje problema.Internet pretraga:A* se može koristiti za web-bazirano pretraživanje staze, gdje algoritam stalno ažurira stazu u skladu s promjenama u okruženju ili pojavom novih. Omogućuje donošenje odluka u stvarnom vremenu u dinamičkim scenarijima.

Nedostaci A* algoritma pretraživanja u umjetnoj inteligenciji

Iako je algoritam pretraživanja A* (slovo A) naširoko korištena i moćna tehnika za rješavanje problema pronalaženja putanje pomoću umjetne inteligencije i obilaženja grafa, ima nedostatke i ograničenja. Evo nekih od glavnih nedostataka algoritma pretraživanja:

    Heuristička točnost:Izvedba algoritma A* uvelike ovisi o točnosti heurističke funkcije koja se koristi za procjenu troška od trenutnog čvora do čvora. Ako je heuristika neprihvatljiva (nikada ne precjenjuje stvarni trošak) ili nedosljedna (zadovoljava nejednakost trokuta), A* možda neće pronaći optimalan put ili može istražiti više čvorova nego što je potrebno, što utječe na njegovu učinkovitost i točnost.Upotreba memorije:A* zahtijeva da se svi posjećeni čvorovi čuvaju u memoriji kako bi se pratili istraženi putovi. Korištenje memorije ponekad može postati značajan problem, posebno kada se radi o velikom prostoru za pretraživanje ili ograničenim memorijskim resursima.Vremenska složenost:Iako je A* općenito učinkovit, njegova vremenska složenost može predstavljati problem za velike prostore pretraživanja ili grafikone. U najgorem slučaju, A* može eksponencijalno dulje pronaći optimalni put ako je heuristika neprikladna za problem.Usko grlo na odredištu:U određenim scenarijima, algoritam A* mora istražiti čvorove daleko od odredišta prije nego što konačno dosegne odredišnu regiju. Ovaj se problem javlja kada heuristika treba rano učinkovito usmjeriti pretragu na cilj.Obvezujući trošak:A* se suočava s poteškoćama kada više čvorova ima istu f-vrijednost (zbroj stvarnog troška i heurističkog troška). Korištena strategija može utjecati na optimalnost i učinkovitost otkrivenog puta. Ako se ne postupa ispravno, može dovesti do istraživanja nepotrebnih čvorova i usporiti algoritam.Složenost u dinamičnim okruženjima:U dinamičnim okruženjima gdje se cijena rubova ili čvorova može promijeniti tijekom pretraživanja, A* možda neće biti prikladan jer se ne prilagođava dobro takvim promjenama. Reformulacija od nule može biti računalno skupa, a algoritmi D* (Dynamic A*) osmišljeni su da to riješeSavršenstvo u beskrajnom svemiru:A* možda neće pronaći rješenje u beskonačnom prostoru stanja. U takvim slučajevima može raditi beskonačno, istražujući sve veći broj čvorova bez pronalaženja rješenja. Unatoč ovim nedostacima, A* je još uvijek robustan i naširoko korišten algoritam jer može učinkovito pronaći optimalne putove u mnogim praktičnim situacijama ako je heuristička funkcija dobro osmišljena i prostorom pretraživanja može se upravljati. Predložene su različite varijacije i inačice A* kako bi se ublažila neka od njegovih ograničenja.

Primjene A* algoritma pretraživanja u umjetnoj inteligenciji

Algoritam pretraživanja A* (slovo A) široko je korišten i robustan algoritam za pronalaženje puta u umjetnoj inteligenciji i računalnoj znanosti. Njegova učinkovitost i optimalnost čine ga pogodnim za različite primjene. Evo nekoliko tipičnih primjena algoritma pretraživanja A* u umjetnoj inteligenciji:

    Pronalaženje puta u igrama:A* se često koristi u video igrama za kretanje likova, neprijateljsku AI navigaciju i pronalaženje najkraćeg puta od jedne lokacije do druge na karti igre. Njegova sposobnost pronalaska optimalnog puta na temelju cijene i heuristike čini ga idealnim za aplikacije u stvarnom vremenu kao što su igre.Robotika i autonomna vozila:A* se koristi u robotici i autonomnoj navigaciji vozila za planiranje optimalne rute za robote da dođu do odredišta, izbjegavajući prepreke i uzimajući u obzir troškove terena. To je ključno za učinkovito i sigurno kretanje u prirodnom okruženju.Rješavanje labirinta:A* može učinkovito pronaći najkraći put kroz labirint, što ga čini vrijednim u mnogim aplikacijama za rješavanje labirinta, kao što je rješavanje zagonetki ili navigacija složenim strukturama.Planiranje rute i navigacija:U GPS sustavima i aplikacijama za mapiranje, A* se može koristiti za pronalaženje optimalne rute između dvije točke na karti, uzimajući u obzir faktore kao što su udaljenost, prometni uvjeti i topologija cestovne mreže.Rješavanje zagonetki:A* može riješiti razne dijagramske zagonetke, kao što su klizne zagonetke, Sudoku i problem s 8 zagonetki. Raspodjela resursa: U scenarijima u kojima resursi moraju biti optimalno raspoređeni, A* može pomoći pronaći najučinkovitiji put raspodjele, minimizirajući troškove i maksimizirajući učinkovitost.Mrežno usmjeravanje:A* se može koristiti u računalnim mrežama za pronalaženje najučinkovitije rute za pakete podataka od izvora do odredišnog čvora.Obrada prirodnog jezika (NLP):U nekim NLP zadacima, A* može generirati koherentne i kontekstualne odgovore tražeći moguće nizove riječi na temelju njihove vjerojatnosti i relevantnosti.Planiranje putanje u robotici:A* se može koristiti za planiranje putanje robota od jedne točke do druge, uzimajući u obzir različita ograničenja, kao što je izbjegavanje prepreka ili smanjenje potrošnje energije.AI igre:A* se također koristi za donošenje inteligentnih odluka za likove koji nisu igrači (NPC), kao što je određivanje najboljeg načina za postizanje cilja ili koordinaciju pokreta u timskoj igri.

Ovo je samo nekoliko primjera kako algoritam pretraživanja A* nalazi primjenu u raznim područjima umjetne inteligencije. Njegova fleksibilnost, učinkovitost i optimizacija čine ga vrijednim alatom za mnoge probleme.

C program za A* Algoritam pretraživanja u umjetnoj inteligenciji

 #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 za A* algoritam pretraživanja u umjetnoj inteligenciji

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

Obrazloženje:

    Čvor strukture:Ovo definira strukturu čvora koja predstavlja ćeliju mreže. Sadrži x i y koordinate čvora, trošak g od početnog čvora do tog čvora, heurističku vrijednost h (procijenjeni trošak od tog čvora do odredišnog čvora) i pokazivač na
  1. početni čvor staze.
  2. Izračunaj heuristiku:Ova funkcija izračunava heuristiku pomoću euklidske udaljenosti između čvora i cilja AStarSearch: Ova funkcija pokreće algoritam pretraživanja A*. Uzima koordinate početka i odredišta, mrežu i vraća vektor parova koji predstavljaju koordinate najkraće staze od početka do kraja.Primarno:Glavna funkcija programa uzima ulazne mreže, ishodište i ciljne koordinate od korisnika. Zatim poziva AStarSearch da pronađe najkraći put i ispisuje rezultat. Čvor strukture: Ovo definira strukturu čvora koja predstavlja ćeliju mreže. Sadrži x i y koordinate čvora, trošak g od početnog čvora do tog čvora, heurističku vrijednost h (procijenjeni trošak od tog čvora do odredišnog čvora) i pokazivač na početni čvor staze.Izračunaj heuristiku:Ova funkcija izračunava heuristiku pomoću euklidske udaljenosti između čvora i cilja AStarSearch: Ova funkcija pokreće algoritam pretraživanja A*. Uzima koordinate početka i odredišta, mrežu i vraća vektor parova koji predstavljaju koordinate najkraće staze od početka do kraja.

Uzorak izlaza

 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 za A* algoritam pretraživanja u umjetnoj inteligenciji

 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* Složenost algoritama pretraživanja u umjetnoj inteligenciji

Algoritam pretraživanja A* (izgovara se 'A-star') popularan je i naširoko korišten algoritam za obilaženje grafa i traženje puta u umjetnoj inteligenciji. Pronalaženje najkraćeg puta između dva čvora u okruženju temeljenom na grafu ili mreži obično je uobičajeno. Algoritam kombinira Dijkstrine i pohlepne elemente pretraživanja prvi prvi kako bi istražio prostor pretraživanja istovremeno osiguravajući optimalnost. Nekoliko čimbenika određuje složenost algoritma pretraživanja A*. Veličina grafa (čvorovi i rubovi): Broj čvorova i rubova grafa uvelike utječe na složenost algoritma. Više čvorova i rubova znači više mogućih opcija za istraživanje, što može povećati vrijeme izvršenja algoritma.

Heuristička funkcija: A* koristi heurističku funkciju (često označenu h(n)) za procjenu troška od trenutnog čvora do odredišnog čvora. Preciznost ove heuristike uvelike utječe na učinkovitost A* pretrage. Dobra heuristika može pomoći u bržem usmjeravanju pretrage do cilja, dok loša heuristika može dovesti do nepotrebnog pretraživanja.

gimp promijeniti boju
    Strukture podataka:A* održava dvije strukture glavnih podataka: otvoreni popis (prioritetni red) i zatvoreni popis (ili posjećeni skup). Učinkovitost ovih struktura podataka, zajedno s odabranom implementacijom (npr. binarne gomile prioritetnog reda), utječe na izvedbu algoritma.Faktor grananja:Prosječan broj sljedbenika za svaki čvor utječe na broj proširenih čvorova tijekom pretraživanja. Veći faktor grananja može dovesti do više istraživanja, što se povećavaOptimalnost i cjelovitost:A* jamči i optimalnost (pronalaženje najkraćeg puta) i potpunost (pronalaženje rješenja koje postoji). Međutim, ovo jamstvo dolazi s kompromisom u smislu računalne složenosti, budući da algoritam mora istraživati ​​različite putove za optimalnu izvedbu. Što se tiče vremenske složenosti, odabrana heuristička funkcija utječe na A* u najgorem slučaju. Uz prihvaćenu heuristiku (koja nikada ne precjenjuje stvarnu cijenu postizanja cilja), A* proširuje najmanji broj čvorova među algoritmima optimizacije. Vremenska složenost A * u najgorem slučaju je eksponencijalna u najgorem slučaju O(b ^ d), gdje je 'b' efektivni faktor grananja (prosječan broj sljedbenika po čvoru), a 'd' je optimalni

U praksi, međutim, A* često ima znatno bolju izvedbu zbog utjecaja heurističke funkcije koja pomaže usmjeriti algoritam na obećavajuće staze. U slučaju dobro osmišljene heuristike, efektivni faktor grananja je mnogo manji, što dovodi do bržeg pristupa optimalnom rješenju.