logo

A* Algorisme de cerca en intel·ligència artificial

Una introducció a l'algoritme de cerca A* en IA

A* (pronunciat 'A-star') és un potent algorisme de traçat i de recerca de gràfics àmpliament utilitzat en intel·ligència artificial i informàtica. S'utilitza principalment per trobar el camí més curt entre dos nodes en un gràfic, donat el cost estimat d'anar des del node actual al node de destinació. El principal avantatge de l'algorisme és la seva capacitat per proporcionar un camí òptim explorant el gràfic d'una manera més informada en comparació amb els algorismes de cerca tradicionals com l'algoritme de Dijkstra.

L'algoritme A* combina els avantatges d'altres dos algorismes de cerca: l'algoritme de Dijkstra i Greedy Best-First Search. Igual que l'algorisme de Dijkstra, A* assegura que el camí trobat sigui el més curt possible, però ho fa de manera més eficient dirigint la seva cerca a través d'una heurística similar a Greedy Best-First Search. Una funció heurística, denotada h(n), estima el cost d'arribar des de qualsevol node n al node de destinació.

La idea principal d'A* és avaluar cada node en funció de dos paràmetres:

un exemple d'un sistema operatiu de codi obert és
    g(n):el cost real per arribar des del node inicial al node n. Representa la suma dels costos del node n vores de sortida.h(n):Cost heurístic (també conegut com a 'cost d'estimació') des del node n fins al node de destinació n. Aquesta funció heurística específica del problema ha de ser acceptable, és a dir, mai sobreestima el cost real d'aconseguir l'objectiu. La funció d'avaluació del node n es defineix com f(n) = g(n) h(n).

L'algorisme A* selecciona els nodes que s'han d'explorar en funció del valor més baix de f(n), preferint els nodes amb el cost total estimat més baix per assolir l'objectiu. L'algorisme A* funciona:

  1. Creeu una llista oberta de nodes trobats però no explorats.
  2. Creeu una llista tancada per contenir nodes ja explorats.
  3. Afegiu un node inicial a la llista oberta amb un valor inicial de g
  4. Repetiu els passos següents fins que la llista oberta estigui buida o arribeu al node objectiu:
    1. Trobeu el node amb el valor f més petit (és a dir, el node amb g(n) h(n) menor) a la llista oberta.
    2. Mou el node seleccionat de la llista oberta a la llista tancada.
    3. Creeu tots els descendents vàlids del node seleccionat.
    4. Per a cada successor, calcula el seu valor g com la suma del valor g del node actual i el cost de passar del node actual al node successor. Actualitzeu el valor g del rastrejador quan es trobi un camí millor.
    5. Si el seguidor no està a la llista oberta, afegiu-lo amb el valor g calculat i calculeu-ne el valor h. Si ja és a la llista oberta, actualitzeu el seu valor g si el camí nou és millor.
    6. Repetiu el cicle. L'algoritme A* acaba quan s'arriba al node objectiu o quan la llista oberta es buida, indicant que no hi ha cap camí des del node inicial fins al node objectiu. L'algoritme de cerca A* s'utilitza àmpliament en diversos camps com ara robòtica, videojocs, enrutament de xarxes i problemes de disseny perquè és eficient i pot trobar camins òptims en gràfics o xarxes.

Tanmateix, escollir una funció heurística adequada i acceptable és essencial perquè l'algorisme funcioni correctament i proporcioni una solució òptima.

Algorismes de cerca informats

Història de l'algoritme de cerca A* en intel·ligència artificial

Va ser desenvolupat per Peter Hart, Nils Nilsson i Bertram Raphael a l'Institut de Recerca de Stanford (ara SRI International) com una extensió de l'algorisme de Dijkstra i altres algorismes de cerca de l'època. A* es va publicar per primera vegada el 1968 i ràpidament va guanyar reconeixement per la seva importància i eficàcia en les comunitats d'intel·ligència artificial i informàtica. Aquí teniu una breu visió general de les fites més crítiques de la història de l'algorisme de cerca A*:

    Els primers algorismes de cerca:Abans del desenvolupament d'A*, existien diversos algorismes de cerca de gràfics, com ara Depth-First Search (DFS) i Breadth-First Search (BFS). Tot i que aquests algorismes van ajudar a trobar camins, no van garantir l'optimització ni tenien en compte les heurístiques per guiar la cerca.Algorisme de Dijkstra:L'any 1959, l'informàtic holandès Edsger W. Dijkstra va introduir l'algoritme de Dijkstra, que va trobar el camí més curt en un gràfic ponderat amb pesos de vora no negatius. L'algorisme de Dijkstra era eficient, però a causa de la seva naturalesa exhaustiva, tenia limitacions quan s'utilitzava en gràfics més grans oCerca informada:S'han desenvolupat algorismes de cerca basats en el coneixement (també coneguts com a cerca heurística) per incorporar informació heurística, com ara costos estimats, per guiar el procés de cerca de manera eficient. Greedy Best-First Search era un d'aquests algorismes, però no garantia l'optimització per trobar el camí més curt.A* desenvolupament:El 1968, Peter Hart, Nils Nilsson i Bertram Raphael van introduir l'algoritme A* com una combinació de l'algoritme de Dijkstra i Greedy Best-First Search. A* va utilitzar una funció heurística per estimar el cost des del node actual fins al node de destinació combinant-lo amb el cost real d'arribar al node actual. Això va permetre a A* explorar el gràfic de manera més conscient, evitant camins innecessaris i garantint una solució òptima.Justícia i perfecció:Els autors d'A* van demostrar que l'algorisme és perfecte (sempre troba una solució si n'hi ha) i òptim (troba el camí més curt) sota determinades condicions.Adopció i progrés generalitzats:A* va guanyar ràpidament popularitat a les comunitats d'IA i TI a causa de la seva eficiència i els investigadors i desenvolupadors han ampliat i aplicat l'algoritme A* a diversos camps, com ara la robòtica, els videojocs, l'enginyeria i l'encaminament de la xarxa. Al llarg dels anys s'han proposat diverses variacions i optimitzacions de l'algorisme A*, com ara A* incremental i A* paral·lel. Avui dia, l'algoritme de cerca A* segueix sent un algorisme fonamental i molt utilitzat en intel·ligència artificial i recorregut de gràfics. Continua jugant un paper essencial en diverses aplicacions i camps de recerca. El seu impacte en la intel·ligència artificial i la seva contribució als problemes de recerca i optimització l'han convertit en un algorisme fonamental en la investigació de sistemes intel·ligents.

