logo

A* Dirbtinio intelekto paieškos algoritmas

Įvadas į A* paieškos algoritmą AI

A* (tariama „A-star“) yra galingas grafiko perėjimo ir kelio nustatymo algoritmas, plačiai naudojamas dirbtinio intelekto ir kompiuterių moksle. Jis daugiausia naudojamas ieškant trumpiausio kelio tarp dviejų grafiko mazgų, atsižvelgiant į numatomas išlaidas norint patekti iš dabartinio mazgo į paskirties mazgą. Pagrindinis algoritmo pranašumas yra jo gebėjimas pateikti optimalų kelią tiriant grafiką labiau informuotu būdu, palyginti su tradiciniais paieškos algoritmais, tokiais kaip Dijkstra algoritmas.

Algoritmas A* apjungia dviejų kitų paieškos algoritmų pranašumus: Dijkstra algoritmą ir Greedy Best-First Search. Kaip ir Dijkstra algoritmas, A* užtikrina, kad rastas kelias būtų kuo trumpesnis, bet tai daro efektyviau, nukreipdamas paiešką per euristiką, panašią į „Greedy Best-First Search“. Euristinė funkcija, pažymėta h(n), įvertina patekimo iš bet kurio mazgo n į paskirties mazgą išlaidas.

Pagrindinė A* idėja yra įvertinti kiekvieną mazgą pagal du parametrus:

kaip vykdyti scenarijų
    g(n):faktinės išlaidos norint patekti iš pradinio mazgo į mazgą n. Tai reiškia n mazgo išeinančių kraštų išlaidų sumą.h(n):Euristinė kaina (taip pat žinoma kaip „įvertinimo kaina“) nuo mazgo n iki paskirties mazgo n. Ši konkrečiai problemai būdinga euristinė funkcija turi būti priimtina, tai reiškia, kad ji niekada nepervertina faktinių tikslo pasiekimo išlaidų. Mazgo n vertinimo funkcija apibrėžiama kaip f(n) = g(n) h(n).

Algoritmas A* parenka tirtinus mazgus pagal mažiausią f(n) reikšmę, pirmenybę teikiant mazgams, kurių bendra sąnaudų suma yra mažiausia, kad būtų pasiektas tikslas. A* algoritmas veikia:

  1. Sukurkite atvirą rastų, bet neištirtų mazgų sąrašą.
  2. Sukurkite uždarą sąrašą, kad galėtumėte laikyti jau ištirtus mazgus.
  3. Į atvirą sąrašą įtraukite pradinį mazgą su pradine g verte
  4. Kartokite šiuos veiksmus, kol atidarytas sąrašas bus tuščias arba pasieksite tikslinį mazgą:
    1. Atvirajame sąraše raskite mazgą su mažiausia f reikšme (t. y. mazgą, kurio g(n) h(n)).
    2. Perkelkite pasirinktą mazgą iš atvirojo sąrašo į uždarą sąrašą.
    3. Sukurti visus galiojančius pasirinkto mazgo palikuonis.
    4. Kiekvienam įpėdiniui apskaičiuoja g reikšmę kaip dabartinio mazgo g vertės ir perėjimo iš dabartinio mazgo į paskesnį mazgą išlaidų sumą. Atnaujinkite sekimo priemonės g reikšmę, kai randamas geresnis kelias.
    5. Jei sekėjo nėra atvirame sąraše, pridėkite jį su apskaičiuota g reikšme ir apskaičiuokite jos h reikšmę. Jei jis jau yra atvirame sąraše, atnaujinkite jo g reikšmę, jei naujas kelias yra geresnis.
    6. Pakartokite ciklą. Algoritmas A* baigiasi, kai pasiekiamas tikslinis mazgas arba kai ištuštėja atviras sąrašas, nurodant, kad nėra kelių nuo pradžios mazgo iki tikslinio mazgo. A* paieškos algoritmas plačiai naudojamas įvairiose srityse, tokiose kaip robotika, vaizdo žaidimai, tinklo maršruto parinkimas ir projektavimo problemos, nes jis yra efektyvus ir gali rasti optimalius kelius grafikuose ar tinkluose.

Tačiau norint, kad algoritmas veiktų tinkamai ir pateiktų optimalų sprendimą, būtina pasirinkti tinkamą ir priimtiną euristinę funkciją.

Informuotos paieškos algoritmai

