logo

A* Algoritmo di ricerca nell'intelligenza artificiale

Un'introduzione all'algoritmo di ricerca A* nell'intelligenza artificiale

A* (pronunciato 'A-star') è un potente algoritmo di attraversamento dei grafici e di ricerca del percorso ampiamente utilizzato nell'intelligenza artificiale e nell'informatica. Viene utilizzato principalmente per trovare il percorso più breve tra due nodi in un grafico, dato il costo stimato per passare dal nodo corrente al nodo di destinazione. Il vantaggio principale dell'algoritmo è la sua capacità di fornire un percorso ottimale esplorando il grafico in modo più informato rispetto agli algoritmi di ricerca tradizionali come l'algoritmo di Dijkstra.

L'algoritmo A* combina i vantaggi di altri due algoritmi di ricerca: l'algoritmo di Dijkstra e Greedy Best-First Search. Come l'algoritmo di Dijkstra, A* garantisce che il percorso trovato sia il più breve possibile ma lo fa in modo più efficiente indirizzando la ricerca attraverso un'euristica simile a Greedy Best-First Search. Una funzione euristica, denominata h(n), stima il costo per passare da un dato nodo n al nodo di destinazione.

L'idea principale di A* è valutare ciascun nodo in base a due parametri:

iskcon modulo completo
    g(n):il costo effettivo per passare dal nodo iniziale al nodo n. Rappresenta la somma dei costi del nodo n archi uscenti.h(n):Costo euristico (noto anche come 'costo di stima') dal nodo n al nodo di destinazione n. Questa funzione euristica specifica del problema deve essere accettabile, nel senso che non sopravvaluta mai il costo effettivo per raggiungere l'obiettivo. La funzione di valutazione del nodo n è definita come f(n) = g(n) h(n).

L'algoritmo A* seleziona i nodi da esplorare in base al valore più basso di f(n), preferendo i nodi con il costo totale stimato più basso per raggiungere l'obiettivo. L'algoritmo A* funziona:

  1. Crea un elenco aperto di nodi trovati ma non esplorati.
  2. Crea un elenco chiuso per contenere i nodi già esplorati.
  3. Aggiungi un nodo iniziale all'elenco aperto con un valore iniziale di g
  4. Ripetere i seguenti passaggi finché l'elenco aperto non sarà vuoto o non si raggiunge il nodo di destinazione:
    1. Trova il nodo con il valore f più piccolo (cioè il nodo con il minore g(n) h(n)) nell'elenco aperto.
    2. Sposta il nodo selezionato dall'elenco aperto all'elenco chiuso.
    3. Crea tutti i discendenti validi del nodo selezionato.
    4. Per ciascun successore, calcola il suo valore g come la somma del valore g del nodo corrente e del costo di spostamento dal nodo corrente al nodo successore. Aggiorna il valore g del tracker quando viene trovato un percorso migliore.
    5. Se il follower non è nell'elenco aperto, aggiungilo con il valore g calcolato e calcola il suo valore h. Se è già nell'elenco aperto, aggiorna il suo valore g se il nuovo percorso è migliore.
    6. Ripeti il ​​ciclo. L'algoritmo A* termina quando viene raggiunto il nodo di destinazione o quando l'elenco aperto si svuota, indicando nessun percorso dal nodo iniziale al nodo di destinazione. L'algoritmo di ricerca A* è ampiamente utilizzato in vari campi come robotica, videogiochi, routing di rete e problemi di progettazione perché è efficiente e può trovare percorsi ottimali nei grafici o nelle reti.

Tuttavia, la scelta di una funzione euristica adeguata e accettabile è essenziale affinché l'algoritmo funzioni correttamente e fornisca una soluzione ottimale.

Algoritmi di ricerca informata

Storia dell'algoritmo di ricerca A* nell'intelligenza artificiale

