logo

A* Hakualgoritmi tekoälyssä

Johdatus tekoälyn A*-hakualgoritmiin

A* (lausutaan 'A-tähti') on tehokas graafin läpikulku- ja polunhakualgoritmi, jota käytetään laajalti tekoälyssä ja tietojenkäsittelytieteessä. Sitä käytetään pääasiassa lyhimmän polun löytämiseen kaavion kahden solmun välillä, kun otetaan huomioon arvioidut kustannukset päästä nykyisestä solmusta kohdesolmuun. Algoritmin tärkein etu on sen kyky tarjota optimaalinen polku tutkimalla kuvaajaa tietoisemmin verrattuna perinteisiin hakualgoritmeihin, kuten Dijkstran algoritmiin.

Algoritmi A* yhdistää kahden muun hakualgoritmin edut: Dijkstran algoritmin ja Greedy Best-First Searchin. Kuten Dijkstran algoritmi, A* varmistaa, että löydetty polku on mahdollisimman lyhyt, mutta tekee sen tehokkaammin ohjaamalla sen haun heuristisen avulla, joka on samanlainen kuin Greedy Best-First Search. Heuristinen funktio, jota merkitään h(n), arvioi kustannukset, jotka aiheutuvat pääsystä mistä tahansa tietystä solmusta n kohdesolmuun.

A*:n pääideana on arvioida jokainen solmu kahden parametrin perusteella:

arp-a-komento
    g(n):todelliset kustannukset päästä alkusolmusta solmuun n. Se edustaa solmun n lähtevän reunan kustannusten summaa.h n):Heuristiset kustannukset (tunnetaan myös nimellä 'arviointikustannukset') solmusta n kohdesolmuun n. Tämän ongelmakohtaisen heuristisen funktion on oltava hyväksyttävä, eli se ei koskaan yliarvioi tavoitteen saavuttamisen todellisia kustannuksia. Solmun n arviointifunktio määritellään f(n) = g(n) h(n).

Algoritmi A* valitsee tutkittavat solmut f(n:n) alimman arvon perusteella ja suosii solmuja, joiden arvioidut kokonaiskustannukset ovat alhaisimmat tavoitteen saavuttamiseksi. A*-algoritmi toimii:

  1. Luo avoin luettelo löydetyistä, mutta tutkimattomista solmuista.
  2. Luo suljettu luettelo jo tutkittujen solmujen säilyttämistä varten.
  3. Lisää avoimeen listaan ​​aloitussolmu, jonka alkuarvo on g
  4. Toista seuraavat vaiheet, kunnes avoin luettelo on tyhjä tai saavutat kohdesolmun:
    1. Etsi avoimesta luettelosta solmu, jolla on pienin f-arvo (eli solmu, jolla on pieni g(n) h(n)).
    2. Siirrä valittu solmu avoimesta luettelosta suljettuun luetteloon.
    3. Luo valitun solmun kaikki kelvolliset jälkeläiset.
    4. Laskee kullekin seuraajalle g-arvon nykyisen solmun g-arvon ja nykyisestä solmusta seuraajasolmuun siirtymiskustannusten summana. Päivitä seurantalaitteen g-arvo, kun parempi polku löytyy.
    5. Jos seuraaja ei ole avoimessa listassa, lisää se lasketun g-arvon kanssa ja laske sen h-arvo. Jos se on jo avoimessa luettelossa, päivitä sen g-arvo, jos uusi polku on parempi.
    6. Toista sykli. Algoritmi A* päättyy, kun kohdesolmu saavutetaan tai kun avoin lista tyhjenee, mikä osoittaa, ettei aloitussolmusta kohdesolmuun ole polkuja. A*-hakualgoritmia käytetään laajasti eri aloilla, kuten robotiikassa, videopeleissä, verkkoreitityksessä ja suunnitteluongelmissa, koska se on tehokas ja pystyy löytämään optimaaliset polut kaavioista tai verkoista.

Sopivan ja hyväksyttävän heuristisen funktion valinta on kuitenkin välttämätöntä, jotta algoritmi toimii oikein ja tarjoaa optimaalisen ratkaisun.

Tietojen hakualgoritmit

A*-hakualgoritmin historia tekoälyssä

