logo

A* Meklēšanas algoritms mākslīgajā intelektā

Ievads A* meklēšanas algoritmā AI

A* (izrunā 'A-zvaigzne') ir spēcīgs grafu šķērsošanas un ceļa noteikšanas algoritms, ko plaši izmanto mākslīgajā intelektā un datorzinātnēs. To galvenokārt izmanto, lai atrastu īsāko ceļu starp diviem diagrammas mezgliem, ņemot vērā aptuvenās izmaksas, kas saistītas ar nokļūšanu no pašreizējā mezgla uz galamērķa mezglu. Algoritma galvenā priekšrocība ir tā spēja nodrošināt optimālu ceļu, izpētot grafiku vairāk informētā veidā, salīdzinot ar tradicionālajiem meklēšanas algoritmiem, piemēram, Dijkstra algoritmu.

Algoritms A* apvieno divu citu meklēšanas algoritmu priekšrocības: Dijkstra algoritmu un Mantkārīgā labākā pirmā meklēšana. Tāpat kā Dijkstra algoritms, arī A* nodrošina, ka atrastais ceļš ir pēc iespējas īss, taču tas tiek darīts efektīvāk, meklējot meklēšanu, izmantojot heiristiku, kas ir līdzīga Mantkārīgā labākā pirmā meklēšana. Heiristiskā funkcija, kas apzīmēta ar h(n), aplēš izmaksas, kas rodas, nokļūstot no jebkura konkrētā mezgla n uz galamērķa mezglu.

A* galvenā ideja ir novērtēt katru mezglu, pamatojoties uz diviem parametriem:

java atjaunināšana
    g(n):faktiskās izmaksas, lai nokļūtu no sākotnējā mezgla uz mezglu n. Tas atspoguļo mezgla n izejošo malu izmaksu summu.h(n):Heiristiskās izmaksas (pazīstamas arī kā “aplēses izmaksas”) no mezgla n līdz galamērķa mezglam n. Šai problēmai specifiskajai heiristiskajai funkcijai ir jābūt pieņemamai, kas nozīmē, ka tā nekad nepārvērtē faktiskās mērķa sasniegšanas izmaksas. Mezgla n novērtēšanas funkcija ir definēta kā f(n) = g(n) h(n).

Algoritms A* izvēlas izpētāmos mezglus, pamatojoties uz zemāko f(n) vērtību, dodot priekšroku mezgliem ar viszemākajām aplēstajām kopējām izmaksām mērķa sasniegšanai. A* algoritms darbojas:

  1. Izveidojiet atklātu atrasto, bet neizpētīto mezglu sarakstu.
  2. Izveidojiet slēgtu sarakstu, lai saglabātu jau izpētītos mezglus.
  3. Pievienojiet sākuma mezglu atvērtajam sarakstam ar sākotnējo vērtību g
  4. Atkārtojiet šīs darbības, līdz atvērtais saraksts ir tukšs vai sasniedzat mērķa mezglu:
    1. Atvērtajā sarakstā atrodiet mezglu ar mazāko f vērtību (t.i., mezglu ar mazāko g(n) h(n)).
    2. Pārvietojiet atlasīto mezglu no atvērtā saraksta uz slēgto sarakstu.
    3. Izveidojiet visus derīgos atlasītā mezgla pēctečus.
    4. Katram pēctecim aprēķina g vērtību kā pašreizējā mezgla g vērtības summu un izmaksas, kas saistītas ar pārvietošanos no pašreizējā mezgla uz nākamo mezglu. Atjauniniet izsekotāja g vērtību, kad tiek atrasts labāks ceļš.
    5. Ja sekotājs nav atvērtajā sarakstā, pievienojiet to ar aprēķināto g vērtību un aprēķiniet tā h vērtību. Ja tas jau ir atvērtajā sarakstā, atjauniniet tā g vērtību, ja jaunais ceļš ir labāks.
    6. Atkārtojiet ciklu. Algoritms A* beidzas, kad tiek sasniegts mērķa mezgls vai kad atvērtais saraksts iztukšojas, norādot, ka nav ceļu no sākuma mezgla uz mērķa mezglu. A* meklēšanas algoritms tiek plaši izmantots dažādās jomās, piemēram, robotikā, videospēlēs, tīkla maršrutēšanas un projektēšanas problēmās, jo tas ir efektīvs un var atrast optimālus ceļus grafikos vai tīklos.