È stato sviluppato da Peter Hart, Nils Nilsson e Bertram Raphael presso lo Stanford Research Institute (ora SRI International) come estensione dell'algoritmo di Dijkstra e di altri algoritmi di ricerca dell'epoca. A* fu pubblicato per la prima volta nel 1968 e ottenne rapidamente il riconoscimento per la sua importanza ed efficacia nelle comunità dell'intelligenza artificiale e dell'informatica. Ecco una breve panoramica delle tappe più importanti nella storia dell’algoritmo di ricerca A*:

    Algoritmi di ricerca anticipati:Prima dello sviluppo di A*, esistevano vari algoritmi di ricerca sui grafici, tra cui Depth-First Search (DFS) e Broadth-First Search (BFS). Sebbene questi algoritmi aiutassero a trovare percorsi, non garantivano l’ottimalità né consideravano l’euristica per guidare la ricercaAlgoritmo di Dijkstra:Nel 1959, l'informatico olandese Edsger W. Dijkstra introdusse l'algoritmo di Dijkstra, che trovava il percorso più breve in un grafico ponderato con pesi dei bordi non negativi. L'algoritmo di Dijkstra era efficiente, ma a causa della sua natura esaustiva presentava limitazioni se utilizzato su grafici più grandi oRicerca informata:Sono stati sviluppati algoritmi di ricerca basati sulla conoscenza (noti anche come ricerca euristica) per incorporare informazioni euristiche, come i costi stimati, per guidare il processo di ricerca in modo efficiente. Greedy Best-First Search era uno di questi algoritmi, ma non garantiva l'ottimalità per trovare il percorso più breve.Sviluppo A*:Nel 1968, Peter Hart, Nils Nilsson e Bertram Raphael introdussero l'algoritmo A* come una combinazione dell'algoritmo di Dijkstra e della Greedy Best-First Search. A* ha utilizzato una funzione euristica per stimare il costo dal nodo corrente al nodo di destinazione combinandolo con il costo effettivo per raggiungere il nodo corrente. Ciò ha consentito ad A* di esplorare il grafico in modo più consapevole, evitando percorsi non necessari e garantendo una soluzione ottimale.Rettitudine e perfezione:Gli autori di A* hanno dimostrato che l'algoritmo è perfetto (trova sempre una soluzione se ne esiste una) e ottimale (trova il percorso più breve) in determinate condizioni.Adozione diffusa e progressi:A* ha rapidamente guadagnato popolarità nelle comunità AI e IT grazie alla sua efficienza e ricercatori e sviluppatori hanno esteso e applicato l'algoritmo A* a vari campi, tra cui robotica, videogiochi, ingegneria e routing di rete. Nel corso degli anni sono state proposte diverse varianti e ottimizzazioni dell'algoritmo A*, come Incremental A* e Parallel A*. Oggi, l’algoritmo di ricerca A* è ancora un algoritmo fondamentale e ampiamente utilizzato nell’intelligenza artificiale e nell’attraversamento dei grafici. Continua a svolgere un ruolo essenziale in varie applicazioni e campi di ricerca. Il suo impatto sull’intelligenza artificiale e il suo contributo ai problemi di individuazione del percorso e di ottimizzazione lo hanno reso un algoritmo fondamentale nella ricerca sui sistemi intelligenti.

Come funziona l'algoritmo di ricerca A* nell'intelligenza artificiale?

L'algoritmo di ricerca A* (pronunciato 'lettera A') è un algoritmo di attraversamento dei grafici popolare e ampiamente utilizzato nell'intelligenza artificiale e nell'informatica. Viene utilizzato per trovare il percorso più breve da un nodo iniziale a un nodo di destinazione in un grafico ponderato. A* è un algoritmo di ricerca informato che utilizza l'euristica per guidare la ricerca in modo efficiente. L'algoritmo di ricerca A* funziona come segue:

L'algoritmo inizia con una coda prioritaria per memorizzare i nodi da esplorare. Inoltre istanzia due strutture dati g(n): il costo del percorso più breve finora dal nodo di partenza al nodo n e h(n), il costo stimato (euristico) dal nodo n al nodo di destinazione. Spesso è un’euristica ragionevole, nel senso che non sovrastima mai il costo effettivo per raggiungere un obiettivo. Metti il ​​nodo iniziale nella coda con priorità e imposta il suo g(n) su 0. Se la coda con priorità non è vuota, rimuovi il nodo con la f(n) più bassa dalla coda con priorità. f(n) = g(n) h(n). Se il nodo eliminato è il nodo di destinazione, l'algoritmo termina e viene trovato il percorso. Altrimenti, espandi il nodo e crea i suoi vicini. Per ciascun nodo vicino, calcola il suo valore g(n) iniziale, che è la somma del valore g del nodo corrente e del costo per spostarsi dal nodo corrente a un nodo vicino. Se il nodo vicino non è in ordine di priorità o il valore g(n) originale è inferiore al valore g corrente, aggiorna il suo valore g e imposta il suo nodo principale sul nodo corrente. Calcola il valore f(n) dal nodo vicino e aggiungilo alla coda di priorità.

Se il ciclo termina senza trovare il nodo di destinazione, il grafo non ha alcun percorso dall'inizio alla fine. La chiave dell'efficienza di A* è l'uso di una funzione euristica h(n) che fornisce una stima del costo rimanente per raggiungere l'obiettivo di qualsiasi nodo. Combinando il costo effettivo g (n) con il costo euristico h (n), l’algoritmo esplora efficacemente percorsi promettenti, dando priorità ai nodi che probabilmente condurranno al percorso più breve. È importante notare che l'efficienza dell'algoritmo A* dipende fortemente dalla scelta della funzione euristica. Euristiche accettabili assicurano che l'algoritmo trovi sempre il percorso più breve, ma euristiche più informate e accurate possono portare a una convergenza più rapida e a uno spazio di ricerca ridotto.

Vantaggi dell'algoritmo di ricerca A* nell'intelligenza artificiale

L'algoritmo di ricerca A* offre numerosi vantaggi negli scenari di intelligenza artificiale e risoluzione dei problemi:

    Soluzione ottimale:A* garantisce di trovare il percorso ottimale (più breve) dal nodo iniziale al nodo di destinazione nel grafico ponderato, data una funzione euristica accettabile. Questa ottimalità è un vantaggio decisivo in molte applicazioni in cui è essenziale trovare il percorso più breve.Completezza:Se esiste una soluzione, A* la troverà, purché il grafo non abbia un costo infinito. Questa proprietà di completezza garantisce che A* possa trarre vantaggio da una soluzione se esiste.Efficienza:A* è efficiente se viene utilizzata una funzione euristica efficiente e accettabile. Le euristiche guidano la ricerca verso un obiettivo concentrandosi su percorsi promettenti ed evitando esplorazioni non necessarie, rendendo A* più efficiente degli algoritmi di ricerca non consapevoli come la ricerca in ampiezza o la ricerca in profondità.Versatilità:A* è ampiamente applicabile a varie aree problematiche, tra cui l'orientamento, la pianificazione dei percorsi, la robotica, lo sviluppo di giochi e altro ancora. A* può essere utilizzato per trovare soluzioni ottimali in modo efficiente purché sia ​​possibile definire un'euristica significativa.Ricerca ottimizzata:A* mantiene un ordine di priorità per selezionare i nodi con il valore f(n) minore (g(n) e h(n)) per l'espansione. Ciò gli consente di esplorare prima percorsi promettenti, il che riduce lo spazio di ricerca e porta a una convergenza più rapida.Efficienza della memoria:A differenza di altri algoritmi di ricerca, come la ricerca in ampiezza, A* memorizza solo un numero limitato di nodi nella coda di priorità, il che lo rende efficiente in termini di memoria, soprattutto per i grafici di grandi dimensioni.Euristiche sintonizzabili:Le prestazioni di A* possono essere ottimizzate selezionando diverse funzioni euristiche. Euristiche più istruite possono portare a una convergenza più rapida e a nodi meno espansi.Ampiamente studiato:A* è un algoritmo consolidato con decenni di ricerca e applicazioni pratiche. Sono state sviluppate molte ottimizzazioni e variazioni, rendendolo uno strumento di risoluzione dei problemi affidabile e ben compreso.Ricerca sul web:A* può essere utilizzato per la ricerca del percorso basata sul web, dove l'algoritmo aggiorna costantemente il percorso in base ai cambiamenti nell'ambiente o alla comparsa di nuove. Consente il processo decisionale in tempo reale in scenari dinamici.

