logo

Een* zoekalgoritme in kunstmatige intelligentie

Een inleiding tot het A*-zoekalgoritme in AI

A* (uitgesproken als 'A-star') is een krachtig algoritme voor het doorlopen van grafieken en het vinden van paden dat veel wordt gebruikt in kunstmatige intelligentie en informatica. Het wordt voornamelijk gebruikt om het kortste pad tussen twee knooppunten in een grafiek te vinden, gegeven de geschatte kosten om van het huidige knooppunt naar het bestemmingsknooppunt te komen. Het belangrijkste voordeel van het algoritme is het vermogen om een ​​optimaal pad te bieden door de grafiek op een beter geïnformeerde manier te verkennen in vergelijking met traditionele zoekalgoritmen zoals het algoritme van Dijkstra.

Algoritme A* combineert de voordelen van twee andere zoekalgoritmen: het algoritme van Dijkstra en Greedy Best-First Search. Net als het algoritme van Dijkstra zorgt A* ervoor dat het gevonden pad zo kort mogelijk is, maar doet dit efficiënter door zijn zoekopdracht te richten via een heuristiek die vergelijkbaar is met Greedy Best-First Search. Een heuristische functie, h(n) genoemd, schat de kosten om van een bepaald knooppunt n naar het bestemmingsknooppunt te komen.

Het belangrijkste idee van A* is om elk knooppunt te evalueren op basis van twee parameters:

volgorde op willekeurige sql
    g(n):de werkelijke kosten om van het initiële knooppunt naar knooppunt n te komen. Het vertegenwoordigt de som van de kosten van knooppunt n uitgaande randen.h(n):Heuristische kosten (ook bekend als 'schattingskosten') van knooppunt n naar bestemmingsknooppunt n. Deze probleemspecifieke heuristische functie moet acceptabel zijn, wat betekent dat de werkelijke kosten voor het bereiken van het doel nooit worden overschat. De evaluatiefunctie van knooppunt n wordt gedefinieerd als f(n) = g(n) h(n).

Algoritme A* selecteert de knooppunten die moeten worden onderzocht op basis van de laagste waarde van f(n), waarbij de voorkeur wordt gegeven aan de knooppunten met de laagste geschatte totale kosten om het doel te bereiken. Het A*-algoritme werkt:

  1. Maak een open lijst met gevonden maar niet onderzochte knooppunten.
  2. Maak een gesloten lijst met reeds onderzochte knooppunten.
  3. Voeg een startknooppunt toe aan de open lijst met een initiële waarde van g
  4. Herhaal de volgende stappen totdat de open lijst leeg is of u het doelknooppunt bereikt:
    1. Zoek het knooppunt met de kleinste f-waarde (dat wil zeggen het knooppunt met de kleine g(n) h(n)) in de open lijst.
    2. Verplaats het geselecteerde knooppunt van de open lijst naar de gesloten lijst.
    3. Creëer alle geldige afstammelingen van het geselecteerde knooppunt.
    4. Bereken voor elke opvolger de g-waarde als de som van de g-waarde van het huidige knooppunt en de kosten om van het huidige knooppunt naar het opvolgerknooppunt te verhuizen. Update de g-waarde van de tracker wanneer een beter pad wordt gevonden.
    5. Als de volger niet in de open lijst staat, voeg deze dan toe met de berekende g-waarde en bereken de h-waarde ervan. Als het al in de open lijst staat, update dan de g-waarde als het nieuwe pad beter is.
    6. Herhaal de cyclus. Algoritme A* eindigt wanneer het doelknooppunt wordt bereikt of wanneer de open lijst leeg raakt, wat aangeeft dat er geen paden zijn vanaf het startknooppunt naar het doelknooppunt. Het A*-zoekalgoritme wordt veel gebruikt op verschillende gebieden, zoals robotica, videogames, netwerkroutering en ontwerpproblemen, omdat het efficiënt is en optimale paden in grafieken of netwerken kan vinden.

Het kiezen van een geschikte en acceptabele heuristische functie is echter essentieel, zodat het algoritme correct presteert en een optimale oplossing biedt.

Geïnformeerde zoekalgoritmen

Geschiedenis van het A*-zoekalgoritme in kunstmatige intelligentie