Tomēr ir svarīgi izvēlēties piemērotu un pieņemamu heiristisko funkciju, lai algoritms darbotos pareizi un nodrošinātu optimālu risinājumu.

Informēti meklēšanas algoritmi

Mākslīgā intelekta A* meklēšanas algoritma vēsture

To izstrādāja Pīters Hārts, Nils Nilsons un Bertrams Rafaels Stenfordas pētniecības institūtā (tagad SRI International) kā Dijkstra algoritma un citu tā laika meklēšanas algoritmu paplašinājumu. A* pirmo reizi tika publicēts 1968. gadā un ātri ieguva atzinību par savu nozīmi un efektivitāti mākslīgā intelekta un datorzinātņu kopienās. Šeit ir īss pārskats par vissvarīgākajiem pagrieziena punktiem meklēšanas algoritma A* vēsturē:

    Agrīnās meklēšanas algoritmi:Pirms A* izstrādes pastāvēja dažādi grafiku meklēšanas algoritmi, tostarp dziļuma meklēšana (DFS) un pirmā meklēšana pēc platuma (BFS). Lai gan šie algoritmi palīdzēja atrast ceļus, tie negarantēja optimālumu un neņēma vērā heiristiku, lai vadītu meklēšanu.Dijkstra algoritms:1959. gadā holandiešu datorzinātnieks Edsgers V. Dijkstra ieviesa Dijkstras algoritmu, kas atrada īsāko ceļu svērtā grafikā ar nenegatīviem malu svariem. Dijkstra algoritms bija efektīvs, taču tā izsmeļošā rakstura dēļ tam bija ierobežojumi, ja to izmantoja lielākos grafikos vaiInformētā meklēšana:Ir izstrādāti uz zināšanām balstīti meklēšanas algoritmi (pazīstami arī kā heiristiskā meklēšana), lai iekļautu heiristisko informāciju, piemēram, aptuvenās izmaksas, lai efektīvi vadītu meklēšanas procesu. Greedy Best-First Search bija viens no šādiem algoritmiem, taču tas negarantēja optimālumu īsākā ceļa atrašanai.A* attīstība:1968. gadā Pīters Hārts, Nils Nilsons un Bertrams Rafaels ieviesa A* algoritmu kā Dijkstras algoritma un Greedy Best-First Search kombināciju. A* izmantoja heiristisko funkciju, lai novērtētu izmaksas no pašreizējā mezgla līdz galamērķa mezglam, apvienojot tās ar faktiskajām pašreizējā mezgla sasniegšanas izmaksām. Tas ļāva A* apzinātāk izpētīt grafiku, izvairoties no nevajadzīgiem ceļiem un garantējot optimālu risinājumu.Taisnīgums un pilnība:A* autori parādīja, ka algoritms ir ideāls (vienmēr atrod risinājumu, ja tāds pastāv) un optimāls (atrod īsāko ceļu) noteiktos apstākļos.Plaši izplatīta pieņemšana un progress:A* ātri ieguva popularitāti AI un IT kopienās, pateicoties tās efektivitātei, un pētnieki un izstrādātāji ir paplašinājuši un piemērojuši A* algoritmu dažādās jomās, tostarp robotikā, videospēlēs, inženierijā un tīkla maršrutēšanā. Gadu gaitā ir ierosinātas vairākas A* algoritma variācijas un optimizācijas, piemēram, Incremental A* un Parallel A*. Mūsdienās A* meklēšanas algoritms joprojām ir fundamentāls un plaši izmantots mākslīgā intelekta un grafiku šķērsošanas algoritms. Tam joprojām ir būtiska loma dažādās lietojumprogrammās un pētniecības jomās. Tā ietekme uz mākslīgo intelektu un tā ieguldījums ceļu noteikšanas un optimizācijas problēmās ir padarījis to par stūrakmeni intelektuālo sistēmu pētījumos.

Kā A* meklēšanas algoritms darbojas mākslīgajā intelektā?

A* (izrunā 'burts A') meklēšanas algoritms ir populārs un plaši izmantots grafu šķērsošanas algoritms mākslīgajā intelektā un datorzinātnēs. To izmanto, lai svērtā grafikā atrastu īsāko ceļu no sākuma mezgla līdz galamērķa mezglam. A* ir informēts meklēšanas algoritms, kas izmanto heiristiku, lai efektīvi vadītu meklēšanu. Meklēšanas algoritms A* darbojas šādi:

Algoritms sākas ar prioritāro rindu, lai saglabātu izpētāmos mezglus. Tas arī veido divas datu struktūras g(n): līdz šim īsākā ceļa izmaksas no sākuma mezgla līdz mezglam n un h(n), aprēķinātās izmaksas (heiristiskais) no mezgla n līdz galamērķa mezglam. Bieži vien tā ir saprātīga heiristiska, kas nozīmē, ka tā nekad nepārvērtē faktiskās mērķa sasniegšanas izmaksas. Ievietojiet sākotnējo mezglu prioritātes rindā un iestatiet tā g(n) uz 0. Ja prioritātes rinda nav tukša, noņemiet no prioritātes rindas mezglu ar zemāko f(n). f(n) = g(n) h(n). Ja dzēstais mezgls ir galamērķa mezgls, algoritms beidzas un ceļš tiek atrasts. Pretējā gadījumā paplašiniet mezglu un izveidojiet tā kaimiņus. Katram kaimiņu mezglam aprēķiniet tā sākotnējo g(n) vērtību, kas ir pašreizējā mezgla g vērtības summa un izmaksas, kas saistītas ar pārvietošanos no pašreizējā mezgla uz blakus mezglu. Ja kaimiņu mezgls nav prioritārā secībā vai sākotnējā g(n) vērtība ir mazāka par tā pašreizējo g vērtību, atjauniniet tā g vērtību un iestatiet tā vecākmezglu uz pašreizējo mezglu. Aprēķiniet f(n) vērtību no kaimiņu mezgla un pievienojiet to prioritārajai rindai.

Ja cikls beidzas, neatrodot galamērķa mezglu, diagrammai nav ceļa no sākuma līdz beigām. A* efektivitātes atslēga ir heiristiskās funkcijas h(n) izmantošana, kas nodrošina jebkura mezgla mērķa sasniegšanas atlikušo izmaksu aprēķinu. Apvienojot faktiskās izmaksas g (n) ar heiristiskajām izmaksām h (n), algoritms efektīvi pēta daudzsološus ceļus, prioritāri nosakot mezglus, kas, iespējams, ved uz īsāko ceļu. Ir svarīgi atzīmēt, ka A* algoritma efektivitāte ir ļoti atkarīga no heiristiskās funkcijas izvēles. Pieņemama heiristika nodrošina, ka algoritms vienmēr atrod īsāko ceļu, taču informētāka un precīzāka heiristika var novest pie ātrākas konverģences un samazinātas meklēšanas vietas.

A* meklēšanas algoritma priekšrocības mākslīgajā intelektā

A* meklēšanas algoritms piedāvā vairākas priekšrocības mākslīgā intelekta un problēmu risināšanas scenārijos:

    Optimālais risinājums:A* nodrošina optimālā (īsākā) ceļa atrašanu no sākuma mezgla līdz galamērķa mezglam svērtajā grafikā, ja ir pieņemama heiristiskā funkcija. Šī optimizācija ir izšķiroša priekšrocība daudzās lietojumprogrammās, kur ir svarīgi atrast īsāko ceļu.Pilnīgums:Ja risinājums pastāv, A* to atradīs, ja grafam nav bezgalīgas izmaksas. Šī pilnīguma īpašība nodrošina, ka A* var izmantot risinājumu, ja tāds pastāv.Efektivitāte:A* ir efektīva, ja tiek izmantota efektīva un pieņemama heiristiskā funkcija. Heiristika virza meklēšanu uz mērķi, koncentrējoties uz daudzsološiem ceļiem un izvairoties no nevajadzīgas izpētes, padarot A* efektīvāku par neapzinātiem meklēšanas algoritmiem, piemēram, meklēšanu pēc platuma vai meklēšanu pēc dziļuma.Daudzpusība:A* ir plaši pielietojama dažādās problēmu jomās, tostarp ceļa noteikšana, maršruta plānošana, robotika, spēļu izstrāde un daudz kas cits. A* var izmantot, lai efektīvi atrastu optimālus risinājumus, ja vien var definēt jēgpilnu heiristiku.Optimizēta meklēšana:A* saglabā prioritātes secību, lai paplašināšanai atlasītu mezglus ar mazāko f(n) vērtību (g(n) un h(n)). Tas ļauj tai vispirms izpētīt daudzsološos ceļus, kas samazina meklēšanas vietu un nodrošina ātrāku konverģenci.Atmiņas efektivitāte:Atšķirībā no dažiem citiem meklēšanas algoritmiem, piemēram, meklēšanas pēc platuma, A* prioritārajā rindā saglabā tikai ierobežotu skaitu mezglu, kas padara to par atmiņu efektīvu, īpaši lieliem grafikiem.Noskaņojamā heiristika:A* veiktspēju var precīzi noregulēt, izvēloties dažādas heiristiskās funkcijas. Izglītotāka heiristika var novest pie ātrākas konverģences un mazāk paplašinātiem mezgliem.Plaši pētīts:A* ir labi izveidots algoritms ar gadu desmitiem ilgušu pētījumu un praktisku pielietojumu. Ir izstrādātas daudzas optimizācijas un variācijas, padarot to par uzticamu un labi saprotamu problēmu novēršanas rīku.Meklēšana tīmeklī:A* var izmantot tīmeklī balstītai ceļu meklēšanai, kur algoritms pastāvīgi atjaunina ceļu atbilstoši izmaiņām vidē vai jaunu izskatu. Tas ļauj pieņemt lēmumus reāllaikā dinamiskos scenārijos.