Dirbtinio intelekto A* paieškos algoritmo istorija

Jį sukūrė Peteris Hartas, Nilsas Nilssonas ir Bertramas Raphaelis iš Stanfordo tyrimų instituto (dabar SRI International) kaip Dijkstros algoritmo ir kitų to meto paieškos algoritmų plėtinį. A* pirmą kartą buvo paskelbtas 1968 m. ir greitai sulaukė pripažinimo dėl savo svarbos ir veiksmingumo dirbtinio intelekto ir kompiuterių mokslo bendruomenėse. Štai trumpa svarbiausių paieškos algoritmo A* istorijos etapų apžvalga:

    Ankstyvosios paieškos algoritmai:Prieš kuriant A*, egzistavo įvairūs grafiko paieškos algoritmai, įskaitant paiešką pagal gylį (DFS) ir paiešką pirmoje vietoje (BFS). Nors šie algoritmai padėjo rasti kelius, jie negarantavo optimalumo ir neatsižvelgė į euristiką, kuri padėtų ieškotiDijkstra algoritmas:1959 metais olandų kompiuterių mokslininkas Edsgeris W. Dijkstra pristatė Dijkstros algoritmą, kuris svertiniame grafe su neneigiamais kraštų svoriais rado trumpiausią kelią. Dijkstra algoritmas buvo efektyvus, tačiau dėl jo išsamaus pobūdžio jis turėjo apribojimų, kai buvo naudojamas didesniuose grafikuose arbaInformuota paieška:Sukurti žiniomis pagrįsti paieškos algoritmai (taip pat vadinami euristine paieška), kad įtrauktų euristinę informaciją, pvz., apskaičiuotas išlaidas, kad būtų veiksmingai nukreiptas paieškos procesas. Greedy Best-First Search buvo vienas iš tokių algoritmų, tačiau jis negarantavo optimalumo ieškant trumpiausio kelio.A* plėtra:1968 m. Peteris Hartas, Nilsas Nilssonas ir Bertramas Raphaelis pristatė A* algoritmą kaip Dijkstros algoritmo ir „Greedy Best-First Search“ derinį. A* naudojo euristinę funkciją, kad įvertintų išlaidas nuo dabartinio mazgo iki paskirties mazgo, sujungdamas jas su faktinėmis dabartinio mazgo pasiekimo išlaidomis. Tai leido A* sąmoningiau tyrinėti grafiką, išvengiant nereikalingų takų ir garantuojant optimalų sprendimą.Teisingumas ir tobulumas:A* autoriai parodė, kad algoritmas tam tikromis sąlygomis yra tobulas (visada randa sprendimą, jei toks yra) ir optimalus (randa trumpiausią kelią).Plačiai paplitęs priėmimas ir pažanga:A* greitai išpopuliarėjo dirbtinio intelekto ir IT bendruomenėse dėl savo efektyvumo, o mokslininkai ir kūrėjai išplėtė ir pritaikė A* algoritmą įvairiose srityse, įskaitant robotiką, vaizdo žaidimus, inžineriją ir tinklo maršruto parinkimą. Bėgant metams buvo pasiūlyta keletas A* algoritmo variantų ir optimizacijų, pavyzdžiui, prieauginis A* ir lygiagretusis A*. Šiandien A* paieškos algoritmas vis dar yra pagrindinis ir plačiai naudojamas dirbtinio intelekto ir grafikų perėjimo algoritmas. Ji ir toliau atlieka esminį vaidmenį įvairiose taikymo srityse ir mokslinių tyrimų srityse. Jo poveikis dirbtiniam intelektui ir indėlis į kelio paieškos bei optimizavimo problemas pavertė jį kertiniu intelektualių sistemų tyrimų algoritmu.

Kaip A* paieškos algoritmas veikia dirbtiniame intelekte?

Paieškos algoritmas A* (tariama „A raidė“) yra populiarus ir plačiai naudojamas grafų apėjimo algoritmas dirbtinio intelekto ir kompiuterių moksle. Jis naudojamas norint rasti trumpiausią kelią nuo pradžios mazgo iki paskirties mazgo svertiniame grafike. A* yra informuotas paieškos algoritmas, kuris naudoja euristiką efektyviai paieškai nukreipti. Paieškos algoritmas A* veikia taip:

Algoritmas pradedamas nuo prioritetinės eilės, kurioje saugomi tyrinėjami mazgai. Ji taip pat sukuria dvi duomenų struktūras g(n): iki šiol trumpiausio kelio nuo pradinio mazgo iki mazgo n kaina ir h(n), apskaičiuota kaina (euristinė) nuo mazgo n iki paskirties mazgo. Tai dažnai yra pagrįsta euristika, o tai reiškia, kad ji niekada nepervertina faktinių tikslo pasiekimo išlaidų. Įdėkite pradinį mazgą į prioritetinę eilę ir nustatykite jo g(n) į 0. Jei prioriteto eilė nėra tuščia, iš prioritetinės eilės pašalinkite mazgą su mažiausiu f(n). f(n) = g(n) h(n). Jei ištrintas mazgas yra paskirties mazgas, algoritmas baigiasi ir kelias randamas. Priešingu atveju išplėskite mazgą ir sukurkite jo kaimynus. Apskaičiuokite kiekvieno kaimyninio mazgo pradinę g(n) reikšmę, kuri yra dabartinio mazgo g vertės ir perėjimo iš dabartinio mazgo į gretimą mazgą išlaidų suma. Jei kaimyninis mazgas nėra prioriteto tvarka arba pradinė g(n) reikšmė mažesnė už dabartinę g reikšmę, atnaujinkite jo g reikšmę ir nustatykite pirminį mazgą į dabartinį mazgą. Apskaičiuokite f(n) reikšmę iš kaimyninio mazgo ir įtraukite ją į prioritetinę eilę.

Jei ciklas baigiasi neradus paskirties mazgo, grafikas neturi kelio nuo pradžios iki pabaigos. A* efektyvumo raktas yra euristinės funkcijos h(n), kuri pateikia likusių bet kurio mazgo tikslo pasiekimo sąnaudų apskaičiavimą. Sujungdamas faktines išlaidas g (n) su euristinėmis kainomis h (n), algoritmas efektyviai tiria perspektyvius kelius, pirmenybę teikdamas mazgams, kurie gali nuvesti į trumpiausią kelią. Svarbu pažymėti, kad A* algoritmo efektyvumas labai priklauso nuo euristinės funkcijos pasirinkimo. Priimtina euristika užtikrina, kad algoritmas visada suras trumpiausią kelią, tačiau labiau informuota ir tikslesnė euristika gali paskatinti greitesnę konvergenciją ir sumažinti paieškos erdvę.

A* paieškos algoritmo privalumai dirbtinio intelekto srityje

A* paieškos algoritmas siūlo keletą privalumų dirbtinio intelekto ir problemų sprendimo scenarijuose:

    Optimalus sprendimas:A* užtikrina optimalaus (trumpiausio) kelio nuo pradžios mazgo iki paskirties mazgo suradimą svertiniame grafike, atsižvelgiant į priimtiną euristinę funkciją. Šis optimalumas yra lemiamas pranašumas daugelyje programų, kuriose būtina rasti trumpiausią kelią.Išsamumas:Jei sprendimas egzistuoja, A* jį suras, jei grafas neturi begalinės kainos. Ši išsamumo savybė užtikrina, kad A* gali pasinaudoti sprendimu, jei jis egzistuoja.Efektyvumas:A* yra efektyvus, jei naudojama efektyvi ir priimtina euristinė funkcija. Euristika nukreipia paiešką į tikslą, sutelkdama dėmesį į daug žadančius kelius ir vengdama nereikalingų tyrinėjimų, todėl A* yra veiksmingesnė už nežinomus paieškos algoritmus, tokius kaip paieška pagal plotį arba paieška pagal gylį.Universalumas:A* yra plačiai taikomas įvairiose probleminėse srityse, įskaitant kelio paiešką, maršruto planavimą, robotiką, žaidimų kūrimą ir kt. A* gali būti naudojamas norint efektyviai rasti optimalius sprendimus tol, kol gali būti apibrėžta prasminga euristika.Optimizuota paieška:A* išlaiko prioritetinę tvarką, kad būtų galima pasirinkti mazgus su mažesne f(n) reikšme (g(n) ir h(n)) plėtrai. Tai leidžia pirmiausia ištirti perspektyvius kelius, o tai sumažina paieškos erdvę ir leidžia greičiau suartėti.Atminties efektyvumas:Skirtingai nuo kai kurių kitų paieškos algoritmų, pvz., paieškos pagal plotį, A* prioritetinėje eilėje išsaugo tik ribotą mazgų skaičių, todėl yra efektyvus atmintis, ypač esant dideliems grafikams.Derinama euristika:A* našumą galima tiksliai sureguliuoti pasirinkus skirtingas euristines funkcijas. Labiau išlavinta euristika gali lemti greitesnę konvergenciją ir mažiau išplėstus mazgus.Plačiai tyrinėta:A* yra gerai nusistovėjęs algoritmas, turintis dešimtmečius tyrimų ir praktinių pritaikymų. Buvo sukurta daug optimizacijų ir variantų, todėl tai patikimas ir gerai suprantamas trikčių šalinimo įrankis.Interneto paieška:A* gali būti naudojamas žiniatinklio kelių paieškai, kai algoritmas nuolat atnaujina kelią, atsižvelgdamas į aplinkos pokyčius ar naujų atsiradimą. Tai leidžia priimti sprendimus realiu laiku dinamiškuose scenarijuose.