Het werd ontwikkeld door Peter Hart, Nils Nilsson en Bertram Raphael van het Stanford Research Institute (nu SRI International) als een uitbreiding van Dijkstra's algoritme en andere zoekalgoritmen van die tijd. A* werd voor het eerst gepubliceerd in 1968 en kreeg al snel erkenning vanwege het belang en de effectiviteit ervan in de kunstmatige intelligentie- en computerwetenschapsgemeenschappen. Hier is een kort overzicht van de meest kritische mijlpalen in de geschiedenis van het zoekalgoritme A*:

    Vroege zoekalgoritmen:Vóór de ontwikkeling van A* bestonden er verschillende grafiekzoekalgoritmen, waaronder Depth-First Search (DFS) en Breadth-First Search (BFS). Hoewel deze algoritmen hielpen bij het vinden van paden, konden ze de optimaliteit niet garanderen en hielden ze geen rekening met heuristieken om de zoektocht te begeleidenDijkstra's algoritme:In 1959 introduceerde de Nederlandse computerwetenschapper Edsger W. Dijkstra het algoritme van Dijkstra, dat het kortste pad vond in een gewogen grafiek met niet-negatieve randgewichten. Het algoritme van Dijkstra was efficiënt, maar vanwege zijn uitputtende karakter had het beperkingen bij gebruik in grotere grafieken ofGeïnformeerd zoeken:Op kennis gebaseerde zoekalgoritmen (ook wel heuristisch zoeken genoemd) zijn ontwikkeld om heuristische informatie, zoals geschatte kosten, op te nemen om het zoekproces efficiënt te begeleiden. Greedy Best-First Search was zo'n algoritme, maar het garandeerde geen optimaliteit voor het vinden van het kortste pad.Een* ontwikkeling:In 1968 introduceerden Peter Hart, Nils Nilsson en Bertram Raphael het A*-algoritme als een combinatie van het algoritme van Dijkstra en Greedy Best-First Search. A* gebruikte een heuristische functie om de kosten van het huidige knooppunt naar het bestemmingsknooppunt te schatten door deze te combineren met de werkelijke kosten om het huidige knooppunt te bereiken. Hierdoor kon A* de grafiek bewuster verkennen, onnodige paden vermijden en een optimale oplossing garanderen.Gerechtigheid en perfectie:De auteurs van A* lieten zien dat het algoritme onder bepaalde omstandigheden perfect is (vindt altijd een oplossing als die bestaat) en optimaal (vindt het kortste pad).Wijdverbreide adoptie en vooruitgang:A* werd snel populair in de AI- en IT-gemeenschappen vanwege de efficiëntie ervan. Onderzoekers en ontwikkelaars hebben het A*-algoritme uitgebreid en toegepast op verschillende gebieden, waaronder robotica, videogames, engineering en netwerkroutering. Er zijn in de loop der jaren verschillende variaties en optimalisaties van het A*-algoritme voorgesteld, zoals Incrementeel A* en Parallel A*. Tegenwoordig is het A*-zoekalgoritme nog steeds een fundamenteel en veelgebruikt algoritme bij kunstmatige intelligentie en het doorkruisen van grafieken. Het blijft een essentiële rol spelen in verschillende toepassingen en onderzoeksgebieden. De impact ervan op kunstmatige intelligentie en de bijdrage ervan aan padvindings- en optimalisatieproblemen hebben het tot een hoeksteenalgoritme gemaakt in het onderzoek naar intelligente systemen.

Hoe werkt het A*-zoekalgoritme in kunstmatige intelligentie?

Het A*-zoekalgoritme (uitgesproken als 'letter A') is een populair en veelgebruikt algoritme voor het doorlopen van grafieken in kunstmatige intelligentie en informatica. Het wordt gebruikt om het kortste pad van een startknooppunt naar een bestemmingsknooppunt in een gewogen grafiek te vinden. A* is een geïnformeerd zoekalgoritme dat heuristieken gebruikt om de zoekopdracht efficiënt te begeleiden. Het zoekalgoritme A* werkt als volgt:

Het algoritme begint met een prioriteitswachtrij waarin de te verkennen knooppunten worden opgeslagen. Het instantiëert ook twee datastructuren g(n): de kosten van het kortste pad tot nu toe van het startknooppunt naar knooppunt n en h(n), de geschatte kosten (heuristisch) van knooppunt n naar het bestemmingsknooppunt. Het is vaak een redelijke heuristiek, wat betekent dat de werkelijke kosten voor het bereiken van een doel nooit worden overschat. Plaats het initiële knooppunt in de prioriteitswachtrij en stel zijn g(n) in op 0. Als de prioriteitswachtrij niet leeg is, verwijdert u het knooppunt met de laagste f(n) uit de prioriteitswachtrij. f(n) = g(n) h(n). Als het verwijderde knooppunt het bestemmingsknooppunt is, eindigt het algoritme en wordt het pad gevonden. Breid anders het knooppunt uit en creëer de buren. Bereken voor elk buurknooppunt de initiële g(n)-waarde, die de som is van de g-waarde van het huidige knooppunt en de kosten om van het huidige knooppunt naar een naburig knooppunt te verhuizen. Als het naburige knooppunt niet in de prioriteitsvolgorde staat of als de oorspronkelijke g(n)-waarde kleiner is dan de huidige g-waarde, update dan de g-waarde ervan en stel het bovenliggende knooppunt in op het huidige knooppunt. Bereken de f(n)-waarde van het aangrenzende knooppunt en voeg deze toe aan de prioriteitswachtrij.