Sen kehittivät Peter Hart, Nils Nilsson ja Bertram Raphael Stanfordin tutkimusinstituutissa (nykyisin SRI International) Dijkstran algoritmin ja muiden sen aikaisten hakualgoritmien jatkeeksi. A* julkaistiin ensimmäisen kerran vuonna 1968 ja sai nopeasti tunnustusta merkityksestään ja tehokkuudestaan ​​tekoäly- ja tietotekniikan yhteisöissä. Tässä on lyhyt katsaus hakualgoritmin A* historian kriittisimmistä virstanpylväistä:

    Varhaiset hakualgoritmit:Ennen A*:n kehittämistä oli olemassa erilaisia ​​graafisen hakualgoritmeja, mukaan lukien Depth-First Search (DFS) ja Breadth-First Search (BFS). Vaikka nämä algoritmit auttoivat löytämään polkuja, ne eivät takaaneet optimaalisuutta tai ottaneet huomioon heuristiikkaa hakua ohjaamassa.Dijkstran algoritmi:Vuonna 1959 hollantilainen tietojenkäsittelytieteilijä Edsger W. Dijkstra esitteli Dijkstran algoritmin, joka löysi lyhimmän polun painotetussa graafissa, jossa on ei-negatiiviset reunapainot. Dijkstran algoritmi oli tehokas, mutta kattavan luonteensa vuoksi sillä oli rajoituksia käytettäessä suurempia kaavioita taiTietoinen haku:Tietopohjaiset hakualgoritmit (tunnetaan myös nimellä heuristinen haku) on kehitetty sisällyttämään heuristisia tietoja, kuten arvioituja kustannuksia, ohjaamaan hakuprosessia tehokkaasti. Greedy Best-First Search oli yksi tällainen algoritmi, mutta se ei takaanut optimaalisuutta lyhimmän polun löytämiseksi.A* kehitys:Vuonna 1968 Peter Hart, Nils Nilsson ja Bertram Raphael esittelivät A*-algoritmin Dijkstran algoritmin ja Greedy Best-First Searchin yhdistelmänä. A* käytti heuristista funktiota arvioidakseen kustannukset nykyisestä solmusta kohdesolmuun yhdistämällä ne nykyisen solmun saavuttamisen todellisiin kustannuksiin. Tämä antoi A*:lle mahdollisuuden tutkia kuvaajaa tietoisemmin, välttäen tarpeettomia polkuja ja taatamalla optimaalisen ratkaisun.Vanhurskaus ja täydellisyys:A*:n kirjoittajat osoittivat, että algoritmi on täydellinen (löytää aina ratkaisun, jos sellainen on olemassa) ja optimaalinen (löytää lyhimmän polun) tietyissä olosuhteissa.Laaja omaksuminen ja edistyminen:A* saavutti nopeasti suosion tekoäly- ja IT-yhteisöissä tehokkuutensa ansiosta. Tutkijat ja kehittäjät ovat laajentaneet ja soveltaneet A*-algoritmia useilla aloilla, kuten robotiikassa, videopeleissä, suunnittelussa ja verkon reitityksessä. A*-algoritmille on vuosien varrella ehdotettu useita muunnelmia ja optimointeja, kuten Incremental A* ja Parallel A*. Nykyään A*-hakualgoritmi on edelleen perustavanlaatuinen ja laajalti käytetty algoritmi tekoälyssä ja graafien läpikäymisessä. Sillä on edelleen keskeinen rooli erilaisissa sovelluksissa ja tutkimusaloilla. Sen vaikutus tekoälyyn ja sen panos polunhaku- ja optimointiongelmiin ovat tehneet siitä älykkäiden järjestelmien tutkimuksen kulmakivialgoritmin.

Kuinka A*-hakualgoritmi toimii tekoälyssä?

A* (lausutaan 'kirjain A') -hakualgoritmi on suosittu ja laajalti käytetty graafin läpikulkualgoritmi tekoälyssä ja tietojenkäsittelytieteessä. Sitä käytetään lyhimmän polun etsimiseen aloitussolmusta kohdesolmuun painotetussa kaaviossa. A* on tietoinen hakualgoritmi, joka ohjaa haun tehokkaasti heuristiikan avulla. Hakualgoritmi A* toimii seuraavasti:

Algoritmi alkaa prioriteettijonolla tutkittavien solmujen tallentamiseksi. Se myös instantoi kaksi tietorakennetta g(n): Toistaiseksi lyhimmän polun hinta aloitussolmusta solmuun n ja h(n), arvioitu kustannus (heuristinen) solmusta n kohdesolmuun. Se on usein järkevä heuristiikka, mikä tarkoittaa, että se ei koskaan yliarvioi tavoitteen saavuttamisen todellisia kustannuksia. Aseta ensimmäinen solmu prioriteettijonoon ja aseta sen g(n) arvoon 0. Jos prioriteettijono ei ole tyhjä, poista prioriteettijonosta solmu, jolla on pienin f(n). f(n) = g(n) h(n). Jos poistettu solmu on kohdesolmu, algoritmi päättyy ja polku löydetään. Muussa tapauksessa laajenna solmu ja luo sen naapurit. Laske jokaiselle naapurisolmulle sen alkuperäinen g(n)-arvo, joka on nykyisen solmun g-arvon ja nykyisestä solmusta naapurisolmuun siirtymisen kustannusten summa. Jos naapurisolmu ei ole prioriteettijärjestyksessä tai alkuperäinen g(n)-arvo on pienempi kuin sen nykyinen g-arvo, päivitä sen g-arvo ja aseta sen pääsolmu nykyiseksi solmuksi. Laske f(n)-arvo naapurisolmusta ja lisää se prioriteettijonoon.

Jos sykli päättyy löytämättä kohdesolmua, kaaviolla ei ole polkua alusta loppuun. A*:n tehokkuuden avain on sen heuristisen funktion h(n) käyttö, joka antaa arvion minkä tahansa solmun tavoitteen saavuttamisen jäljellä olevista kustannuksista. Yhdistämällä todelliset kustannukset g (n) heuristiseen hintaan h (n), algoritmi tutkii tehokkaasti lupaavia polkuja ja priorisoi solmut, jotka todennäköisesti johtavat lyhimpään polkuun. On tärkeää huomata, että A*-algoritmin tehokkuus riippuu suuresti heuristisen funktion valinnasta. Hyväksyttävä heuristiikka varmistaa, että algoritmi löytää aina lyhimmän polun, mutta tietoisempi ja tarkempi heuristiikka voi johtaa nopeampaan konvergenssiin ja pienempään hakutilaan.

A*-hakualgoritmin edut tekoälyssä

A*-hakualgoritmi tarjoaa useita etuja tekoäly- ja ongelmanratkaisuskenaarioissa:

    Optimaalinen ratkaisu:A* varmistaa optimaalisen (lyhyimmän) polun löytämisen aloitussolmusta kohdesolmuun painotetussa kaaviossa hyväksytyllä heuristisella funktiolla. Tämä optimaalisuus on ratkaiseva etu monissa sovelluksissa, joissa lyhimmän polun löytäminen on välttämätöntä.Täydellisyys:Jos ratkaisu on olemassa, A* löytää sen, mikäli graafilla ei ole ääretöntä hintaa. Tämä täydellisyysominaisuus varmistaa, että A* voi hyödyntää ratkaisua, jos se on olemassa.Tehokkuus:A* on tehokas, jos käytetään tehokasta ja hyväksyttävää heuristista funktiota. Heuristiikka ohjaa haun päämäärään keskittymällä lupaaviin polkuihin ja välttämällä tarpeetonta tutkimista, mikä tekee A*:sta tehokkaamman kuin tietämättömät hakualgoritmit, kuten leveyshaku tai syvyyshaku.Monipuolisuus:A* soveltuu laajasti useille ongelma-alueille, mukaan lukien reittien etsiminen, reittisuunnittelu, robotiikka, pelien kehittäminen ja paljon muuta. A*:ta voidaan käyttää optimaalisten ratkaisujen löytämiseen tehokkaasti niin kauan kuin mielekäs heuristiikka voidaan määritellä.Optimoitu haku:A* ylläpitää prioriteettijärjestystä valitakseen solmut, joilla on pieni f(n)-arvo (g(n) ja h(n)) laajentamista varten. Näin se voi tutkia lupaavia polkuja ensin, mikä vähentää hakutilaa ja johtaa nopeampaan lähentymiseen.Muistin tehokkuus:Toisin kuin jotkin muut hakualgoritmit, kuten leveysensimmäinen haku, A* tallentaa vain rajoitetun määrän solmuja prioriteettijonoon, mikä tekee siitä muistitehokkaan, erityisesti suurille kaavioille.Viritettävä heuristiikka:A*:n suorituskykyä voidaan hienosäätää valitsemalla erilaisia ​​heuristisia toimintoja. Koulutetumpi heuristiikka voi johtaa nopeampaan konvergenssiin ja vähemmän laajennettuihin solmuihin.Laajasti tutkittu:A* on vakiintunut algoritmi, jolla on vuosikymmenten tutkimus ja käytännön sovellukset. Monia optimointeja ja muunnelmia on kehitetty, mikä tekee siitä luotettavan ja hyvin ymmärrettävän vianetsintätyökalun.Nettihaku:A*:ta voidaan käyttää verkkopohjaiseen polkuhakuun, jossa algoritmi päivittää polkua jatkuvasti ympäristön muutosten tai uusien ilmaantumisen mukaan. Se mahdollistaa reaaliaikaisen päätöksenteon dynaamisissa skenaarioissa.