A* paieškos algoritmo trūkumai dirbtinio intelekto srityje

Nors A* (raidės A) paieškos algoritmas yra plačiai naudojamas ir galingas būdas DI kelio paieškos ir grafiko perėjimo problemoms spręsti, jis turi trūkumų ir apribojimų. Štai keletas pagrindinių paieškos algoritmo trūkumų:

    Euristinis tikslumas:A* algoritmo našumas labai priklauso nuo euristinės funkcijos, naudojamos apskaičiuojant išlaidas nuo dabartinio mazgo iki dabartinio mazgo tikslumo. Jei euristika yra nepriimtina (niekada nepervertina faktinių išlaidų) arba nenuosekli (tenkina trikampio nelygybę), A*. gali nerasti optimalaus kelio arba ištirti daugiau mazgų nei reikia, o tai turės įtakos jo efektyvumui ir tikslumui.Atminties naudojimas:A* reikalauja, kad visi aplankyti mazgai būtų saugomi atmintyje, kad būtų galima sekti ištirtus kelius. Atminties naudojimas kartais gali tapti svarbia problema, ypač kai reikia daug paieškos vietos arba riboti atminties ištekliai.Laiko sudėtingumas:Nors A* paprastai yra efektyvus, jo sudėtingumas gali kelti susirūpinimą didelėse paieškos erdvėse ar grafikuose. Blogiausiu atveju A* gali užtrukti eksponentiškai ilgiau, kol suras optimalų kelią, jei euristika yra netinkama problemai spręsti.Kliūtis paskirties vietoje:Tam tikrais scenarijais A* algoritmas turi ištirti mazgus, esančius toli nuo paskirties vietos, kad galiausiai pasiektų paskirties regioną. Ši problema kyla, kai euristika turi anksti efektyviai nukreipti paiešką į tikslą.Išlaidų susiejimas:A* susiduria su sunkumais, kai keli mazgai turi tą pačią f reikšmę (faktinių išlaidų ir euristinių išlaidų suma). Naudojama strategija gali turėti įtakos atrasto kelio optimalumui ir efektyvumui. Jei netinkamai elgiamasi, gali būti tiriami nereikalingi mazgai ir sulėtėja algoritmas.Sudėtingumas dinamiškoje aplinkoje:Dinaminėje aplinkoje, kur paieškos metu gali keistis briaunų ar mazgų kaina, A* gali netikti, nes ji netinkamai prisitaiko prie tokių pokyčių. Performuliavimas nuo nulio gali būti brangus, todėl D* (Dynamic A*) algoritmai buvo sukurti tam išspręstiTobulumas begalinėje erdvėje:A* gali nerasti sprendimo begalinėje būsenų erdvėje. Tokiais atvejais jis gali veikti neribotą laiką, tyrinėdamas vis didesnį mazgų skaičių, nerasdamas sprendimo. Nepaisant šių trūkumų, A* vis dar yra tvirtas ir plačiai naudojamas algoritmas, nes jis gali veiksmingai rasti optimalius kelius daugelyje praktinių situacijų, jei euristinė funkcija yra gerai suplanuota ir paieškos erdvė yra valdoma. Siekiant sušvelninti kai kuriuos jo apribojimus, buvo pasiūlyti įvairūs A* variantai ir variantai.

A* paieškos algoritmo taikymas dirbtiniam intelektui