A* meklēšanas algoritma trūkumi mākslīgajā intelektā

Lai gan A* (burts A) meklēšanas algoritms ir plaši izmantots un jaudīgs paņēmiens mākslīgā intelekta ceļa noteikšanas un grafika šķērsošanas problēmu risināšanai, tam ir trūkumi un ierobežojumi. Šeit ir daži no galvenajiem meklēšanas algoritma trūkumiem:

    Heiristiskā precizitāte:A* algoritma veiktspēja lielā mērā ir atkarīga no heiristiskās funkcijas precizitātes, ko izmanto, lai novērtētu izmaksas no pašreizējā mezgla uz Ja heiristiska ir nepieņemama (nekad nepārvērtē faktiskās izmaksas) vai nekonsekventa (apmierina trīsstūra nevienlīdzību), A* var neatrast optimālo ceļu vai izpētīt vairāk mezglu, nekā nepieciešams, tādējādi ietekmējot tā efektivitāti un precizitāti.Atmiņas lietojums:A* pieprasa, lai visi apmeklētie mezgli tiktu saglabāti atmiņā, lai sekotu līdzi izpētītajiem ceļiem. Atmiņas lietojums dažkārt var kļūt par būtisku problēmu, it īpaši, ja ir daudz meklēšanas vietas vai ierobežoti atmiņas resursi.Laika sarežģītība:Lai gan A* parasti ir efektīva, tā laika sarežģītība var radīt bažas plašām meklēšanas telpām vai grafikiem. Sliktākajā gadījumā A* var aizņemt eksponenciāli ilgāku laiku, lai atrastu optimālo ceļu, ja heiristika problēmai nav piemērota.Sašaurinājums galamērķī:Konkrētos scenārijos A* algoritmam ir jāizpēta mezgli, kas atrodas tālu no galamērķa, pirms beidzot sasniedz galamērķa reģionu. Šī problēma rodas, ja heiristikai ir nepieciešams savlaicīgi efektīvi virzīt meklēšanu uz mērķi.Izmaksu saistošs:A* saskaras ar grūtībām, ja vairākiem mezgliem ir vienāda f vērtība (faktisko izmaksu un heiristisko izmaksu summa). Izmantotā stratēģija var ietekmēt atklātā ceļa optimālumu un efektivitāti. Ja tas netiek pareizi apstrādāts, tas var novest pie nevajadzīgu mezglu izpētes un palēnināt algoritma darbību.Sarežģītība dinamiskā vidē:Dinamiskā vidē, kur meklēšanas laikā var mainīties malu vai mezglu izmaksas, A* var nebūt piemērots, jo tas slikti pielāgojas šādām izmaiņām. Pārformulēšana no nulles var būt skaitļošanas ziņā dārga, un D* (Dynamic A*) algoritmi tika izstrādāti, lai to atrisinātu.Pilnība bezgalīgā telpā:A* var neatrast risinājumu bezgalīgā stāvokļu telpā. Šādos gadījumos tas var darboties bezgalīgi, izpētot arvien lielāku mezglu skaitu, neatrodot risinājumu. Neskatoties uz šiem trūkumiem, A* joprojām ir stabils un plaši izmantots algoritms, jo tas var efektīvi atrast optimālos ceļus daudzās praktiskās situācijās, ja heiristiskā funkcija ir labi izstrādāta un meklēšanas telpa ir pārvaldāma. Ir ierosinātas dažādas A* variācijas un varianti, lai mazinātu dažus tā ierobežojumus.