Als de cyclus eindigt zonder het bestemmingsknooppunt te vinden, heeft de grafiek geen pad van begin tot eind. De sleutel tot de efficiëntie van A* is het gebruik van een heuristische functie h(n) die een schatting geeft van de resterende kosten om het doel van een willekeurig knooppunt te bereiken. Door de werkelijke kosten g (n) te combineren met de heuristische kosten h (n), onderzoekt het algoritme effectief veelbelovende paden, waarbij prioriteit wordt gegeven aan knooppunten die waarschijnlijk naar het kortste pad zullen leiden. Het is belangrijk op te merken dat de efficiëntie van het A*-algoritme sterk afhankelijk is van de keuze van de heuristische functie. Acceptabele heuristieken zorgen ervoor dat het algoritme altijd het kortste pad vindt, maar beter geïnformeerde en nauwkeurigere heuristieken kunnen leiden tot snellere convergentie en verminderde zoekruimte.

Voordelen van een* zoekalgoritme in kunstmatige intelligentie

Het A*-zoekalgoritme biedt verschillende voordelen in kunstmatige intelligentie en probleemoplossende scenario's:

    Optimale oplossing:A* zorgt ervoor dat het optimale (kortste) pad van het startknooppunt naar het bestemmingsknooppunt in de gewogen grafiek wordt gevonden, gegeven een acceptabele heuristische functie. Deze optimaliteit is een doorslaggevend voordeel in veel toepassingen waarbij het vinden van het kortste pad essentieel is.Volledigheid:Als er een oplossing bestaat, zal A* die vinden, op voorwaarde dat de grafiek geen oneindige kosten heeft. Deze volledigheidseigenschap zorgt ervoor dat A* voordeel kan halen uit een oplossing als die bestaat.Efficiëntie:A* is efficiënt als er een efficiënte en acceptabele heuristische functie wordt gebruikt. Heuristieken begeleiden de zoektocht naar een doel door zich te concentreren op veelbelovende paden en onnodige verkenning te vermijden, waardoor A* efficiënter wordt dan niet-bewuste zoekalgoritmen zoals zoeken in de breedte of eerst in de diepte.Veelzijdigheid:A* is breed toepasbaar op verschillende probleemgebieden, waaronder bewegwijzering, routeplanning, robotica, game-ontwikkeling en meer. A* kan worden gebruikt om op efficiënte wijze optimale oplossingen te vinden, zolang er maar een betekenisvolle heuristiek kan worden gedefinieerd.Geoptimaliseerd zoeken:A* handhaaft een prioriteitsvolgorde voor het selecteren van de knooppunten met de kleine f(n)-waarde (g(n) en h(n)) voor uitbreiding. Hierdoor kan het eerst veelbelovende paden verkennen, wat de zoekruimte verkleint en tot snellere convergentie leidt.Geheugenefficiëntie:In tegenstelling tot sommige andere zoekalgoritmen, zoals breedte-eerst zoeken, slaat A* slechts een beperkt aantal knooppunten op in de prioriteitswachtrij, waardoor het geheugen efficiënt is, vooral voor grote grafieken.Afstembare heuristieken:De prestaties van A* kunnen worden verfijnd door verschillende heuristische functies te selecteren. Beter opgeleide heuristieken kunnen leiden tot snellere convergentie en minder uitgebreide knooppunten.Uitgebreid onderzocht:A* is een beproefd algoritme met tientallen jaren onderzoek en praktische toepassingen. Er zijn veel optimalisaties en variaties ontwikkeld, waardoor het een betrouwbare en goed begrepen tool voor probleemoplossing is.Zoeken op internet:A* kan worden gebruikt voor het zoeken naar paden op internet, waarbij het algoritme het pad voortdurend bijwerkt op basis van veranderingen in de omgeving of het verschijnen van nieuwe. Het maakt realtime besluitvorming in dynamische scenario's mogelijk.

Nadelen van een A*-zoekalgoritme in kunstmatige intelligentie