A*-hakualgoritmin haitat tekoälyssä

Vaikka A* (kirjain A) -hakualgoritmi on laajalti käytetty ja tehokas tekniikka tekoälyn polunhaku- ja kuvaajan läpikulkuongelmien ratkaisemiseen, sillä on haittoja ja rajoituksia. Tässä on joitain hakualgoritmin tärkeimmistä haitoista:

    Heuristinen tarkkuus:A*-algoritmin suorituskyky riippuu suuresti sen heuristisen funktion tarkkuudesta, jota käytetään arvioimaan kustannukset nykyisestä solmusta solmuun. Jos heuristiikka ei ole hyväksyttävä (ei koskaan yliarvioi todellisia kustannuksia) tai epäjohdonmukainen (täyttää kolmion epätasa-arvon), A* ei välttämättä löydä optimaalista polkua tai voi tutkia enemmän solmuja kuin on tarpeen, mikä vaikuttaa sen tehokkuuteen ja tarkkuuteen.Muistin käyttö:A* edellyttää, että kaikki vieraillut solmut säilytetään muistissa tutkittujen polkujen seuraamiseksi. Muistin käytöstä voi joskus tulla merkittävä ongelma, varsinkin kun kyseessä on runsaasti hakutilaa tai rajalliset muistiresurssit.Aika monimutkaisuus:Vaikka A* on yleensä tehokas, sen aika monimutkaisuus voi olla huolenaihe valtavissa hakuavaruuksissa tai kaavioissa. Pahimmassa tapauksessa A* voi kestää eksponentiaalisesti kauemmin löytääkseen optimaalisen polun, jos heuristiikka ei sovellu ongelmaan.Pullonkaula määränpäässä:Tietyissä skenaarioissa A*-algoritmin on tutkittava kaukana määränpäästä olevia solmuja ennen kuin se lopulta saavuttaa kohdealueen. Tämä ongelma ilmenee, kun heuristiikan on ohjattava haku varhaisessa vaiheessa tehokkaasti.Kustannussidonta:A* kohtaa vaikeuksia, kun useilla solmuilla on sama f-arvo (todellisten kustannusten ja heurististen kustannusten summa). Käytetty strategia voi vaikuttaa löydetyn polun optimaalisuuteen ja tehokkuuteen. Jos sitä ei käsitellä oikein, se voi johtaa tarpeettomien solmujen tutkimiseen ja hidastaa algoritmia.Monimutkaisuus dynaamisissa ympäristöissä:Dynaamisissa ympäristöissä, joissa reunojen tai solmujen hinta voi muuttua haun aikana, A* ei ehkä ole sopiva, koska se ei mukaudu hyvin tällaisiin muutoksiin. Uudelleenformulointi tyhjästä voi olla laskennallisesti kallista, ja D* (Dynamic A*) -algoritmit on suunniteltu ratkaisemaan tämä.Täydellisyys äärettömässä avaruudessa:A* ei välttämättä löydä ratkaisua äärettömässä tilaavaruudessa. Tällaisissa tapauksissa se voi toimia loputtomiin ja tutkia jatkuvasti kasvavaa määrää solmuja löytämättä ratkaisua. Näistä puutteista huolimatta A* on edelleen vankka ja laajalti käytetty algoritmi, koska se voi tehokkaasti löytää optimaaliset polut monissa käytännön tilanteissa, jos heuristinen funktio on hyvin suunniteltu ja hakutila hallittavissa. A*:lle on ehdotettu erilaisia ​​muunnelmia ja muunnelmia joidenkin sen rajoitusten lievittämiseksi.

A*-hakualgoritmin sovellukset tekoälyssä