Paieškos algoritmas A* (A raidė) yra plačiai naudojamas ir patikimas kelio paieškos algoritmas dirbtinio intelekto ir kompiuterių mokslo srityse. Dėl savo efektyvumo ir optimalumo jis tinka įvairioms reikmėms. Štai keletas tipiškų A* paieškos algoritmo pritaikymų dirbtiniame intelekte:

    Kelio paieška žaidimuose:A* dažnai naudojamas vaizdo žaidimuose, skirtas veikėjų judėjimui, priešo AI navigacijai ir trumpiausio kelio iš vienos vietos į kitą paieškai žaidimo žemėlapyje. Dėl galimybės rasti optimalų kelią, pagrįstą sąnaudomis ir euristika, jis idealiai tinka realaus laiko programoms, pvz., žaidimams.Robotika ir autonominės transporto priemonės:A* naudojamas robotikoje ir autonominėje transporto priemonių navigacijoje, siekiant planuoti optimalų maršrutą robotams pasiekti tikslą, išvengiant kliūčių ir atsižvelgiant į vietovės išlaidas. Tai labai svarbu norint efektyviai ir saugiai judėti natūralioje aplinkoje.Labirinto sprendimas:A* gali efektyviai rasti trumpiausią kelią per labirintą, todėl jis naudingas daugelyje labirinto sprendimo programų, pavyzdžiui, sprendžiant galvosūkius ar naršant sudėtingose ​​struktūrose.Maršruto planavimas ir navigacija:GPS sistemose ir žemėlapių sudarymo programose A* gali būti naudojamas norint rasti optimalų maršrutą tarp dviejų taškų žemėlapyje, atsižvelgiant į tokius veiksnius kaip atstumas, eismo sąlygos ir kelių tinklo topologija.Galvosūkių sprendimas:A* gali išspręsti įvairius schemų galvosūkius, pvz., stumdomus galvosūkius, Sudoku ir 8 galvosūkių problemą. Išteklių paskirstymas: scenarijuose, kai ištekliai turi būti paskirstyti optimaliai, A* gali padėti rasti efektyviausią paskirstymo kelią, sumažinant išlaidas ir padidinant efektyvumą.Tinklo maršrutas:A* gali būti naudojamas kompiuterių tinkluose norint rasti efektyviausią maršrutą duomenų paketams iš šaltinio į paskirties mazgą.Natūralios kalbos apdorojimas (NLP):Kai kuriose NLP užduotyse A* gali generuoti nuoseklius ir kontekstinius atsakymus ieškodama galimų žodžių sekų pagal jų tikimybę ir aktualumą.Kelio planavimas robotikoje:A* gali būti naudojamas planuojant roboto kelią iš vieno taško į kitą, atsižvelgiant į įvairius suvaržymus, tokius kaip kliūčių išvengimas arba energijos suvartojimo sumažinimas.Žaidimo AI:A* taip pat naudojamas norint priimti protingus sprendimus dėl ne žaidėjų personažų (NPC), pvz., nustatyti geriausią būdą pasiekti tikslą arba koordinuoti judesius komandiniame žaidime.

Tai tik keli pavyzdžiai, kaip A* paieškos algoritmas randa pritaikymų įvairiose dirbtinio intelekto srityse. Dėl lankstumo, efektyvumo ir optimizavimo jis yra vertingas įrankis daugeliui problemų.

C programa, skirta dirbtinio intelekto A* paieškos algoritmui

 #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++ programa, skirta A* paieškos algoritmui dirbtinio intelekto srityje

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

