logo

A* Keresési algoritmus a mesterséges intelligenciában

Bevezetés az A* keresési algoritmusba az AI-ban

Az A* (ejtsd: „A-csillag”) egy hatékony gráfbejárási és útkereső algoritmus, amelyet széles körben használnak a mesterséges intelligenciában és a számítástechnikában. Főleg a gráf két csomópontja közötti legrövidebb út megkeresésére szolgál, figyelembe véve az aktuális csomóponttól a célcsomópontig való eljutás becsült költségét. Az algoritmus fő előnye, hogy a hagyományos keresési algoritmusokhoz, például a Dijkstra-algoritmushoz képest képes optimális útvonalat biztosítani a gráf tájékozottabb feltárásával.

Az A* algoritmus két másik keresési algoritmus előnyeit ötvözi: a Dijkstra-algoritmus és a Greedy Best-First Search. Dijkstra algoritmusához hasonlóan az A* is gondoskodik arról, hogy a talált útvonal a lehető legrövidebb legyen, de ezt hatékonyabban teszi azáltal, hogy a keresést a Greedy Best-First Search-hez hasonló heurisztikán keresztül irányítja. A h(n) heurisztikus függvény megbecsüli az adott n csomópontból a célcsomóponthoz való eljutás költségét.

Az A* fő ötlete az, hogy minden csomópontot két paraméter alapján értékeljen:

youtube vlc médialejátszó letöltése
    g(n):a kezdeti csomóponttól az n csomópontig való eljutás tényleges költsége. Ez az n csomópont kimenő élének költségeinek összege.h(n):Heurisztikus költség (más néven „becslési költség”) az n csomóponttól az n. célcsomópontig. Ennek a probléma-specifikus heurisztikus függvénynek elfogadhatónak kell lennie, vagyis soha nem becsüli túl a cél elérésének tényleges költségét. Az n csomópont kiértékelési függvénye f(n) = g(n) h(n).

Az A* algoritmus az f(n) legalacsonyabb értéke alapján választja ki a felderítendő csomópontokat, előnyben részesítve a legalacsonyabb becsült összköltséggel rendelkező csomópontokat a cél eléréséhez. Az A* algoritmus működik:

  1. Hozzon létre egy nyílt listát a talált, de fel nem fedezett csomópontokról.
  2. Hozzon létre egy zárt listát a már feltárt csomópontok tárolására.
  3. Adjon hozzá egy kezdőcsomópontot a nyitott listához g kezdeti értékkel
  4. Ismételje meg a következő lépéseket, amíg a nyitott lista ki nem ürül, vagy el nem éri a célcsomópontot:
    1. Keresse meg a legkisebb f értékű csomópontot (azaz a kisebb g(n) h(n) csomópontot) a nyílt listában.
    2. Helyezze át a kiválasztott csomópontot a nyitott listából a zárt listába.
    3. A kiválasztott csomópont összes érvényes leszármazottjának létrehozása.
    4. Minden utód esetében a g-értéket az aktuális csomópont g értékének és az aktuális csomópontról az utódcsomópontra való áthelyezés költségének összegeként számítja ki. Frissítse a nyomkövető g-értékét, ha jobb elérési utat talál.
    5. Ha a követő nem szerepel a nyitott listában, adja hozzá a számított g-értékkel és számítsa ki a h-értékét. Ha már szerepel a nyitott listában, frissítse a g értékét, ha az új elérési út jobb.
    6. Ismételje meg a ciklust. Az A* algoritmus akkor fejeződik be, amikor elérjük a célcsomópontot, vagy amikor a nyitott lista kiürül, jelezve, hogy nincs útvonal a kezdő csomóponttól a célcsomópontig. Az A* keresési algoritmust széles körben használják különféle területeken, mint például a robotika, a videojátékok, a hálózati útválasztás és a tervezési problémák, mivel hatékony, és képes megtalálni az optimális útvonalakat a gráfokban vagy hálózatokban.

A megfelelő és elfogadható heurisztikus függvény kiválasztása azonban elengedhetetlen ahhoz, hogy az algoritmus megfelelően működjön és optimális megoldást nyújtson.

Tájékozott keresési algoritmusok

Az A* keresési algoritmus története a mesterséges intelligenciában