Hoewel het A*-zoekalgoritme (letter A) een veelgebruikte en krachtige techniek is voor het oplossen van problemen met AI-padvinding en het doorlopen van grafieken, heeft het nadelen en beperkingen. Hier zijn enkele van de belangrijkste nadelen van het zoekalgoritme:

    Heuristische nauwkeurigheid:De prestaties van het A*-algoritme zijn sterk afhankelijk van de nauwkeurigheid van de heuristische functie die wordt gebruikt om de kosten van het huidige knooppunt naar het knooppunt te schatten. Als de heuristiek onaanvaardbaar is (nooit de werkelijke kosten overschat) of inconsistent (voldoet aan de driehoeksongelijkheid), A* kan mogelijk geen optimaal pad vinden of meer knooppunten verkennen dan nodig is, wat de efficiëntie en nauwkeurigheid ervan beïnvloedt.Geheugengebruik:A* vereist dat alle bezochte knooppunten in het geheugen worden bewaard om de onderzochte paden bij te houden. Geheugengebruik kan soms een groot probleem worden, vooral als u te maken heeft met voldoende zoekruimte of beperkte geheugenbronnen.Tijdcomplexiteit:Hoewel A* over het algemeen efficiënt is, kan de tijdscomplexiteit ervan een probleem zijn voor grote zoekruimten of grafieken. In het ergste geval kan het voor A* exponentieel langer duren om het optimale pad te vinden als de heuristiek niet geschikt is voor het probleem.Knelpunt op de bestemming:In specifieke scenario's moet het A*-algoritme knooppunten ver van de bestemming verkennen voordat het uiteindelijk de bestemmingsregio bereikt. Dit probleem doet zich voor wanneer de heuristiek de zoektocht vroegtijdig effectief op het doel moet richten.Kosten bindend:A* heeft problemen wanneer meerdere knooppunten dezelfde f-waarde hebben (de som van de werkelijke kosten en de heuristische kosten). De gebruikte strategie kan de optimaliteit en efficiëntie van het ontdekte pad beïnvloeden. Als dit niet correct wordt afgehandeld, kan dit ertoe leiden dat onnodige knooppunten worden onderzocht en het algoritme wordt vertraagd.Complexiteit in dynamische omgevingen:In dynamische omgevingen waar de kosten van randen of knooppunten tijdens het zoeken kunnen veranderen, is A* mogelijk niet geschikt omdat het zich niet goed aan dergelijke veranderingen aanpast. Een geheel nieuwe formulering kan rekenkundig duur zijn, en D* (Dynamic A*)-algoritmen zijn ontworpen om dit op te lossenPerfectie in oneindige ruimte:A* vindt mogelijk geen oplossing in de oneindige toestandsruimte. In dergelijke gevallen kan het voor onbepaalde tijd draaien, waarbij een steeds groter aantal knooppunten wordt onderzocht zonder een oplossing te vinden. Ondanks deze tekortkomingen is A* nog steeds een robuust en veelgebruikt algoritme, omdat het in veel praktische situaties effectief optimale paden kan vinden als de heuristische functie goed is ontworpen en de zoekruimte beheersbaar is. Er zijn verschillende variaties en varianten van A* voorgesteld om enkele van de beperkingen ervan te verlichten.

Toepassingen van het A*-zoekalgoritme in kunstmatige intelligentie

Het zoekalgoritme A* (letter A) is een veelgebruikt en robuust padzoekalgoritme in de kunstmatige intelligentie en informatica. Door zijn efficiëntie en optimaliteit is hij geschikt voor diverse toepassingen. Hier zijn enkele typische toepassingen van het A*-zoekalgoritme in kunstmatige intelligentie:

    Padvinden in games:A* wordt vaak gebruikt in videogames voor het verplaatsen van personages, vijandelijke AI-navigatie en het vinden van het kortste pad van de ene locatie naar de andere op de gamekaart. Het vermogen om het optimale pad te vinden op basis van kosten en heuristieken maakt het ideaal voor realtime toepassingen zoals games.Robotica en autonome voertuigen:A* wordt gebruikt in robotica en autonome voertuignavigatie om een ​​optimale route voor robots te plannen om een ​​bestemming te bereiken, waarbij obstakels worden vermeden en rekening wordt gehouden met de terreinkosten. Dit is cruciaal voor efficiënt en veilig verkeer in een natuurlijke omgeving.Doolhof oplossen:A* kan efficiënt het kortste pad door een doolhof vinden, waardoor dit waardevol is bij veel toepassingen voor het oplossen van doolhoven, zoals het oplossen van puzzels of het navigeren door complexe structuren.Routeplanning en navigatie:In GPS-systemen en kaarttoepassingen kan A* worden gebruikt om de optimale route tussen twee punten op een kaart te vinden, rekening houdend met factoren zoals afstand, verkeersomstandigheden en wegennetwerktopologie.Puzzels oplossen:A* kan verschillende diagrampuzzels oplossen, zoals schuifpuzzels, Sudoku en het 8-puzzelprobleem. Toewijzing van middelen: In scenario's waarin middelen optimaal moeten worden toegewezen, kan A* helpen bij het vinden van het meest efficiënte toewijzingspad, waardoor de kosten worden geminimaliseerd en de efficiëntie wordt gemaximaliseerd.Netwerkroutering:A* kan in computernetwerken worden gebruikt om de meest efficiënte route voor datapakketten van een bron- naar een bestemmingsknooppunt te vinden.Natuurlijke taalverwerking (NLP):Bij sommige NLP-taken kan A* coherente en contextuele reacties genereren door te zoeken naar mogelijke woordreeksen op basis van hun waarschijnlijkheid en relevantie.Padplanningin robotica:A* kan worden gebruikt om het pad van een robot van het ene punt naar het andere te plannen, rekening houdend met verschillende beperkingen, zoals het vermijden van obstakels of het minimaliseren van het energieverbruik.Spel-AI:A* wordt ook gebruikt om intelligente beslissingen te nemen voor niet-spelerpersonages (NPC's), zoals het bepalen van de beste manier om een ​​doel te bereiken of bewegingen te coördineren in een teamgebaseerd spel.