Paaiškinimas:

    Struktūros mazgas:Tai apibrėžia mazgo struktūrą, vaizduojančią tinklelio langelį. Jame yra mazgo x ir y koordinatės, kaina g nuo pradinio mazgo iki to mazgo, euristinė reikšmė h (apskaičiuotos išlaidos nuo to mazgo iki paskirties mazgo) ir rodyklė į
  1. pradinis kelio mazgas.
  2. Apskaičiuokite euristiką:Ši funkcija apskaičiuoja euristiką, naudodama euklido atstumą tarp mazgo ir tikslinės AStarSearch: ši funkcija vykdo A* paieškos algoritmą. Ji paima pradžios ir tikslo koordinates, tinklelį ir grąžina porų vektorių, atspindintį trumpiausio kelio koordinates nuo pradžios iki pabaigos.Pagrindinis:Pagrindinė programos funkcija iš vartotojo paima įvesties tinklelius, pradžią ir tikslines koordinates. Tada ji skambina AStarSearch, kad surastų trumpiausią kelią ir išspausdina rezultatą. Struktūros mazgas: tai apibrėžia mazgo struktūrą, vaizduojančią tinklelio langelį. Jame yra mazgo x ir y koordinatės, kaina g nuo pradinio mazgo iki to mazgo, euristinė reikšmė h (apskaičiuota kaina nuo to mazgo iki paskirties mazgo) ir žymeklis į pradinį kelio mazgą.Apskaičiuokite euristiką:Ši funkcija apskaičiuoja euristiką, naudodama euklido atstumą tarp mazgo ir tikslinės AStarSearch: ši funkcija vykdo A* paieškos algoritmą. Ji paima pradžios ir tikslo koordinates, tinklelį ir grąžina porų vektorių, atspindintį trumpiausio kelio koordinates nuo pradžios iki pabaigos.

Pavyzdžio išvestis

 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 programa, skirta dirbtinio intelekto A* paieškos algoritmui

 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* Paieškos algoritmo sudėtingumas dirbtinio intelekto srityje

A* (tariama „A žvaigždutė“) paieškos algoritmas yra populiarus ir plačiai naudojamas grafiko perėjimo ir kelio paieškos algoritmas dirbtiniame intelekte. Paprastai įprasta rasti trumpiausią kelią tarp dviejų mazgų grafoje arba tinklelio aplinkoje. Algoritmas sujungia Dijkstra ir gobšus geriausius pirmiausia paieškos elementus, kad ištirtų paieškos erdvę ir efektyviai užtikrintų optimalumą. Keletas veiksnių lemia A* paieškos algoritmo sudėtingumą. Grafiko dydis (mazgai ir briaunos): grafiko mazgų ir briaunų skaičius labai veikia algoritmo sudėtingumą. Daugiau mazgų ir kraštų reiškia daugiau galimų tyrinėti parinkčių, o tai gali padidinti algoritmo vykdymo laiką.

Euristinė funkcija: A* naudoja euristinę funkciją (dažnai žymima h(n)), kad įvertintų išlaidas nuo dabartinio mazgo iki paskirties mazgo. Šios euristikos tikslumas labai veikia A* paieškos efektyvumą. Gera euristika gali padėti greičiau nukreipti paiešką iki tikslo, o bloga euristika gali sukelti nereikalingą paiešką.

    Duomenų struktūros:A* palaiko dvi pagrindinių duomenų struktūras: atvirą sąrašą (prioritetinė eilė) ir uždarą sąrašą (arba aplankytą telkinį). Šių duomenų struktūrų efektyvumas kartu su pasirinktu įgyvendinimu (pvz., prioritetinės eilės dvejetainės krūvos) turi įtakos algoritmo veikimui.Filialo faktorius:Vidutinis kiekvieno mazgo sekėjų skaičius turi įtakos paieškos metu išplėstų mazgų skaičiui. Didesnis šakojimosi veiksnys gali paskatinti daugiau tyrinėti, o tai didėjaOptimalumas ir išsamumas:A* garantuoja ir optimalumą (trumpiausio kelio radimas), ir užbaigtumą (esamo sprendimo radimą). Tačiau ši garantija susijusi su kompromisu dėl skaičiavimo sudėtingumo, nes algoritmas turi ištirti skirtingus optimalaus veikimo būdus. Kalbant apie laiko sudėtingumą, pasirinkta euristinė funkcija blogiausiu atveju paveikia A*. Naudodamas priimtą euristiką (kuri niekada nepervertina tikrosios tikslo pasiekimo kainos), A* išplečia mažiausiai mazgų tarp optimizavimo algoritmų. Blogiausio atvejo laiko sudėtingumas A * yra eksponentinis blogiausiu atveju O(b ^ d), kur „b“ yra efektyvusis šakojimosi koeficientas (vidutinis sekėjų skaičius mazge), o „d“ yra optimalus.

Tačiau praktikoje A* dažnai veikia žymiai geriau dėl euristinės funkcijos, kuri padeda nukreipti algoritmą į perspektyvius kelius. Gerai suplanuotos euristikos atveju efektyvus šakojimosi koeficientas yra daug mažesnis, todėl greičiau pasiekiamas optimalus sprendimas.

k artimiausio kaimyno algoritmas