Hakualgoritmi A* (kirjain A) on laajalti käytetty ja vankka polunetsintäalgoritmi tekoälyssä ja tietojenkäsittelytieteessä. Sen tehokkuus ja optimaalisuus tekevät siitä sopivan erilaisiin sovelluksiin. Tässä on joitain tyypillisiä A*-hakualgoritmin sovelluksia tekoälyssä:

    Polun löytäminen peleissä:A*:ta käytetään usein videopeleissä hahmojen liikkumiseen, vihollisen tekoälynavigointiin ja lyhimmän polun löytämiseen paikasta toiseen pelikartalta. Sen kyky löytää optimaalinen polku kustannusten ja heuristiikan perusteella tekee siitä ihanteellisen reaaliaikaisiin sovelluksiin, kuten peleihin.Robotiikka ja autonomiset ajoneuvot:A*:ta käytetään robotiikassa ja autonomisessa ajoneuvonavigaatiossa suunnittelemaan optimaalinen reitti roboteille päästäkseen määränpäähän välttäen esteitä ja ottamalla huomioon maastokustannukset. Tämä on ratkaisevan tärkeää tehokkaan ja turvallisen liikkumisen kannalta luonnonympäristöissä.Labyrintin ratkaisu:A* pystyy löytämään tehokkaasti lyhimmän polun sokkelon läpi, mikä tekee siitä arvokkaan monissa sokkeloita ratkaisevissa sovelluksissa, kuten pulmien ratkaisemisessa tai monimutkaisissa rakenteissa navigoinnissa.Reitin suunnittelu ja navigointi:GPS-järjestelmissä ja karttasovelluksissa A*:ta voidaan käyttää optimaalisen reitin löytämiseen kahden kartan pisteen välillä ottaen huomioon sellaiset tekijät kuin etäisyys, liikenneolosuhteet ja tieverkoston topologia.Palapelin ratkaiseminen:A* osaa ratkaista erilaisia ​​kaaviopulmia, kuten liukuvat pulmat, Sudokut ja 8 palapelin ongelman. Resurssien allokointi: Skenaarioissa, joissa resurssit on allokoitava optimaalisesti, A* voi auttaa löytämään tehokkaimman allokointipolun, minimoiden kustannukset ja maksimoiden tehokkuuden.Verkkoreititys:A*:ta voidaan käyttää tietokoneverkoissa tehokkaimman reitin löytämiseen datapaketteille lähteestä kohdesolmuun.Luonnollisen kielen käsittely (NLP):Joissakin NLP-tehtävissä A* voi luoda yhtenäisiä ja kontekstuaalisia vastauksia etsimällä mahdollisia sanasarjoja niiden todennäköisyyden ja merkityksen perusteella.Reitin suunnittelu robotiikassa:A*:lla voidaan suunnitella robotin polku pisteestä toiseen ottaen huomioon erilaiset rajoitteet, kuten esteiden välttäminen tai energiankulutuksen minimoiminen.Pelin tekoäly:A*:ta käytetään myös älykkäiden päätösten tekemiseen ei-pelaajahahmojen (NPC) suhteen, kuten parhaan tavan saavuttamiseksi tavoite tai liikkeiden koordinoimiseksi joukkuepohjaisessa pelissä.

Nämä ovat vain muutamia esimerkkejä siitä, kuinka A*-hakualgoritmi löytää sovelluksia tekoälyn eri alueilla. Sen joustavuus, tehokkuus ja optimointi tekevät siitä arvokkaan työkalun moniin ongelmiin.

C-ohjelma tekoälyn A*-hakualgoritmille

 #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++-ohjelma tekoälyn A*-hakualgoritmille

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

Selitys:

    Rakennesolmu:Tämä määrittää solmurakenteen, joka edustaa ruudukon solua. Se sisältää solmun x- ja y-koordinaatit, kustannukset g aloitussolmusta kyseiseen solmuun, heuristisen arvon h (arvioitu hinta kyseisestä solmusta kohdesolmuun) ja osoittimen
  1. polun aloitussolmu.
  2. Laske heuristinen:Tämä funktio laskee heuristisen käyttämällä solmun ja kohteen välistä euklidista etäisyyttä. AStarSearch: Tämä funktio suorittaa A*-hakualgoritmin. Se ottaa alku- ja määränpääkoordinaatit, ruudukon ja palauttaa parien vektorin, joka edustaa lyhimmän polun koordinaatteja alusta loppuun.Ensisijainen:Ohjelman päätoiminto ottaa käyttäjältä syöteruudukot, lähtöpisteet ja kohdekoordinaatit. Sitten se soittaa AStarSearchille löytääkseen lyhimmän polun ja tulostaa tuloksen. Rakennesolmu: Tämä määrittää solmurakenteen, joka edustaa ruudukon solua. Se sisältää solmun x- ja y-koordinaatit, kustannukset g aloitussolmusta kyseiseen solmuun, heuristisen arvon h (arvioitu hinta kyseisestä solmusta kohdesolmuun) ja osoittimen polun aloitussolmuun.Laske heuristinen:Tämä funktio laskee heuristiikan käyttämällä solmun ja kohteen välistä euklidista etäisyyttä. AStarSearch: Tämä funktio suorittaa A*-hakualgoritmin. Se ottaa alku- ja määränpääkoordinaatit, ruudukon ja palauttaa parien vektorin, joka edustaa lyhimmän polun koordinaatteja alusta loppuun.