Dit zijn slechts enkele voorbeelden van hoe het A*-zoekalgoritme toepassingen vindt op verschillende gebieden van kunstmatige intelligentie. Dankzij de flexibiliteit, efficiëntie en optimalisatie is het een waardevol hulpmiddel voor veel problemen.

C-programma voor A* zoekalgoritme in kunstmatige intelligentie

 #include #include #define ROWS 5 #define COLS 5 // Define a structure for a grid cell typedef struct { int row, col; } Cell; // Define a structure for a node in the A* algorithm typedef struct { Cell position; int g, h, f; struct Node* parent; } Node; // Function to calculate the Manhattan distance between two cells int heuristic(Cell current, Cell goal) { return abs(current.row - goal.row) + abs(current.col - goal.col); } // Function to check if a cell is valid (within the grid and not an obstacle) int isValid(int row, int col, int grid[ROWS][COLS]) { return (row &gt;= 0) &amp;&amp; (row = 0) &amp;&amp; (col <cols) && (grid[row][col]="=" 0); } function to check if a cell is the goal int isgoal(cell cell, goal) { return (cell.row="=" goal.row) (cell.col="=" goal.col); perform a* search algorithm void astarsearch(int grid[rows][cols], start, todo: implement here main() grid[rows][cols]="{" {0, 1, 0, 0}, 0} }; start="{0," 0}; - cols 1}; astarsearch (grid, goal); 0; < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Data Structures:</td> A cell structure represents a grid cell with a row and a column. The node structure stores information about a cell during an A* lookup, including its location, cost (g, h, f), and a reference to its parent. </tr><tr><td>Heuristic function (heuristic):</td> This function calculates the Manhattan distance (also known as a &apos;cab ride&apos;) between two cells. It is used as a heuristic to estimate the cost from the current cell to the target cell. The Manhattan distance is the sum of the absolute differences between rows and columns. </tr><tr><td>Validation function (isValid):</td> This function checks if the given cell is valid, i.e., whether it is within the grid boundaries and is not an obstacle (indicated by a grid value of 1). </tr><tr><td>Goal check function (isGoal):</td> This function checks if the given cell is a target cell, i.e., does it match the coordinates of the target cell. </tr><tr><td>Search function* (AStarSearch):</td> This is the main function where the A* search algorithm should be applied. It takes a grid, a source cell, and a target cell as inputs. This activity aims to find the shortest path from the beginning to the end, avoiding the obstacles on the grid. The main function initializes a grid representing the environment, a start, and a target cell. It then calls the AStarSearch function with those inputs. </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> (0, 0) (1, 0) (2, 0) (3, 0) (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) </pre> <h3>C++ program for A* Search Algorithm in Artificial Intelligence</h3> <pre> #include #include #include using namespace std; struct Node { int x, y; // Coordinates of the node int g; // Cost from the start node to this node int h; // Heuristic value (estimated cost from this node to the goal node) Node* parent; // Parent node in the path Node (int x, int y): x(x), y(y), g(0), h(0), parent(nullptr) {} // Calculate the total cost (f = g + h) int f () const { return g + h; } }; // Heuristic function (Euclidean distance) int calculateHeuristic (int x, int y, int goals, int goal) { return static cast (sqrt (pow (goals - x, 2) + pow (goal - y, 2))); } // A* search algorithm vector<pair> AStarSearch (int startX, int startY, int goals, int goal, vector<vector>&amp; grid) { vector<pair> path; int rows = grid. size (); int cols = grid [0].size (); // Create the open and closed lists Priority queue <node*, vector, function> open List([](Node* lhs, Node* rhs) { return lhs-&gt;f() &gt; rhs-&gt;f(); }); vector<vector> closed List (rows, vector (cols, false)); // Push the start node to the open list openList.push(start Node); // Main A* search loop while (! Open-list. Empty ()) { // Get the node with the lowest f value from the open list Node* current = open-list. Top (); openest. pop (); // Check if the current node is the goal node if (current-&gt;x == goals &amp;&amp; current-&gt;y == goal) { // Reconstruct the path while (current! = nullptr) { path. push_back(make_pair(current-&gt;x, current-&gt;y)); current = current-&gt;parent; } Reverse (path. Begin(), path.end ()); break; } // Mark the current node as visited (in the closed list) Closed-list [current-&gt;x] [current-&gt;y] = true; // Generate successors (adjacent nodes) int dx [] = {1, 0, -1, 0}; int dy [] = {0, 1, 0, -1}; for (int i = 0; i x + dx [i]; int new Y = current-&gt;y + dy [i]; } break; } successor-&gt;parent = current; open List.push(successor); } // Cleanup memory for (Node* node: open List) { delete node; } return path; } int main () { int rows, cols; cout &lt;&gt; rows; cout &lt;&gt; cols; vector<vector> grid (rows, vector(cols)); cout &lt;&lt; &apos;Enter the grid (0 for empty, 1 for obstacle):&apos; &lt;&lt; endl; for (int i = 0; i &lt; rows; i++) { for (int j = 0; j&gt; grid[i][j]; } } int startX, startY, goalX, goalY; cout &lt;&gt; startX &gt;&gt; start; cout &lt;&gt; goals &gt;&gt; goals; vector<pair> path = AStarSearch (startX, startY, goal, goal, grid); if (! path. Empty ()) { cout &lt;&lt; &apos;Shortest path from (&apos; &lt;&lt; startX &lt;&lt; &apos;,&apos; &lt;&lt; start &lt;&lt; &apos;) to (&apos; &lt;&lt; goal &lt;&lt; &apos;,&apos; &lt;&lt; goal &lt;&lt; &apos;):&apos; &lt;&lt; endl; for (const auto&amp; point: path) { cout &lt;&lt; &apos;(&apos; &lt;&lt; point. first &lt;&lt; &apos;,&apos; &lt;&lt; point. second &lt;&lt; &apos;) &apos;; } cout &lt;&lt; endl; } else { cout &lt;&lt; &apos;No path found!&apos; &lt;&lt; endl; } return 0; } </pair></vector></vector></node*,></pair></vector></pair></pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Struct Node:</td> This defines a nodestructure that represents a grid cell. It contains the x and y coordinates of the node, the cost g from the starting node to that node, the heuristic value h (estimated cost from that node to the destination node), and a pointer to the <li>starting node of the path.</li> </tr><tr><td>Calculate heuristic:</td> This function calculates a heuristic using the Euclidean distance between a node and the target AStarSearch: This function runs the A* search algorithm. It takes the start and destination coordinates, a grid, and returns a vector of pairs representing the coordinates of the shortest path from start to finish. </tr><tr><td>Primary:</td> The program&apos;s main function takes input grids, origin, and target coordinates from the user. It then calls AStarSearch to find the shortest path and prints the result. Struct Node: This defines a node structure that represents a grid cell. It contains the x and y coordinates of the node, the cost g from the starting node to that node, the heuristic value h (estimated cost from that node to the destination node), and a pointer to the starting node of the path. </tr><tr><td>Calculate heuristic:</td> This function calculates heuristics using the Euclidean distance between a node and the target AStarSearch: This function runs the A* search algorithm. It takes the start and destination coordinates, a grid, and returns a vector of pairs representing the coordinates of the shortest path from start to finish. </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Enter the number of rows: 5 Enter the number of columns: 5 Enter the grid (0 for empty, 1 for obstacle): 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 Enter the start coordinates (x y): 0 0 Enter the goal coordinates (x y): 4 4 </pre> <h3>Java program for A* Search Algorithm in Artificial Intelligence</h3> <pre> import java. util.*; class Node { int x, y; // Coordinates of the node int g; // Cost from the start node to the current node int h; // Heuristic value (estimated cost from the current node to goal node) int f; // Total cost f = g + h Node parent; // Parent node in the path public Node (int x, int y) { this. g = x; this. f = y; this. Parent = null; } } public class AStarSearch { // Heuristic function (Manhattan distance) private static int heuristic (Node current, Node goal) { return Math. Abs (current.x - goal.x) + Math. Abs(current.y - goal.y); } // A* search algorithm public static List aStarSearch(int [][] grid, Node start, Node goal) { int rows = grid. Length; int cols = grid [0].length; // Add the start node to the open set opened.add(start); while (! openSet.isEmpty()) { // Get the node with the lowest f value from the open set Node current = openSet.poll(); // If the current node is the goal node, reconstruct the path and return it if (current == goal) { List path = new ArrayList(); while (current != null) { path.add(0, current); current = current.parent; } return path; } // Move the current node from the open set to the closed set closedSet.add(current); // Generate neighbors of the current node int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; for (int i = 0; i = 0 &amp;&amp; nx = 0 &amp;&amp; ny = neighbor.g) { // Skip this neighbor as it is already in the closed set with a lower or equal g value continue; } if (!openSet.contains(neighbor) || tentativeG <neighbor.g) { update the neighbor's values neighbor.g="tentativeG;" neighbor.h="heuristic(neighbor," goal); neighbor.f="neighbor.g" + neighbor.h; neighbor.parent="current;" if (!openset.contains(neighbor)) add neighbor to open set not already present openset.add(neighbor); } is empty and goal reached, there no path return null; public static void main(string[] args) int[][] grid="{" {0, 0, 0}, 1, 0} }; node start="new" node(0, 0); node(4, 4); list start, (path !="null)" system.out.println('path found:'); for (node : path) system.out.println('(' node.x ', ' node.y ')'); else system.out.println('no found.'); < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Node Class:</td> We start by defining a nodeclass representing each grid cell. Each node contains coordinates (x, y), an initial node cost (g), a heuristic value (h), a total cost (f = g h), and a reference to the parent node of the path. </tr><tr><td>Heuristicfunction:</td> The heuristic function calculates the Manhattan distance between a node and a destination The Manhattan distance is a heuristic used to estimate the cost from the current node to the destination node. </tr><tr><td>Search algorithm* function:</td> A Star Search is the primary implementation of the search algorithm A*. It takes a 2D grid, a start node, and a destination node as inputs and returns a list of nodes representing the path from the start to the destination node. </tr><tr><td>Priority Queue and Closed Set:</td> The algorithm uses a priority queue (open Set) to track thenodes to be explored. The queue is ordered by total cost f, so the node with the lowest f value is examined The algorithm also uses a set (closed set) to track the explored nodes. </tr><tr><td>The main loop of the algorithm:</td> The main loop of the A* algorithm repeats until there are no more nodes to explore in the open Set. In each iteration, the node f with the lowest total cost is removed from the opener, and its neighbors are created. </tr><tr><td>Creating neighbors:</td> The algorithm creates four neighbors (up, down, left, right) for each node and verifies that each neighbor is valid (within the network boundaries and not as an obstacle). If the neighbor is valid, it calculates the initial value g from the source node to that neighbor and the heuristic value h from that neighbor to the destination The total cost is then calculated as the sum of f, g, and h. </tr><tr><td>Node evaluation:</td> The algorithm checks whether the neighbor is already in the closed set and, if so, whether the initial cost g is greater than or equal to the existing cost of the neighbor If true, the neighbor is omitted. Otherwise, the neighbor values are updated and added to the open Set if it is not already there. </tr><tr><td>Pathreconstruction:</td> When the destination node is reached, the algorithm reconstructs the path from the start node to the destination node following the main links from the destination node back to the start node. The path is returned as a list of nodes </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Path found: (0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (4, 2) (4, 3) (4, 4) </pre> <h2>A* Search Algorithm Complexity in Artificial Intelligence</h2> <p>The A* (pronounced &apos;A-star&apos;) search algorithm is a popular and widely used graph traversal and path search algorithm in artificial intelligence. Finding the shortest path between two nodes in a graph or grid-based environment is usually common. The algorithm combines Dijkstra&apos;s and greedy best-first search elements to explore the search space while ensuring optimality efficiently. Several factors determine the complexity of the A* search algorithm. Graph size (nodes and edges): A graph&apos;s number of nodes and edges greatly affects the algorithm&apos;s complexity. More nodes and edges mean more possible options to explore, which can increase the execution time of the algorithm.</p> <p>Heuristic function: A* uses a heuristic function (often denoted h(n)) to estimate the cost from the current node to the destination node. The precision of this heuristic greatly affects the efficiency of the A* search. A good heuristic can help guide the search to a goal more quickly, while a bad heuristic can lead to unnecessary searching.</p> <ol class="points"> <tr><td>Data Structures:</td> A* maintains two maindata structures: an open list (priority queue) and a closed list (or visited pool). The efficiency of these data structures, along with the chosen implementation (e.g., priority queue binary heaps), affects the algorithm&apos;s performance. </tr><tr><td>Branch factor:</td> The average number of followers for each node affects the number of nodes expanded during the search. A higher branching factor can lead to more exploration, which increases </tr><tr><td>Optimality and completeness:</td> A* guarantees both optimality (finding the shortest path) and completeness (finding a solution that exists). However, this guarantee comes with a trade-off in terms of computational complexity, as the algorithm must explore different paths for optimal performance. Regarding time complexity, the chosen heuristic function affects A* in the worst case. With an accepted heuristic (which never overestimates the true cost of reaching the goal), A* expands the fewest nodes among the optimization algorithms. The worst-case time complexity of A * is exponential in the worst-case O(b ^ d), where &apos;b&apos; is the effective branching factor (average number of followers per node) and &apos;d&apos; is the optimal </tr></ol> <p>In practice, however, A* often performs significantly better due to the influence of a heuristic function that helps guide the algorithm to promising paths. In the case of a well-designed heuristic, the effective branching factor is much smaller, which leads to a faster approach to the optimal solution.</p> <hr></neighbor.g)></pre></cols)>