A* meklēšanas algoritma pielietojumi mākslīgajā intelektā

Meklēšanas algoritms A* (burts A) ir plaši izmantots un stabils ceļu noteikšanas algoritms mākslīgajā intelektā un datorzinātnēs. Tā efektivitāte un optimālums padara to piemērotu dažādiem lietojumiem. Šeit ir daži tipiski A* meklēšanas algoritma pielietojumi mākslīgajā intelektā:

    Ceļa meklēšana spēlēs:A* bieži izmanto videospēlēs varoņu pārvietošanai, ienaidnieka AI navigācijai un īsākā ceļa atrašanai no vienas vietas uz otru spēles kartē. Tā spēja atrast optimālo ceļu, pamatojoties uz izmaksām un heiristiku, padara to ideāli piemērotu reāllaika lietojumprogrammām, piemēram, spēlēm.Robotika un autonomie transportlīdzekļi:A* tiek izmantots robotikā un autonomā transportlīdzekļu navigācijā, lai plānotu optimālu maršrutu robotiem, lai sasniegtu galamērķi, izvairoties no šķēršļiem un ņemot vērā reljefa izmaksas. Tas ir ļoti svarīgi efektīvai un drošai kustībai dabiskā vidē.Labirints risināšana:A* var efektīvi atrast īsāko ceļu caur labirintu, padarot to vērtīgu daudzās labirintu risināšanas lietojumprogrammās, piemēram, mīklu risināšanā vai sarežģītu struktūru navigācijā.Maršruta plānošana un navigācija:GPS sistēmās un kartēšanas lietojumprogrammās A* var izmantot, lai atrastu optimālo maršrutu starp diviem punktiem kartē, ņemot vērā tādus faktorus kā attālums, satiksmes apstākļi un ceļu tīkla topoloģija.Mīklu risināšana:A* var atrisināt dažādas diagrammu mīklas, piemēram, slīdošās mīklas, Sudoku un 8 mīklu uzdevumu. Resursu piešķiršana: gadījumos, kad resursi ir jāpiešķir optimāli, A* var palīdzēt atrast visefektīvāko sadales ceļu, samazinot izmaksas un palielinot efektivitāti.Tīkla maršrutēšana:A* var izmantot datortīklos, lai atrastu visefektīvāko maršrutu datu paketēm no avota uz galamērķa mezglu.Dabiskās valodas apstrāde (NLP):Dažos NLP uzdevumos A* var ģenerēt saskaņotas un kontekstuālas atbildes, meklējot iespējamās vārdu secības, pamatojoties uz to iespējamību un atbilstību.Ceļu plānošana robotikā:A* var izmantot, lai plānotu robota ceļu no viena punkta uz otru, ņemot vērā dažādus ierobežojumus, piemēram, izvairīšanos no šķēršļiem vai līdz minimumam samazinot enerģijas patēriņu.Spēles AI:A* tiek izmantots arī, lai pieņemtu inteliģentus lēmumus par varoņiem, kas nav spēlētāji (NPC), piemēram, lai noteiktu labāko veidu, kā sasniegt mērķi vai koordinēt kustības komandas spēlē.

Šie ir tikai daži piemēri, kā A* meklēšanas algoritms atrod pielietojumu dažādās mākslīgā intelekta jomās. Tā elastība, efektivitāte un optimizācija padara to par vērtīgu rīku daudzu problēmu risināšanai.

C programma A* meklēšanas algoritmam mākslīgajā intelektā

 #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++ programma A* meklēšanas algoritmam mākslīgajā intelektā

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

Paskaidrojums:

Kylie Jenner vecums
    Struktūras mezgls:Tas definē mezgla struktūru, kas attēlo režģa šūnu. Tas satur mezgla x un y koordinātas, izmaksas g no sākuma mezgla līdz šim mezglam, heiristisko vērtību h (aptuvenās izmaksas no šī mezgla līdz galamērķa mezglam) un rādītāju uz
  1. ceļa sākuma mezgls.
  2. Aprēķināt heiristisku:Šī funkcija aprēķina heiristiku, izmantojot Eiklīda attālumu starp mezglu un mērķa AStarSearch: šī funkcija palaiž A* meklēšanas algoritmu. Tas ņem sākuma un galamērķa koordinātas, režģi un atgriež pāru vektoru, kas attēlo īsākā ceļa koordinātas no sākuma līdz beigām.Primārs:Programmas galvenā funkcija no lietotāja ņem ievades režģus, izcelsmi un mērķa koordinātas. Pēc tam tas izsauc AStarSearch, lai atrastu īsāko ceļu, un izdrukā rezultātu. Struktūras mezgls: tas definē mezgla struktūru, kas attēlo režģa šūnu. Tajā ir mezgla x un y koordinātas, izmaksas g no sākuma mezgla līdz šim mezglam, heiristiskā vērtība h (aptuvenās izmaksas no šī mezgla līdz galamērķa mezglam) un rādītājs uz ceļa sākuma mezglu.Aprēķināt heiristisku:Šī funkcija aprēķina heiristiku, izmantojot Eiklīda attālumu starp mezglu un mērķa AStarSearch: šī funkcija palaiž A* meklēšanas algoritmu. Tas ņem sākuma un galamērķa koordinātas, režģi un atgriež pāru vektoru, kas attēlo īsākā ceļa koordinātas no sākuma līdz beigām.

Izvades paraugs

 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 programma A* meklēšanas algoritmam mākslīgajā intelektā

 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* Meklēšanas algoritma sarežģītība mākslīgajā intelektā

Meklēšanas algoritms A* (izrunā 'A-zvaigzne') ir populārs un plaši izmantots grafu šķērsošanas un ceļa meklēšanas algoritms mākslīgajā intelektā. Parasti parasti tiek atrasts īsākais ceļš starp diviem mezgliem grafiskā vai režģa vidē. Algoritms apvieno Dijkstra un mantkārīgos labākos vispirms meklēšanas elementus, lai izpētītu meklēšanas telpu, vienlaikus efektīvi nodrošinot optimālumu. Vairāki faktori nosaka A* meklēšanas algoritma sarežģītību. Grafika lielums (mezgli un malas): grafa mezglu un malu skaits lielā mērā ietekmē algoritma sarežģītību. Vairāk mezglu un malu nozīmē vairāk iespēju izpētīt, kas var palielināt algoritma izpildes laiku.

Heiristiskā funkcija: A* izmanto heiristisko funkciju (bieži apzīmē h(n)), lai novērtētu izmaksas no pašreizējā mezgla līdz galamērķa mezglam. Šīs heiristikas precizitāte lielā mērā ietekmē A* meklēšanas efektivitāti. Laba heiristika var palīdzēt ātrāk virzīt meklēšanu uz mērķi, savukārt slikta heiritika var izraisīt nevajadzīgu meklēšanu.

    Datu struktūras:A* uztur divas galveno datu struktūras: atvērto sarakstu (prioritātes rindu) un slēgto sarakstu (vai apmeklēto kopu). Šo datu struktūru efektivitāte kopā ar izvēlēto ieviešanu (piemēram, prioritāro rindu bināro kaudzes) ietekmē algoritma veiktspēju.Nozares faktors:Vidējais sekotāju skaits katram mezglam ietekmē meklēšanas laikā paplašināto mezglu skaitu. Augstāks sazarojuma faktors var izraisīt plašāku izpēti, kas palielināsOptimalitāte un pilnība:A* garantē gan optimālumu (īsākā ceļa atrašana), gan pilnīgumu (esoša risinājuma atrašana). Tomēr šī garantija ir saistīta ar kompromisu skaitļošanas sarežģītības ziņā, jo algoritmam ir jāizpēta dažādi ceļi optimālai veiktspējai. Runājot par laika sarežģītību, izvēlētā heiristiskā funkcija sliktākajā gadījumā ietekmē A*. Izmantojot pieņemto heiristiku (kas nekad nepārvērtē patiesās mērķa sasniegšanas izmaksas), A* paplašina vismazāko mezglu skaitu optimizācijas algoritmu vidū. A * sliktākā gadījuma laika sarežģītība ir eksponenciāla sliktākajā gadījumā O(b ^ d), kur 'b' ir efektīvais sazarošanas faktors (vidējais sekotāju skaits mezglā) un 'd' ir optimālais.

Tomēr praksē A* bieži darbojas ievērojami labāk heiristiskās funkcijas ietekmes dēļ, kas palīdz virzīt algoritmu uz daudzsološiem ceļiem. Labi izstrādātas heiristikas gadījumā efektīvais sazarošanas faktors ir daudz mazāks, kas noved pie ātrākas pieejas optimālajam risinājumam.