Com funciona l'algoritme de cerca A* en intel·ligència artificial?

L'algoritme de cerca A* (pronunciat 'lletra A') és un algorisme de recorregut de gràfics popular i molt utilitzat en intel·ligència artificial i informàtica. S'utilitza per trobar el camí més curt des d'un node inicial fins a un node de destinació en un gràfic ponderat. A* és un algorisme de cerca informat que utilitza heurístiques per guiar la cerca de manera eficient. L'algorisme de cerca A* funciona de la següent manera:

L'algorisme comença amb una cua de prioritats per emmagatzemar els nodes a explorar. També crea dues estructures de dades g(n): el cost del camí més curt des del node inicial fins al node n i h(n), el cost estimat (heurístic) des del node n fins al node de destinació. Sovint és una heurística raonable, és a dir, mai sobreestima el cost real d'aconseguir un objectiu. Col·loqueu el node inicial a la cua de prioritats i establiu el seu g(n) a 0. Si la cua de prioritats no està buida, traieu el node amb la f(n) més baixa de la cua de prioritats. f(n) = g(n) h(n). Si el node suprimit és el node de destinació, l'algorisme finalitza i es troba el camí. En cas contrari, expandiu el node i creeu els seus veïns. Per a cada node veí, calculeu el seu valor inicial g(n), que és la suma del valor g del node actual i el cost de passar del node actual a un node veí. Si el node veí no està en ordre de prioritat o el valor g(n) original és inferior al seu valor g actual, actualitzeu el seu valor g i configureu el node pare al node actual. Calculeu el valor f(n) del node veí i afegiu-lo a la cua de prioritats.

Si el cicle acaba sense trobar el node de destinació, el gràfic no té camí des del principi fins al final. La clau de l'eficiència d'A* és l'ús d'una funció heurística h(n) que proporciona una estimació del cost restant per assolir l'objectiu de qualsevol node. En combinar el cost real g (n) amb el cost heurístic h (n), l'algoritme explora eficaçment camins prometedors, prioritzant els nodes que poden conduir al camí més curt. És important tenir en compte que l'eficiència de l'algorisme A* depèn molt de l'elecció de la funció heurística. Les heurístiques acceptables garanteixen que l'algoritme sempre trobi el camí més curt, però les heurístiques més informades i precises poden conduir a una convergència més ràpida i a un espai de cerca reduït.