C++-programma voor A*-zoekalgoritme in kunstmatige intelligentie

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

Uitleg:

preg_match
    Structuurknooppunt:Dit definieert een knooppuntstructuur die een rastercel vertegenwoordigt. Het bevat de x- en y-coördinaten van het knooppunt, de kosten g van het startknooppunt naar dat knooppunt, de heuristische waarde h (geschatte kosten van dat knooppunt naar het bestemmingsknooppunt) en een verwijzing naar de
  1. startknooppunt van het pad.
  2. Bereken heuristiek:Deze functie berekent een heuristiek met behulp van de Euclidische afstand tussen een knooppunt en het doel AStarSearch: Deze functie voert het A*-zoekalgoritme uit. Het neemt de start- en bestemmingscoördinaten, een raster, en retourneert een vector van paren die de coördinaten van het kortste pad van begin tot eind vertegenwoordigen.Primair:De hoofdfunctie van het programma neemt invoerrasters, oorsprong en doelcoördinaten van de gebruiker over. Vervolgens roept het AStarSearch aan om het kortste pad te vinden en drukt het resultaat af. Structuurknooppunt: Dit definieert een knooppuntstructuur die een rastercel vertegenwoordigt. Het bevat de x- en y-coördinaten van het knooppunt, de kosten g van het startknooppunt naar dat knooppunt, de heuristische waarde h (geschatte kosten van dat knooppunt naar het bestemmingsknooppunt) en een verwijzing naar het startknooppunt van het pad.Bereken heuristiek:Deze functie berekent heuristieken met behulp van de Euclidische afstand tussen een knooppunt en het doel AStarSearch: Deze functie voert het A*-zoekalgoritme uit. Het neemt de start- en bestemmingscoördinaten, een raster, en retourneert een vector van paren die de coördinaten van het kortste pad van begin tot eind vertegenwoordigen.