Svantaggi dell'algoritmo di ricerca A* nell'intelligenza artificiale

Sebbene l'algoritmo di ricerca A* (lettera A) sia una tecnica potente e ampiamente utilizzata per risolvere problemi di pathfinding e attraversamento dei grafici dell'intelligenza artificiale, presenta svantaggi e limitazioni. Ecco alcuni dei principali svantaggi dell’algoritmo di ricerca:

    Precisione euristica:Le prestazioni dell'algoritmo A* dipendono fortemente dall'accuratezza della funzione euristica utilizzata per stimare il costo dal nodo corrente al nodo corrente. Se l'euristica è inaccettabile (non sovrastima mai il costo effettivo) o incoerente (soddisfa la disuguaglianza triangolare), A* potrebbe non trovare un percorso ottimale o esplorare più nodi del necessario, compromettendone l'efficienza e la precisione.Utilizzo della memoria:A* richiede che tutti i nodi visitati siano mantenuti in memoria per tenere traccia dei percorsi esplorati. L'utilizzo della memoria a volte può diventare un problema significativo, soprattutto quando si ha a che fare con un ampio spazio di ricerca o risorse di memoria limitate.Complessità temporale:Sebbene A* sia generalmente efficiente, la sua complessità temporale può rappresentare un problema per ampi spazi di ricerca o grafici. Nel peggiore dei casi, A* può impiegare un tempo esponenzialmente più lungo per trovare il percorso ottimale se l'euristica è inappropriata per il problema.Collo di bottiglia a destinazione:In scenari specifici, l'algoritmo A* deve esplorare i nodi lontani dalla destinazione prima di raggiungere finalmente la regione di destinazione. Questo problema si verifica quando l'euristica deve dirigere la ricerca verso l'obiettivo in modo efficace e tempestivo.Costo vincolante:A* incontra difficoltà quando più nodi hanno lo stesso valore f (la somma del costo effettivo e del costo euristico). La strategia utilizzata può influenzare l'ottimalità e l'efficienza del percorso scoperto. Se non gestito correttamente, può portare all’esplorazione di nodi non necessari e rallentare l’algoritmo.Complessità in ambienti dinamici:In ambienti dinamici dove il costo dei bordi o dei nodi può cambiare durante la ricerca, A* potrebbe non essere adatto perché non si adatta bene a tali cambiamenti. La riformulazione da zero può essere computazionalmente costosa e gli algoritmi D* (Dynamic A*) sono stati progettati per risolvere questo problemaPerfezione nello spazio infinito:A* potrebbe non trovare una soluzione nello spazio degli stati infinito. In questi casi, può funzionare indefinitamente, esplorando un numero sempre crescente di nodi senza trovare una soluzione. Nonostante questi limiti, A* è ancora un algoritmo robusto e ampiamente utilizzato perché può trovare efficacemente percorsi ottimali in molte situazioni pratiche se la funzione euristica è ben progettata e lo spazio di ricerca è gestibile. Sono state proposte varie variazioni e varianti di A* per alleviare alcune delle sue limitazioni.

Applicazioni dell'algoritmo di ricerca A* nell'intelligenza artificiale