Avantatges de l'algoritme de cerca A* en intel·ligència artificial

L'algoritme de cerca A* ofereix diversos avantatges en escenaris d'intel·ligència artificial i resolució de problemes:

    Solució òptima:A* garanteix trobar el camí òptim (més curt) des del node inicial fins al node de destinació al gràfic ponderat donada una funció heurística acceptable. Aquesta optimitat és un avantatge decisiu en moltes aplicacions on trobar el camí més curt és essencial.Exhaustivitat:Si existeix una solució, A* la trobarà, sempre que el gràfic no tingui un cost infinit. Aquesta propietat d'exhaustivitat garanteix que A* pugui aprofitar una solució si existeix.Eficiència:A* és eficient si s'utilitza una funció heurística eficient i acceptable. Les heurístiques orienten la cerca cap a un objectiu centrant-se en camins prometedors i evitant l'exploració innecessària, fent A* més eficient que els algorismes de cerca no conscients, com ara la cerca en profunditat o la cerca en profunditat.Versatilitat:A* és àmpliament aplicable a diverses àrees problemàtiques, com ara l'orientació, la planificació de rutes, la robòtica, el desenvolupament de jocs i molt més. A* es pot utilitzar per trobar solucions òptimes de manera eficient sempre que es pugui definir una heurística significativa.Cerca optimitzada:A* manté un ordre de prioritat per seleccionar els nodes amb el valor menor f(n) (g(n) i h(n)) per a l'expansió. Això li permet explorar primer camins prometedors, cosa que redueix l'espai de cerca i condueix a una convergència més ràpida.Eficiència de la memòria:A diferència d'altres algorismes de cerca, com ara la cerca en amplitud, A* només emmagatzema un nombre limitat de nodes a la cua de prioritats, cosa que fa que la memòria sigui eficient, especialment per a gràfics grans.Heurístics ajustables:El rendiment d'A* es pot ajustar seleccionant diferents funcions heurístiques. Les heurístiques més educades poden conduir a una convergència més ràpida i a nodes menys expandits.Ampliament investigat:A* és un algorisme ben establert amb dècades d'investigació i aplicacions pràctiques. S'han desenvolupat moltes optimitzacions i variacions, cosa que la converteix en una eina de resolució de problemes fiable i ben entesa.Cerca web:A* es pot utilitzar per a la cerca de rutes basada en web, on l'algoritme actualitza constantment la ruta segons els canvis en l'entorn o l'aparició de nous. Permet la presa de decisions en temps real en escenaris dinàmics.

Inconvenients de l'algoritme de cerca A* en intel·ligència artificial

Tot i que l'algoritme de cerca A* (lletra A) és una tècnica molt utilitzada i potent per resoldre problemes d'identificació de camins d'IA i travessa de gràfics, té desavantatges i limitacions. Aquests són alguns dels principals desavantatges de l'algorisme de cerca:

    Exactitud heurística:El rendiment de l'algorisme A* depèn en gran mesura de la precisió de la funció heurística utilitzada per estimar el cost des del node actual fins al Si l'heurística és inacceptable (mai sobreestima el cost real) o inconsistent (satisfa la desigualtat del triangle), A* pot no trobar un camí òptim o explorar més nodes del necessari, afectant la seva eficiència i precisió.Ús de memòria:A* requereix que tots els nodes visitats es mantinguin a la memòria per fer un seguiment dels camins explorats. L'ús de la memòria de vegades pot esdevenir un problema important, especialment quan es tracta d'un espai de cerca ampli o recursos de memòria limitats.Complexitat temporal:Tot i que A* és generalment eficient, la seva complexitat temporal pot ser una preocupació per a grans espais de cerca o gràfics. En el pitjor dels casos, A* pot trigar exponencialment més a trobar el camí òptim si l'heurística és inadequada per al problema.Coll d'ampolla a la destinació:En escenaris específics, l'algoritme A* ha d'explorar nodes lluny de la destinació abans d'arribar finalment a la regió de destinació. Aquest problema es produeix quan l'heurística necessita dirigir la cerca a l'objectiu de manera eficaç.Vinculació de costos:A* s'enfronta a dificultats quan diversos nodes tenen el mateix valor f (la suma del cost real i el cost heurístic). L'estratègia utilitzada pot afectar l'optimitat i l'eficiència del camí descobert. Si no es gestiona correctament, pot provocar que s'explorin nodes innecessaris i alentir l'algorisme.Complexitat en entorns dinàmics:En entorns dinàmics on el cost de les vores o dels nodes pot canviar durant la cerca, pot ser que A* no sigui adequat perquè no s'adapta bé a aquests canvis. La reformulació des de zero pot ser costosa computacionalment, i els algorismes D* (A* dinàmic) es van dissenyar per resoldre-ho.La perfecció en l'espai infinit:És possible que A* no trobi una solució a l'espai d'estats infinit. En aquests casos, es pot executar indefinidament, explorant un nombre cada cop més gran de nodes sense trobar una solució. Malgrat aquestes mancances, A* segueix sent un algorisme robust i àmpliament utilitzat perquè pot trobar de manera efectiva camins òptims en moltes situacions pràctiques si la funció heurística està ben dissenyada i l'espai de cerca és manejable. S'han proposat diverses variacions i variants d'A* per pal·liar algunes de les seves limitacions.