Voorbeelduitvoer

 Enter the number of rows: 5 Enter the number of columns: 5 Enter the grid (0 for empty, 1 for obstacle): 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 Enter the start coordinates (x y): 0 0 Enter the goal coordinates (x y): 4 4 

Java-programma voor A* Search Algorithm in Artificial Intelligence

 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* Zoekalgoritmecomplexiteit in kunstmatige intelligentie

Het A*-zoekalgoritme (uitgesproken als 'A-star') is een populair en veelgebruikt algoritme voor het doorkruisen van grafieken en het zoeken naar paden in de kunstmatige intelligentie. Het vinden van het kortste pad tussen twee knooppunten in een grafiek- of rastergebaseerde omgeving is meestal gebruikelijk. Het algoritme combineert Dijkstra's en hebzuchtige 'best-first'-zoekelementen om de zoekruimte te verkennen en tegelijkertijd optimale optimaliteit te garanderen. Verschillende factoren bepalen de complexiteit van het A*-zoekalgoritme. Grafiekgrootte (knooppunten en randen): Het aantal knooppunten en randen van een grafiek heeft grote invloed op de complexiteit van het algoritme. Meer knooppunten en randen betekenen meer mogelijke opties om te verkennen, wat de uitvoeringstijd van het algoritme kan verlengen.