L'algoritmo di ricerca A* (lettera A) è un algoritmo di pathfinding robusto e ampiamente utilizzato nell'intelligenza artificiale e nell'informatica. La sua efficienza e ottimalità lo rendono adatto a varie applicazioni. Ecco alcune applicazioni tipiche dell'algoritmo di ricerca A* nell'intelligenza artificiale:

    Ricerca del percorso nei giochi:A* viene spesso utilizzato nei videogiochi per il movimento dei personaggi, la navigazione dell'IA nemica e la ricerca del percorso più breve da un luogo all'altro sulla mappa di gioco. La sua capacità di trovare il percorso ottimale in base ai costi e all'euristica lo rende ideale per applicazioni in tempo reale come i giochi.Robotica e veicoli autonomi:A* viene utilizzato nella robotica e nella navigazione di veicoli autonomi per pianificare un percorso ottimale affinché i robot raggiungano una destinazione, evitando gli ostacoli e considerando i costi del terreno. Questo è fondamentale per un movimento efficiente e sicuro negli ambienti naturali.Risoluzione del labirinto:A* può trovare in modo efficiente il percorso più breve attraverso un labirinto, rendendolo prezioso in molte applicazioni di risoluzione dei labirinti, come la risoluzione di enigmi o l'esplorazione di strutture complesse.Pianificazione del percorso e navigazione:Nei sistemi GPS e nelle applicazioni di mappatura, A* può essere utilizzato per trovare il percorso ottimale tra due punti su una mappa, considerando fattori quali la distanza, le condizioni del traffico e la topologia della rete stradale.Risoluzione di enigmi:A* può risolvere vari puzzle con diagrammi, come puzzle scorrevoli, Sudoku e il problema degli 8 puzzle. Allocazione delle risorse: negli scenari in cui le risorse devono essere allocate in modo ottimale, A* può aiutare a trovare il percorso di allocazione più efficiente, minimizzando i costi e massimizzando l'efficienza.Instradamento di rete:A* può essere utilizzato nelle reti di computer per trovare il percorso più efficiente per i pacchetti di dati da un nodo di origine a un nodo di destinazione.Elaborazione del linguaggio naturale (PNL):In alcuni compiti di PNL, A* può generare risposte coerenti e contestuali cercando possibili sequenze di parole in base alla loro probabilità e rilevanza.Pianificazione del percorso nella robotica:A* può essere utilizzato per pianificare il percorso di un robot da un punto a un altro, considerando vari vincoli, come evitare ostacoli o ridurre al minimo il consumo di energia.IA del gioco:A* viene utilizzato anche per prendere decisioni intelligenti per i personaggi non giocanti (NPC), come determinare il modo migliore per raggiungere un obiettivo o coordinare i movimenti in un gioco di squadra.

Questi sono solo alcuni esempi di come l’algoritmo di ricerca A* trova applicazioni in vari ambiti dell’intelligenza artificiale. La sua flessibilità, efficienza e ottimizzazione lo rendono uno strumento prezioso per molti problemi.

neve contro ghiaccio

Programma C per un algoritmo di ricerca A* nell'intelligenza artificiale

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

Programma C++ per un algoritmo di ricerca A* nell'intelligenza artificiale

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