Peter Hart, Nils Nilsson és Bertram Raphael fejlesztette ki a Stanford Research Institute-nál (ma SRI International), Dijkstra algoritmusának és más korabeli keresési algoritmusainak kiterjesztéseként. Az A*-t először 1968-ban tették közzé, és hamar elismerést szerzett fontosságáért és hatékonyságáért a mesterséges intelligencia és a számítástechnikai közösségekben. Íme egy rövid áttekintés az A* keresési algoritmus történetének legkritikusabb mérföldköveiről:

    Korai keresési algoritmusok:Az A* kifejlesztése előtt különféle gráfkereső algoritmusok léteztek, köztük a mélységi keresés (DFS) és a Breadth-First Search (BFS). Bár ezek az algoritmusok segítettek megtalálni az utakat, nem garantálták az optimalitást, és nem vették figyelembe a keresést irányító heurisztikát.Dijkstra algoritmusa:1959-ben Edsger W. Dijkstra holland informatikus bemutatta Dijkstra algoritmusát, amely egy súlyozott gráfban találta meg a legrövidebb utat nem negatív élsúlyokkal. Dijkstra algoritmusa hatékony volt, de kimerítő jellege miatt korlátai voltak, amikor nagyobb gráfokon ill.Tájékozott keresés:Tudásalapú keresési algoritmusokat (más néven heurisztikus keresést) fejlesztettek ki a heurisztikus információk, például a becsült költségek beépítésére a keresési folyamat hatékony irányításához. A Greedy Best-First Search volt az egyik ilyen algoritmus, de nem garantálta az optimálisságot a legrövidebb út megtalálásához.A* fejlesztés:1968-ban Peter Hart, Nils Nilsson és Bertram Raphael bevezette az A* algoritmust a Dijkstra algoritmus és a Greedy Best-First Search kombinációjaként. Az A* egy heurisztikus függvény segítségével becsülte meg az aktuális csomóponttól a célcsomópontig tartó költséget, kombinálva azt az aktuális csomópont elérésének tényleges költségével. Ez lehetővé tette A* számára a gráf tudatosabb feltárását, elkerülve a felesleges utakat és garantálva az optimális megoldást.Igazság és tökéletesség:Az A* szerzői kimutatták, hogy az algoritmus bizonyos feltételek mellett tökéletes (mindig talál megoldást, ha létezik) és optimális (megtalálja a legrövidebb utat).Széles körű elfogadás és előrehaladás:Az A* gyorsan népszerűvé vált a mesterséges intelligencia és az informatikai közösségek körében hatékonyságának köszönhetően, és a kutatók és fejlesztők kiterjesztették és alkalmazták az A* algoritmust különböző területekre, beleértve a robotikát, a videojátékokat, a mérnöki munkát és a hálózati útválasztást. Az évek során az A* algoritmus számos változatát és optimalizálását javasolták, mint például az Inkrementális A* és a Párhuzamos A*. Az A* keresési algoritmus ma is alapvető és széles körben használt algoritmus a mesterséges intelligencia és a gráfbejárás terén. Továbbra is alapvető szerepet játszik különböző alkalmazásokban és kutatási területeken. A mesterséges intelligenciára gyakorolt ​​hatása, valamint az útkeresési és optimalizálási problémákhoz való hozzájárulása az intelligens rendszerek kutatásának sarokkövévé tették.

Hogyan működik az A* keresési algoritmus a mesterséges intelligenciában?

Az A* (ejtsd: 'A betű') keresési algoritmus egy népszerű és széles körben használt gráfbejárási algoritmus a mesterséges intelligencia és a számítástechnika területén. Arra használják, hogy megtalálják a legrövidebb utat a kezdő csomóponttól a célcsomópontig egy súlyozott gráfban. Az A* egy tájékozott keresési algoritmus, amely heurisztikát használ a keresés hatékony irányításához. Az A* keresési algoritmus a következőképpen működik:

Az algoritmus egy prioritási sorral indul a feltárandó csomópontok tárolására. Két g(n) adatstruktúrát is példányosít: a kezdő csomóponttól az n csomópontig és h(n) a legrövidebb út költsége, az n csomóponttól a célcsomópontig becsült költség (heurisztika). Ez gyakran ésszerű heurisztika, ami azt jelenti, hogy soha nem becsüli túl a cél elérésének tényleges költségeit. Helyezze a kezdeti csomópontot a prioritási sorba, és állítsa g(n) értékét 0-ra. Ha a prioritási sor nem üres, távolítsa el a legalacsonyabb f(n) értékkel rendelkező csomópontot a prioritási sorból. f(n) = g(n) h(n). Ha a törölt csomópont a célcsomópont, az algoritmus véget ér, és a rendszer megtalálja az elérési utat. Ellenkező esetben bontsa ki a csomópontot, és hozzon létre szomszédokat. Minden szomszédos csomóponthoz számítsa ki a kezdeti g(n) értékét, amely az aktuális csomópont g értékének és az aktuális csomópontról a szomszédos csomópontra való áthelyezés költségének összege. Ha a szomszédos csomópont nincs prioritási sorrendben, vagy az eredeti g(n) érték kisebb, mint az aktuális g érték, frissítse a g értékét, és állítsa szülőcsomópontját az aktuális csomópontra. Számítsa ki az f(n) értéket a szomszéd csomópontból, és adja hozzá a prioritási sorhoz.

Ha a ciklus a célcsomópont megtalálása nélkül ér véget, a gráfnak nincs elérési útja az elejétől a végéig. Az A* hatékonyságának kulcsa egy h(n) heurisztikus függvény használata, amely becslést ad bármely csomópont céljának eléréséhez szükséges fennmaradó költségekről. A g (n) tényleges költség és a h (n) heurisztikus költség kombinálásával az algoritmus hatékonyan tárja fel az ígéretes utakat, prioritást adva a valószínűleg a legrövidebb úthoz vezető csomópontoknak. Fontos megjegyezni, hogy az A* algoritmus hatékonysága nagymértékben függ a heurisztikus függvény megválasztásától. Az elfogadható heurisztika biztosítja, hogy az algoritmus mindig a legrövidebb utat találja meg, de a tájékozottabb és pontosabb heurisztika gyorsabb konvergenciát és csökkentett keresési teret eredményezhet.

Az A* keresési algoritmus előnyei a mesterséges intelligenciában

Az A* keresési algoritmus számos előnnyel jár a mesterséges intelligencia és a problémamegoldó forgatókönyvekben:

    Optimális megoldás:Az A* biztosítja az optimális (legrövidebb) útvonal megtalálását a kezdő csomóponttól a célcsomópontig a súlyozott gráfban, elfogadható heurisztikus függvény mellett. Ez az optimálisság döntő előnyt jelent számos olyan alkalmazásban, ahol elengedhetetlen a legrövidebb út megtalálása.Teljesség:Ha létezik megoldás, A* meg fogja találni, feltéve, hogy a gráfnak nincs végtelen költsége. Ez a teljességi tulajdonság biztosítja, hogy A* kihasználhassa a megoldást, ha létezik.Hatékonyság:Az A* hatékony, ha hatékony és elfogadható heurisztikus függvényt használunk. A heurisztika a célhoz irányítja a keresést azáltal, hogy az ígéretes utakra összpontosít, és elkerüli a szükségtelen feltárást, ezáltal hatékonyabbá teszi az A*-t, mint a nem tudatos keresési algoritmusok, mint például a szélességi keresés vagy a mélység szerinti keresés.Sokoldalúság:Az A* széles körben alkalmazható különféle problématerületeken, beleértve az útkeresést, az útvonaltervezést, a robotikát, a játékfejlesztést és még sok mást. Az A* használható optimális megoldások hatékony megtalálására mindaddig, amíg egy értelmes heurisztika definiálható.Optimalizált keresés:Az A* prioritási sorrendet tart fenn a kisebb f(n) értékű csomópontok (g(n) és h(n)) kiválasztásához a bővítéshez. Ez lehetővé teszi, hogy először fedezze fel az ígéretes utakat, ami csökkenti a keresési teret és gyorsabb konvergenciához vezet.Memória hatékonyság:Ellentétben néhány más keresési algoritmussal, mint például a szélességi kereséssel, az A* csak korlátozott számú csomópontot tárol a prioritási sorban, ami memóriatakarékossá teszi, különösen nagy grafikonok esetén.Hangolható heurisztika:Az A* teljesítménye különböző heurisztikus függvények kiválasztásával finomhangolható. Az alaposabb heurisztika gyorsabb konvergenciához és kevésbé bővített csomópontokhoz vezethet.Alaposan kutatott:Az A* egy jól bevált algoritmus több évtizedes kutatással és gyakorlati alkalmazásokkal. Számos optimalizálást és variációt fejlesztettek ki, így megbízható és jól érthető hibaelhárítási eszköz.Internetes keresés:Az A* használható web alapú útvonalkeresésre, ahol az algoritmus folyamatosan frissíti az útvonalat a környezet változásainak vagy az új megjelenésének megfelelően. Lehetővé teszi a valós idejű döntéshozatalt dinamikus forgatókönyvekben.