Heuristische functie: A* gebruikt een heuristische functie (vaak h(n) genoemd) om de kosten van het huidige knooppunt naar het bestemmingsknooppunt te schatten. De nauwkeurigheid van deze heuristiek heeft grote invloed op de efficiëntie van de A*-zoekopdracht. Een goede heuristiek kan ertoe bijdragen dat de zoektocht sneller naar een doel wordt geleid, terwijl een slechte heuristiek tot onnodig zoeken kan leiden.

    Data structuren:A* onderhoudt twee hoofddatastructuren: een open lijst (prioriteitwachtrij) en een gesloten lijst (of bezochte pool). De efficiëntie van deze datastructuren, samen met de gekozen implementatie (bijvoorbeeld binaire heaps met prioriteitswachtrij), beïnvloedt de prestaties van het algoritme.Branchfactor:Het gemiddelde aantal volgers voor elk knooppunt is van invloed op het aantal knooppunten dat tijdens de zoekopdracht wordt uitgebreid. Een hogere vertakkingsfactor kan leiden tot meer exploratie, wat toeneemtOptimaliteit en volledigheid:A* garandeert zowel optimaliteit (het vinden van de kortste weg) als volledigheid (het vinden van een bestaande oplossing). Deze garantie gaat echter gepaard met een afweging in termen van rekencomplexiteit, omdat het algoritme verschillende paden moet verkennen voor optimale prestaties. Wat de tijdscomplexiteit betreft, heeft de gekozen heuristische functie in het ergste geval invloed op A*. Met een geaccepteerde heuristiek (die nooit de werkelijke kosten voor het bereiken van het doel overschat), breidt A* de minste knooppunten onder de optimalisatiealgoritmen uit. De tijdscomplexiteit van A * in het slechtste geval is exponentieel in het slechtste geval O(b ^ d), waarbij 'b' de effectieve vertakkingsfactor is (gemiddeld aantal volgers per knooppunt) en 'd' de optimale

In de praktijk presteert A* echter vaak aanzienlijk beter dankzij de invloed van een heuristische functie die het algoritme naar veelbelovende paden helpt leiden. Bij een goed ontworpen heuristiek is de effectieve vertakkingsfactor veel kleiner, wat leidt tot een snellere benadering van de optimale oplossing.