Spiegazione:

    Nodo di struttura:Ciò definisce una struttura del nodo che rappresenta una cella della griglia. Contiene le coordinate xey del nodo, il costo g dal nodo di partenza a quel nodo, il valore euristico h (costo stimato da quel nodo al nodo di destinazione) e un puntatore al
  1. nodo iniziale del percorso.
  2. Calcola euristica:Questa funzione calcola un'euristica utilizzando la distanza euclidea tra un nodo e il target AStarSearch: questa funzione esegue l'algoritmo di ricerca A*. Prende le coordinate di partenza e di destinazione, una griglia, e restituisce un vettore di coppie che rappresentano le coordinate del percorso più breve dall'inizio alla fine.Primario:La funzione principale del programma prende le griglie di input, l'origine e le coordinate di destinazione dall'utente. Quindi chiama AStarSearch per trovare il percorso più breve e stampa il risultato. Nodo struttura: definisce una struttura nodo che rappresenta una cella della griglia. Contiene le coordinate xey del nodo, il costo g dal nodo iniziale a quel nodo, il valore euristico h (costo stimato da quel nodo al nodo di destinazione) e un puntatore al nodo iniziale del percorso.Calcola euristica:Questa funzione calcola l'euristica utilizzando la distanza euclidea tra un nodo e il target AStarSearch: questa funzione esegue l'algoritmo di ricerca A*. Prende le coordinate di partenza e di destinazione, una griglia, e restituisce un vettore di coppie che rappresentano le coordinate del percorso più breve dall'inizio alla fine.

Uscita del campione

 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 

Programma Java per un algoritmo di ricerca A* nell'intelligenza artificiale

 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* Complessità degli algoritmi di ricerca nell'intelligenza artificiale

L'algoritmo di ricerca A* (pronunciato 'A-star') è un algoritmo di ricerca di percorsi e attraversamento di grafici popolare e ampiamente utilizzato nell'intelligenza artificiale. Trovare il percorso più breve tra due nodi in un ambiente grafico o basato su griglia è solitamente comune. L'algoritmo combina gli elementi di ricerca best-first di Dijkstra e Greedy per esplorare lo spazio di ricerca garantendo al tempo stesso l'ottimalità in modo efficiente. Diversi fattori determinano la complessità dell'algoritmo di ricerca A*. Dimensione del grafico (nodi e spigoli): il numero di nodi e spigoli di un grafico influisce notevolmente sulla complessità dell'algoritmo. Più nodi e bordi significano più opzioni possibili da esplorare, il che può aumentare il tempo di esecuzione dell'algoritmo.

Funzione euristica: A* utilizza una funzione euristica (spesso indicata con h(n)) per stimare il costo dal nodo corrente al nodo di destinazione. La precisione di questa euristica influisce notevolmente sull'efficienza della ricerca A*. Una buona euristica può aiutare a guidare la ricerca verso un obiettivo più rapidamente, mentre una cattiva euristica può portare a ricerche non necessarie.

    Strutture dati:A* mantiene due strutture di dati principali: una lista aperta (coda prioritaria) e una lista chiusa (o pool visitato). L'efficienza di queste strutture dati, insieme all'implementazione scelta (ad esempio, gli heap binari della coda con priorità), influisce sulle prestazioni dell'algoritmo.Fattore di filiale:Il numero medio di follower per ciascun nodo influisce sul numero di nodi espansi durante la ricerca. Un fattore di ramificazione più elevato può portare a una maggiore esplorazione, che aumentaOttimalità e completezza:A* garantisce sia l'ottimalità (trovare il percorso più breve) che la completezza (trovare una soluzione che esiste). Tuttavia, questa garanzia comporta un compromesso in termini di complessità computazionale, poiché l’algoritmo deve esplorare percorsi diversi per ottenere prestazioni ottimali. Per quanto riguarda la complessità temporale, la funzione euristica scelta influenza A* nel caso peggiore. Con un'euristica accettata (che non sovrastima mai il costo reale per raggiungere l'obiettivo), A* espande il minor numero di nodi tra gli algoritmi di ottimizzazione. La complessità temporale nel caso peggiore di A * è esponenziale nel caso peggiore O(b ^ d), dove 'b' è il fattore di ramificazione effettivo (numero medio di follower per nodo) e 'd' è il fattore ottimale

In pratica, tuttavia, A* spesso ha prestazioni significativamente migliori grazie all’influenza di una funzione euristica che aiuta a guidare l’algoritmo verso percorsi promettenti. Nel caso di un’euristica ben progettata, il fattore di ramificazione effettivo è molto più piccolo, il che porta ad un approccio più rapido alla soluzione ottimale.