Az A* keresési algoritmus hátrányai a mesterséges intelligenciában

Bár az A* (A betű) keresési algoritmus egy széles körben használt és hatékony technika az AI útkeresési és gráfbejárási problémák megoldására, vannak hátrányai és korlátai. Íme néhány fő hátránya a keresési algoritmusnak:

    Heurisztikus pontosság:Az A* algoritmus teljesítménye nagymértékben függ annak a heurisztikus függvénynek a pontosságától, amelyet az aktuális csomóponttól a költségbecsléshez használnak. Ha a heurisztika elfogadhatatlan (soha nem becsüli túl a tényleges költséget) vagy inkonzisztens (elégíti a háromszög egyenlőtlenséget), A* Előfordulhat, hogy nem talál optimális utat, vagy a szükségesnél több csomópontot kutat fel, ami befolyásolja annak hatékonyságát és pontosságát.Memóriahasználat:Az A* megköveteli, hogy minden meglátogatott csomópont a memóriában legyen a feltárt útvonalak nyomon követése érdekében. A memóriahasználat néha jelentős problémát jelenthet, különösen akkor, ha bőséges keresési helyről vagy korlátozott memóriaerőforrásokról van szó.Időbeli összetettség:Bár az A* általában hatékony, időbeli összetettsége aggodalomra ad okot a hatalmas keresési terek vagy grafikonok esetében. A legrosszabb esetben az A*-nak exponenciálisan tovább tart az optimális út megtalálása, ha a heurisztika nem megfelelő a problémához.Szűk keresztmetszetek a célállomáson:Bizonyos forgatókönyvekben az A* algoritmusnak fel kell fedeznie a céltól távol eső csomópontokat, mielőtt végül elérné a célterületet. Ez a probléma akkor jelentkezik, ha a heurisztikának hatékonyan korán a célra kell irányítania a keresést.Költségkötés:Az A* nehézségekkel szembesül, ha több csomópontnak ugyanaz az f-értéke (a tényleges költség és a heurisztikus költség összege). Az alkalmazott stratégia befolyásolhatja a felfedezett út optimálisságát és hatékonyságát. Ha nem kezelik megfelelően, szükségtelen csomópontok felfedezéséhez vezethet, és lelassítja az algoritmust.Komplexitás dinamikus környezetben:Dinamikus környezetben, ahol az élek vagy csomópontok költsége változhat a keresés során, előfordulhat, hogy az A* nem megfelelő, mert nem alkalmazkodik jól az ilyen változásokhoz. A nulláról történő újratervezés számítási szempontból költséges lehet, és ennek megoldására a D* (Dynamic A*) algoritmusokat tervezték.Tökéletesség a végtelen térben:Előfordulhat, hogy A* nem talál megoldást a végtelen állapottérben. Ilyenkor korlátlan ideig futhat, egyre növekvő számú csomópontot tár fel anélkül, hogy megoldást találna. E hiányosságok ellenére az A* továbbra is egy robusztus és széles körben használt algoritmus, mert számos gyakorlati helyzetben hatékonyan képes megtalálni az optimális útvonalat, ha a heurisztikus függvény jól megtervezett és a keresési terület kezelhető. Az A* különféle változatait és változatait javasolták egyes korlátainak enyhítésére.

Az A* keresési algoritmus alkalmazásai a mesterséges intelligenciában