Aplicacions de l'Algoritme de cerca A* en Intel·ligència Artificial

L'algoritme de cerca A* (lletra A) és un algorisme de recerca de camins robust i àmpliament utilitzat en intel·ligència artificial i informàtica. La seva eficiència i òptimitat el fan apte per a diverses aplicacions. A continuació es mostren algunes aplicacions típiques de l'algoritme de cerca A* en intel·ligència artificial:

    Pathfinding als jocs:A* s'utilitza sovint als videojocs per al moviment de personatges, la navegació amb IA de l'enemic i per trobar el camí més curt d'una ubicació a una altra al mapa del joc. La seva capacitat per trobar el camí òptim en funció del cost i de l'heurística el fa ideal per a aplicacions en temps real com ara jocs.Robòtica i vehicles autònoms:A* s'utilitza en robòtica i navegació de vehicles autònoms per planificar una ruta òptima perquè els robots arribin a una destinació, evitant obstacles i tenint en compte els costos del terreny. Això és crucial per a un moviment eficient i segur en entorns naturals.Resolució de laberints:A* pot trobar de manera eficient el camí més curt a través d'un laberint, cosa que el fa valuós en moltes aplicacions de resolució de laberints, com ara resoldre trencaclosques o navegar per estructures complexes.Planificació de rutes i navegació:En sistemes GPS i aplicacions de mapes, A* es pot utilitzar per trobar la ruta òptima entre dos punts d'un mapa, tenint en compte factors com ara la distància, les condicions del trànsit i la topologia de la xarxa de carreteres.Resolució de trencaclosques:A* pot resoldre diversos trencaclosques de diagrames, com ara trencaclosques lliscants, Sudoku i el problema de 8 trencaclosques. Assignació de recursos: en escenaris en què els recursos s'han d'assignar de manera òptima, A* pot ajudar a trobar la ruta d'assignació més eficient, minimitzant els costos i maximitzant l'eficiència.Enrutament de xarxa:A* es pot utilitzar en xarxes informàtiques per trobar la ruta més eficient per als paquets de dades des d'una font fins a un node de destinació.Processament del llenguatge natural (PNL):En algunes tasques de PNL, A* pot generar respostes coherents i contextuals cercant possibles seqüències de paraules en funció de la seva probabilitat i rellevància.Planificació de rutes en robòtica:A* es pot utilitzar per planificar el recorregut d'un robot d'un punt a un altre, tenint en compte diverses limitacions, com ara evitar obstacles o minimitzar el consum d'energia.IA del joc:A* també s'utilitza per prendre decisions intel·ligents per als personatges no jugadors (NPC), com ara determinar la millor manera d'assolir un objectiu o coordinar moviments en un joc basat en equip.

Aquests són només alguns exemples de com l'algoritme de cerca A* troba aplicacions en diverses àrees de la intel·ligència artificial. La seva flexibilitat, eficiència i optimització el converteixen en una eina valuosa per a molts problemes.

Programa C per a algorisme de cerca A* en intel·ligència artificial

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

Programa C++ per a l'algoritme de cerca A* en intel·ligència artificial

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