Näytelähtö

 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-ohjelma tekoälyn A*-hakualgoritmille

 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* Hakualgoritmien monimutkaisuus tekoälyssä

A* (lausutaan 'A-tähti') -hakualgoritmi on suosittu ja laajalti käytetty graafin läpikulku- ja polkuhakualgoritmi tekoälyssä. Lyhimmän polun löytäminen kahden solmun välillä kaaviossa tai ruudukkopohjaisessa ympäristössä on yleensä yleistä. Algoritmi yhdistää Dijkstran ja ahneita paras ensin -hakuelementtejä tutkiakseen hakuavaruutta ja varmistaakseen optimaalisen toiminnan tehokkaasti. Useat tekijät määräävät A*-hakualgoritmin monimutkaisuuden. Graafin koko (solmut ja reunat): Graafin solmujen ja reunojen määrä vaikuttaa suuresti algoritmin monimutkaisuuteen. Enemmän solmuja ja reunoja merkitsee enemmän mahdollisia tutkittavia vaihtoehtoja, mikä voi pidentää algoritmin suoritusaikaa.

jotain bf:lle

Heuristinen funktio: A* käyttää heuristista funktiota (merkitty usein h(n)) arvioidakseen kustannukset nykyisestä solmusta kohdesolmuun. Tämän heuristiikan tarkkuus vaikuttaa suuresti A*-haun tehokkuuteen. Hyvä heuristiikka voi auttaa ohjaamaan haun tavoitteeseen nopeammin, kun taas huono heuristinen voi johtaa tarpeettomaan etsimiseen.

    Tietorakenteet:A* ylläpitää kahta päätietorakennetta: avointa listaa (prioriteettijono) ja suljettua listaa (tai vierailtua poolia). Näiden tietorakenteiden tehokkuus yhdessä valitun toteutuksen kanssa (esim. prioriteettijonon binäärikasat) vaikuttaa algoritmin suorituskykyyn.Haaratekijä:Kunkin solmun seuraajien keskimääräinen määrä vaikuttaa haun aikana laajennettujen solmujen määrään. Suurempi haarautumiskerroin voi johtaa enemmän etsintään, mikä lisääntyyOptimaalisuus ja täydellisyys:A* takaa sekä optimaalisuuden (lyhimmän polun löytäminen) että täydellisyyden (olemassa olevan ratkaisun löytäminen). Tämä takuu sisältää kuitenkin kompromissin laskennan monimutkaisuuden suhteen, koska algoritmin on tutkittava eri polkuja optimaalisen suorituskyvyn saavuttamiseksi. Ajan monimutkaisuuden kannalta valittu heuristinen funktio vaikuttaa A*:een pahimmassa tapauksessa. Hyväksytyllä heuristiikalla (joka ei koskaan yliarvioi tavoitteen saavuttamisen todellisia kustannuksia) A* laajentaa optimointialgoritmien vähiten solmuja. A*:n pahimman tapauksen aikamonimutkaisuus on eksponentiaalinen pahimmassa tapauksessa O(b ^ d), missä 'b' on tehokas haarautumiskerroin (seuraajien keskimääräinen määrä solmua kohti) ja 'd' on optimaalinen

Käytännössä A* toimii kuitenkin usein huomattavasti paremmin johtuen heuristisen funktion vaikutuksesta, joka auttaa ohjaamaan algoritmin lupaaville poluille. Hyvin suunnitellun heuristiikan tapauksessa tehokas haarautumiskerroin on paljon pienempi, mikä johtaa nopeampaan lähestymistapaan optimaaliseen ratkaisuun.