Az A* keresőalgoritmus (A betű) egy széles körben használt és robusztus útkereső algoritmus a mesterséges intelligencia és a számítástechnika területén. Hatékonysága és optimálissága alkalmassá teszi különféle alkalmazásokhoz. Íme az A* keresőalgoritmus néhány tipikus alkalmazása a mesterséges intelligenciában:

    Útkeresés a játékokban:Az A*-t gyakran használják videojátékokban a karakterek mozgatására, az ellenséges mesterséges intelligencia navigációjára, valamint az egyik helytől a másikig vezető legrövidebb út megtalálásához a játéktérképen. Az a képessége, hogy megtalálja az optimális utat a költségek és a heurisztika alapján, ideálissá teszi valós idejű alkalmazásokhoz, például játékokhoz.Robotika és autonóm járművek:Az A* a robotikában és az autonóm járműnavigációban használatos, hogy optimális útvonalat tervezzenek a robotok számára a cél eléréséhez, elkerülve az akadályokat és figyelembe véve a terepköltségeket. Ez elengedhetetlen a hatékony és biztonságos mozgáshoz természetes környezetben.Labirintus megoldása:Az A* hatékonyan képes megtalálni a legrövidebb utat egy labirintuson keresztül, így számos labirintusmegoldó alkalmazásban értékes, például rejtvények megoldásában vagy összetett szerkezetekben való navigálásban.Útvonaltervezés és navigáció:GPS-rendszerekben és térképészeti alkalmazásokban az A* használható a térkép két pontja közötti optimális útvonal megkeresésére, figyelembe véve olyan tényezőket, mint a távolság, a forgalmi viszonyok és az úthálózat topológiája.Rejtvényfejtés:Az A* különféle diagramrejtvényeket tud megoldani, például csúszórejtvényeket, Sudokut és a 8 rejtvényes feladatot. Erőforrás-allokáció: Azokban a forgatókönyvekben, ahol az erőforrásokat optimálisan kell elosztani, az A* segíthet megtalálni a leghatékonyabb elosztási utat, minimalizálva a költségeket és maximalizálva a hatékonyságot.Hálózati útválasztás:Az A* használható számítógépes hálózatokban az adatcsomagok leghatékonyabb útvonalának megtalálására a forrástól a célcsomópontig.Természetes nyelvi feldolgozás (NLP):Egyes NLP-feladatokban az A* koherens és kontextuális válaszokat generálhat, ha lehetséges szósorozatokat keres azok valószínűsége és relevanciája alapján.Útvonaltervezés a robotikában:Az A* segítségével megtervezheti a robot útvonalát egyik ponttól a másikig, figyelembe véve a különféle korlátokat, például az akadályok elkerülését vagy az energiafogyasztás minimalizálását.Játék AI:Az A*-t arra is használják, hogy intelligens döntéseket hozzanak a nem játékos karakterek (NPC-k) esetében, például meghatározzák a cél elérésének vagy a mozgások összehangolásának legjobb módját egy csapatalapú játékban.

Ez csak néhány példa arra, hogyan talál alkalmazásokat az A* keresőalgoritmus a mesterséges intelligencia különböző területein. Rugalmassága, hatékonysága és optimalizálása értékes eszközzé teszik számos probléma megoldásában.

C program az A* keresési algoritmushoz a mesterséges intelligenciában

 #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 A* Search Algorithm in Artificial Intelligence

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