Explicació:

    Node d'estructura:Això defineix una estructura de nodes que representa una cel·la de quadrícula. Conté les coordenades x i y del node, el cost g des del node inicial fins a aquest node, el valor heurístic h (cost estimat des d'aquest node fins al node de destinació) i un punter a la
  1. node inicial del camí.
  2. Calcula l'heurística:Aquesta funció calcula una heurística utilitzant la distància euclidiana entre un node i l'objectiu AStarSearch: aquesta funció executa l'algorisme de cerca A*. Pren les coordenades d'inici i de destinació, una quadrícula, i retorna un vector de parells que representen les coordenades del camí més curt des del principi fins al final.Primària:La funció principal del programa pren les quadrícules d'entrada, l'origen i les coordenades de destinació de l'usuari. A continuació, crida a AStarSearch per trobar el camí més curt i imprimeix el resultat. Node d'estructura: defineix una estructura de node que representa una cel·la de quadrícula. Conté les coordenades x i y del node, el cost g des del node inicial fins a aquest node, el valor heurístic h (cost estimat des d'aquest node fins al node de destinació) i un punter al node inicial del camí.Calcula l'heurística:Aquesta funció calcula les heurístiques utilitzant la distància euclidiana entre un node i l'objectiu AStarSearch: aquesta funció executa l'algorisme de cerca A*. Pren les coordenades d'inici i de destinació, una quadrícula, i retorna un vector de parells que representen les coordenades del camí més curt des del principi fins al final.

Sortida de mostra

java afegint a una matriu
 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 

Programa Java per a l'algoritme de cerca A* en intel·ligència artificial

 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* Complexitat de l'algoritme de cerca en intel·ligència artificial

L'algoritme de cerca A* (pronunciat 'A-star') és un algorisme de cerca de recorregut i recorregut de gràfics popular i àmpliament utilitzat en intel·ligència artificial. Trobar el camí més curt entre dos nodes en un entorn basat en gràfics o graelles sol ser habitual. L'algoritme combina els elements de cerca de Dijkstra i el millor primer primer per explorar l'espai de cerca alhora que garanteix l'optimització de manera eficient. Diversos factors determinen la complexitat de l'algoritme de cerca A*. Mida del gràfic (nodes i arestes): el nombre de nodes i arestes d'un gràfic afecta molt la complexitat de l'algorisme. Més nodes i vores signifiquen més opcions possibles per explorar, que poden augmentar el temps d'execució de l'algorisme.

Funció heurística: A* utilitza una funció heurística (sovint denotada h(n)) per estimar el cost des del node actual fins al node de destinació. La precisió d'aquesta heurística afecta molt l'eficiència de la cerca A*. Una bona heurística pot ajudar a guiar la cerca cap a un objectiu més ràpidament, mentre que una mala heurística pot provocar cerques innecessàries.

    Estructures de dades:A* manté dues estructures de dades principals: una llista oberta (cua de prioritats) i una llista tancada (o grup visitat). L'eficiència d'aquestes estructures de dades, juntament amb la implementació escollida (per exemple, els munts binaris de la cua de prioritat), afecta el rendiment de l'algorisme.Factor de branca:El nombre mitjà de seguidors per a cada node afecta el nombre de nodes expandits durant la cerca. Un factor de ramificació més alt pot conduir a més exploració, que augmentaOptimitat i exhaustivitat:A* garanteix tant l'optimitat (trobar el camí més curt) com la integritat (trobar una solució que existeix). Tanmateix, aquesta garantia ve amb un compromís en termes de complexitat computacional, ja que l'algoritme ha d'explorar diferents camins per obtenir un rendiment òptim. Pel que fa a la complexitat temporal, la funció heurística escollida afecta a A* en el pitjor dels casos. Amb una heurística acceptada (que mai sobreestima el cost real d'assolir l'objectiu), A* expandeix el menor nombre de nodes entre els algorismes d'optimització. La complexitat temporal del pitjor dels casos d'A * és exponencial en el pitjor dels casos O(b ^ d), on 'b' és el factor de ramificació efectiu (nombre mitjà de seguidors per node) i 'd' és l'òptim.

A la pràctica, però, A* sovint funciona molt millor a causa de la influència d'una funció heurística que ajuda a guiar l'algorisme cap a camins prometedors. En el cas d'una heurística ben dissenyada, el factor de ramificació eficaç és molt més petit, la qual cosa condueix a una aproximació més ràpida a la solució òptima.