Magyarázat:

    Struktúra csomópont:Ez meghatároz egy csomóponti struktúrát, amely egy rácscellát képvisel. Tartalmazza a csomópont x és y koordinátáit, a kezdő csomóponttól a csomópontig tartó g költséget, a h heurisztikus értéket (az adott csomóponttól a célcsomópontig becsült költség), valamint egy mutatót a
  1. az útvonal kezdő csomópontja.
  2. Heurisztika kiszámítása:Ez a függvény a csomópont és a célpont közötti euklideszi távolság alapján számít ki egy heurisztikát. AStarSearch: Ez a függvény az A* keresési algoritmust futtatja. Felveszi a kiindulási és cél koordinátákat, egy rácsot, és visszaadja a párok vektorát, amely a legrövidebb út koordinátáit képviseli az elejétől a végéig.Elsődleges:A program fő funkciója bemeneti rácsokat, origót és célkoordinátákat vesz a felhasználótól. Ezután meghívja az AStarSearch-t, hogy megtalálja a legrövidebb utat, és kinyomtatja az eredményt. Struktúra csomópont: Ez meghatároz egy csomóponti struktúrát, amely egy rácscellát képvisel. Tartalmazza a csomópont x és y koordinátáit, a kezdő csomóponttól az adott csomópontig tartó g költséget, a h heurisztikus értéket (az adott csomóponttól a célcsomópontig becsült költség), valamint egy mutatót az útvonal kezdő csomópontjára.Heurisztika kiszámítása:Ez a függvény a heurisztikát a csomópont és a célpont közötti euklideszi távolság alapján számítja ki. AStarSearch: Ez a függvény az A* keresési algoritmust futtatja. Felveszi a kiindulási és cél koordinátákat, egy rácsot, és visszaadja a párok vektorát, amely a legrövidebb út koordinátáit képviseli az elejétől a végéig.

Minta kimenet

 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 A* keresési algoritmushoz a mesterséges intelligenciában

 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* Keresési algoritmusok összetettsége a mesterséges intelligenciában

Az A* (ejtsd: „A-csillag”) keresési algoritmus egy népszerű és széles körben használt gráfbejárási és útvonalkereső algoritmus a mesterséges intelligenciában. Általában gyakori a legrövidebb út megtalálása két csomópont között egy gráf- vagy rácsalapú környezetben. Az algoritmus a Dijkstra és a mohó legjobb első keresési elemeket kombinálja a keresési terület felderítésére, miközben hatékonyan biztosítja az optimalitást. Az A* keresési algoritmus bonyolultságát számos tényező határozza meg. Gráf mérete (csomópontok és élek): A gráf csomópontjainak és éleinek száma nagyban befolyásolja az algoritmus bonyolultságát. Több csomópont és él több lehetséges felfedezési lehetőséget jelent, ami növelheti az algoritmus végrehajtási idejét.

Heurisztikus függvény: Az A* egy heurisztikus függvényt (gyakran h(n)-nek jelölve) használ az aktuális csomóponttól a célcsomópontig terjedő költségek becslésére. A heurisztika pontossága nagyban befolyásolja az A* keresés hatékonyságát. Egy jó heurisztika segíthet a keresés gyorsabb célhoz irányításában, míg a rossz heurisztika szükségtelen kereséshez vezethet.

cast string mint int java
    Adatstruktúrák:Az A* két főadat-struktúrát tart fenn: egy nyílt listát (prioritási sor) és egy zárt listát (vagy látogatott készletet). Ezeknek az adatstruktúráknak a hatékonysága, valamint a választott megvalósítás (pl. prioritási sor bináris kupacok) befolyásolja az algoritmus teljesítményét.Ágazati tényező:Az egyes csomópontokhoz tartozó követők átlagos száma befolyásolja a keresés során kibővített csomópontok számát. A magasabb elágazási tényező több feltáráshoz vezethet, ami növekszikOptimalitás és teljesség:Az A* garantálja az optimalitást (a legrövidebb út megtalálása) és a teljességet (a létező megoldás megtalálását). Ez a garancia azonban kompromisszumot jelent a számítási bonyolultság tekintetében, mivel az algoritmusnak különböző utakat kell feltárnia az optimális teljesítmény érdekében. Az időbonyolultság tekintetében a választott heurisztikus függvény legrosszabb esetben A*-ra hat. Egy elfogadott heurisztikával (amely soha nem becsüli túl a cél elérésének valódi költségeit) az A* kiterjeszti a legkevesebb csomópontot az optimalizálási algoritmusok közül. A * legrosszabb eseti időbonyolultsága exponenciális a legrosszabb eset O(b ^ d) esetén, ahol 'b' az effektív elágazási tényező (a követők átlagos száma csomópontonként), és 'd' az optimális

A gyakorlatban azonban az A* gyakran szignifikánsan jobban teljesít egy heurisztikus függvény hatására, amely segít az algoritmust ígéretes útvonalakra terelni. Egy jól megtervezett heurisztika esetén az effektív elágazási tényező sokkal kisebb, ami az optimális megoldás gyorsabb megközelítéséhez vezet.