logo

A* Algoritmo de Pesquisa em Inteligência Artificial

Uma introdução ao algoritmo de pesquisa A* em IA

A* (pronuncia-se 'A-star') é um poderoso algoritmo de travessia de gráfico e localização de caminhos amplamente utilizado em inteligência artificial e ciência da computação. É usado principalmente para encontrar o caminho mais curto entre dois nós em um grafo, dado o custo estimado para ir do nó atual ao nó de destino. A principal vantagem do algoritmo é sua capacidade de fornecer um caminho ideal, explorando o gráfico de uma forma mais informada em comparação com algoritmos de busca tradicionais, como o algoritmo de Dijkstra.

O Algoritmo A* combina as vantagens de dois outros algoritmos de busca: o algoritmo de Dijkstra e o Greedy Best-First Search. Assim como o algoritmo de Dijkstra, A* garante que o caminho encontrado seja o mais curto possível, mas o faz de forma mais eficiente, direcionando sua busca por meio de uma heurística semelhante à Greedy Best-First Search. Uma função heurística, denotada por h(n), estima o custo de ir de qualquer nó n até o nó de destino.

A ideia principal de A* é avaliar cada nó com base em dois parâmetros:

pandas e numpy
    g(n):o custo real para ir do nó inicial ao nó n. Representa a soma dos custos do nó n arestas de saída.h(n):Custo heurístico (também conhecido como 'custo de estimativa') do nó n ao nó de destino n. Esta função heurística específica do problema deve ser aceitável, o que significa que nunca superestima o custo real para atingir a meta. A função de avaliação do nó n é definida como f(n) = g(n) h(n).

O algoritmo A* seleciona os nós a serem explorados com base no menor valor de f(n), preferindo os nós com menor custo total estimado para atingir a meta. O algoritmo A* funciona:

  1. Crie uma lista aberta de nós encontrados, mas não explorados.
  2. Crie uma lista fechada para conter nós já explorados.
  3. Adicione um nó inicial à lista aberta com um valor inicial de g
  4. Repita as etapas a seguir até que a lista aberta esteja vazia ou você alcance o nó de destino:
    1. Encontre o nó com o menor valor f (ou seja, o nó com o g(n) h(n) menor) na lista aberta.
    2. Mova o nó selecionado da lista aberta para a lista fechada.
    3. Crie todos os descendentes válidos do nó selecionado.
    4. Para cada sucessor, calcule seu valor g como a soma do valor g do nó atual e o custo de mudança do nó atual para o nó sucessor. Atualize o valor g do rastreador quando um caminho melhor for encontrado.
    5. Se o seguidor não estiver na lista aberta, adicione-o ao valor g calculado e calcule seu valor h. Se já estiver na lista aberta, atualize seu valor g se o novo caminho for melhor.
    6. Repita o ciclo. O algoritmo A* termina quando o nó de destino é alcançado ou quando a lista aberta se esvazia, indicando nenhum caminho do nó inicial ao nó de destino. O algoritmo de busca A* é amplamente utilizado em vários campos, como robótica, videogames, roteamento de rede e problemas de projeto, porque é eficiente e pode encontrar caminhos ideais em grafos ou redes.

Entretanto, escolher uma função heurística adequada e aceitável é essencial para que o algoritmo funcione corretamente e forneça uma solução ótima.

Algoritmos de pesquisa informados

História do Algoritmo de Pesquisa A* em Inteligência Artificial

Foi desenvolvido por Peter Hart, Nils Nilsson e Bertram Raphael no Stanford Research Institute (agora SRI International) como uma extensão do algoritmo de Dijkstra e outros algoritmos de busca da época. A* foi publicado pela primeira vez em 1968 e rapidamente ganhou reconhecimento pela sua importância e eficácia nas comunidades de inteligência artificial e ciência da computação. Aqui está uma breve visão geral dos marcos mais críticos na história do algoritmo de pesquisa A*:

    Algoritmos de pesquisa inicial:Antes do desenvolvimento de A*, existiam vários algoritmos de busca em grafos, incluindo Busca em Profundidade (DFS) e Busca em Largura (BFS). Embora esses algoritmos ajudassem a encontrar caminhos, eles não garantiam a otimização nem consideravam heurísticas para orientar a busca.Algoritmo de Dijkstra:Em 1959, o cientista da computação holandês Edsger W. Dijkstra introduziu o algoritmo de Dijkstra, que encontrou o caminho mais curto em um gráfico ponderado com pesos de aresta não negativos. O algoritmo de Dijkstra foi eficiente, mas devido à sua natureza exaustiva, apresentou limitações quando utilizado em grafos maiores ouPesquisa informada:Algoritmos de busca baseados em conhecimento (também conhecidos como busca heurística) foram desenvolvidos para incorporar informações heurísticas, como custos estimados, para orientar o processo de busca de forma eficiente. Greedy Best-First Search era um desses algoritmos, mas não garantia a otimização para encontrar o caminho mais curto.Desenvolvimento A*:Em 1968, Peter Hart, Nils Nilsson e Bertram Raphael introduziram o algoritmo A* como uma combinação do algoritmo de Dijkstra e da Greedy Best-First Search. A* usou uma função heurística para estimar o custo do nó atual até o nó de destino, combinando-o com o custo real para chegar ao nó atual. Isso permitiu que A* explorasse o grafo de forma mais consciente, evitando caminhos desnecessários e garantindo uma solução ótima.Justiça e Perfeição:Os autores de A* mostraram que o algoritmo é perfeito (sempre encontra uma solução, se existir) e ótimo (encontra o caminho mais curto) sob certas condições.Adoção e progresso generalizados:A* rapidamente ganhou popularidade nas comunidades de IA e TI devido à sua eficiência. Pesquisadores e desenvolvedores estenderam e aplicaram o algoritmo A* a vários campos, incluindo robótica, videogames, engenharia e roteamento de rede. Diversas variações e otimizações do algoritmo A* foram propostas ao longo dos anos, como Incremental A* e Parallel A*. Hoje, o algoritmo de busca A* ainda é um algoritmo fundamental e amplamente utilizado em inteligência artificial e travessia de grafos. Continua a desempenhar um papel essencial em diversas aplicações e campos de pesquisa. Seu impacto na inteligência artificial e sua contribuição para problemas de localização e otimização tornaram-no um algoritmo fundamental na pesquisa de sistemas inteligentes.

Como funciona o algoritmo de busca A* em Inteligência Artificial?

O algoritmo de pesquisa A* (pronuncia-se 'letra A') é um algoritmo de passagem de gráfico popular e amplamente utilizado em inteligência artificial e ciência da computação. É usado para encontrar o caminho mais curto de um nó inicial a um nó de destino em um grafo ponderado. A* é um algoritmo de busca informado que usa heurística para guiar a busca de forma eficiente. O algoritmo de busca A* funciona da seguinte forma:

O algoritmo começa com uma fila de prioridade para armazenar os nós a serem explorados. Ele também instancia duas estruturas de dados g(n): O custo do caminho mais curto até agora do nó inicial ao nó n e h(n), o custo estimado (heurística) do nó n ao nó de destino. Muitas vezes é uma heurística razoável, o que significa que nunca superestima o custo real para atingir uma meta. Coloque o nó inicial na fila de prioridade e defina seu g(n) como 0. Se a fila de prioridade não estiver vazia, remova o nó com o f(n) mais baixo da fila de prioridade. f(n) = g(n) h(n). Se o nó excluído for o nó de destino, o algoritmo termina e o caminho é encontrado. Caso contrário, expanda o nó e crie seus vizinhos. Para cada nó vizinho, calcule seu valor g(n) inicial, que é a soma do valor g do nó atual e o custo de mudança do nó atual para um nó vizinho. Se o nó vizinho não estiver em ordem de prioridade ou o valor g(n) original for menor que seu valor g atual, atualize seu valor g e defina seu nó pai como o nó atual. Calcule o valor f(n) do nó vizinho e adicione-o à fila de prioridade.

Se o ciclo terminar sem encontrar o nó de destino, o grafo não terá caminho do início ao fim. A chave para a eficiência de A* é o uso de uma função heurística h(n) que fornece uma estimativa do custo restante para atingir a meta de qualquer nó. Ao combinar o custo real g (n) com o custo heurístico h (n), o algoritmo explora efetivamente caminhos promissores, priorizando nós que provavelmente levarão ao caminho mais curto. É importante notar que a eficiência do algoritmo A* é altamente dependente da escolha da função heurística. Heurísticas aceitáveis ​​garantem que o algoritmo sempre encontre o caminho mais curto, mas heurísticas mais informadas e precisas podem levar a uma convergência mais rápida e a um espaço de busca reduzido.

Vantagens do algoritmo de pesquisa A* em inteligência artificial

O algoritmo de busca A* oferece diversas vantagens em cenários de inteligência artificial e resolução de problemas:

    Solução ideal:A* garante encontrar o caminho ideal (mais curto) do nó inicial ao nó de destino no gráfico ponderado, dada uma função heurística aceitável. Esta otimização é uma vantagem decisiva em muitas aplicações onde encontrar o caminho mais curto é essencial.Completude:Se existir uma solução, A* irá encontrá-la, desde que o grafo não tenha um custo infinito. Esta propriedade de completude garante que A* possa tirar vantagem de uma solução, se ela existir.Eficiência:A* é eficiente se uma função heurística eficiente e aceitável for usada. A heurística orienta a busca até um objetivo, concentrando-se em caminhos promissores e evitando explorações desnecessárias, tornando A* mais eficiente do que algoritmos de busca não conscientes, como busca em largura ou busca em profundidade.Versatilidade:A* é amplamente aplicável a diversas áreas problemáticas, incluindo orientação, planejamento de rotas, robótica, desenvolvimento de jogos e muito mais. A* pode ser usado para encontrar soluções ótimas de forma eficiente, desde que uma heurística significativa possa ser definida.Pesquisa otimizada:A* mantém uma ordem de prioridade para selecionar os nós com menor valor de f(n) (g(n) e h(n)) para expansão. Isso permite explorar primeiro caminhos promissores, o que reduz o espaço de busca e leva a uma convergência mais rápida.Eficiência de memória:Ao contrário de alguns outros algoritmos de busca, como a busca em largura, A* armazena apenas um número limitado de nós na fila de prioridade, o que o torna eficiente em termos de memória, especialmente para grafos grandes.Heurísticas ajustáveis:O desempenho de A* pode ser ajustado selecionando diferentes funções heurísticas. Heurísticas mais informadas podem levar a uma convergência mais rápida e a nós menos expandidos.Extensamente pesquisado:A* é um algoritmo bem estabelecido com décadas de pesquisa e aplicações práticas. Muitas otimizações e variações foram desenvolvidas, tornando-o uma ferramenta de solução de problemas confiável e bem compreendida.Pesquisa na internet:A* pode ser usado para busca de caminhos baseada na web, onde o algoritmo atualiza constantemente o caminho de acordo com as mudanças no ambiente ou o aparecimento de novos. Ele permite a tomada de decisões em tempo real em cenários dinâmicos.

Desvantagens do algoritmo de pesquisa A* em inteligência artificial

Embora o algoritmo de pesquisa A* (letra A) seja uma técnica amplamente utilizada e poderosa para resolver problemas de localização de caminhos e travessia de gráficos de IA, ele tem desvantagens e limitações. Aqui estão algumas das principais desvantagens do algoritmo de pesquisa:

    Precisão heurística:O desempenho do algoritmo A* depende muito da precisão da função heurística usada para estimar o custo do nó atual para o nó atual. Se a heurística for inaceitável (nunca superestima o custo real) ou inconsistente (satisfaz a desigualdade triangular), A* pode não encontrar um caminho ideal ou explorar mais nós do que o necessário, afetando sua eficiência e precisão.Uso de memória:A* exige que todos os nós visitados sejam mantidos na memória para acompanhar os caminhos explorados. Às vezes, o uso da memória pode se tornar um problema significativo, especialmente quando se lida com um amplo espaço de pesquisa ou recursos de memória limitados.Complexidade de tempo:Embora A* seja geralmente eficiente, sua complexidade de tempo pode ser uma preocupação para vastos espaços de busca ou grafos. Na pior das hipóteses, A* pode levar exponencialmente mais tempo para encontrar o caminho ideal se a heurística for inadequada para o problema.Gargalo no destino:Em cenários específicos, o algoritmo A* precisa explorar nós distantes do destino antes de finalmente chegar à região de destino. Este problema ocorre quando a heurística precisa direcionar a busca para o objetivo de forma eficaz.Vinculação de custos:A* enfrenta dificuldades quando vários nós têm o mesmo valor f (a soma do custo real e do custo heurístico). A estratégia utilizada pode afetar a otimização e a eficiência do caminho descoberto. Se não for tratado corretamente, pode levar à exploração de nós desnecessários e tornar o algoritmo mais lento.Complexidade em ambientes dinâmicos:Em ambientes dinâmicos onde o custo das arestas ou nós pode mudar durante a busca, A* pode não ser adequado porque não se adapta bem a tais mudanças. A reformulação do zero pode ser computacionalmente cara, e algoritmos D* (Dynamic A*) foram projetados para resolver issoPerfeição no espaço infinito:A* pode não encontrar uma solução no espaço de estados infinito. Nesses casos, ele pode funcionar indefinidamente, explorando um número cada vez maior de nós sem encontrar uma solução. Apesar dessas deficiências, A* ainda é um algoritmo robusto e amplamente utilizado porque pode efetivamente encontrar caminhos ótimos em muitas situações práticas se a função heurística for bem projetada e o espaço de busca for gerenciável. Várias variações e variantes de A* foram propostas para aliviar algumas de suas limitações.

Aplicações do Algoritmo de Busca A* em Inteligência Artificial

O algoritmo de busca A* (letra A) é um algoritmo de busca de caminhos robusto e amplamente utilizado em inteligência artificial e ciência da computação. Sua eficiência e otimização o tornam adequado para diversas aplicações. Aqui estão algumas aplicações típicas do algoritmo de busca A* em inteligência artificial:

    Descoberta em jogos:A* é frequentemente usado em videogames para movimentação de personagens, navegação de IA inimiga e localização do caminho mais curto de um local para outro no mapa do jogo. Sua capacidade de encontrar o caminho ideal com base no custo e na heurística o torna ideal para aplicações em tempo real, como jogos.Robótica e Veículos Autônomos:A* é usado em robótica e navegação de veículos autônomos para planejar uma rota ideal para os robôs chegarem a um destino, evitando obstáculos e considerando os custos do terreno. Isto é crucial para um movimento eficiente e seguro em ambientes naturais.Resolução de labirinto:A* pode encontrar com eficiência o caminho mais curto através de um labirinto, tornando-o valioso em muitas aplicações de resolução de labirintos, como resolver quebra-cabeças ou navegar em estruturas complexas.Planejamento de rotas e navegação:Em sistemas GPS e aplicações de mapeamento, A* pode ser usado para encontrar a rota ideal entre dois pontos em um mapa, considerando fatores como distância, condições de tráfego e topologia da rede rodoviária.Resolução de quebra-cabeças:A* pode resolver vários quebra-cabeças de diagramas, como quebra-cabeças deslizantes, Sudoku e o problema dos 8 quebra-cabeças. Alocação de Recursos: Em cenários onde os recursos devem ser alocados de forma otimizada, A* pode ajudar a encontrar o caminho de alocação mais eficiente, minimizando custos e maximizando a eficiência.Roteamento de rede:A* pode ser usado em redes de computadores para encontrar a rota mais eficiente para pacotes de dados de um nó de origem a um nó de destino.Processamento de Linguagem Natural (PNL):Em algumas tarefas de PNL, A* pode gerar respostas coerentes e contextuais pesquisando possíveis sequências de palavras com base em sua probabilidade e relevância.Planejamento de caminho em robótica:A* pode ser utilizado para planejar o caminho de um robô de um ponto a outro, considerando diversas restrições, como evitar obstáculos ou minimizar o consumo de energia.IA do jogo:A* também é usado para tomar decisões inteligentes para personagens não-jogadores (NPCs), como determinar a melhor maneira de alcançar um objetivo ou coordenar movimentos em um jogo baseado em equipe.

Esses são apenas alguns exemplos de como o algoritmo de busca A* encontra aplicações em diversas áreas da inteligência artificial. Sua flexibilidade, eficiência e otimização fazem dele uma ferramenta valiosa para muitos problemas.

Programa C para Algoritmo de Pesquisa A* em Inteligê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++ para Algoritmo de Pesquisa A* em Inteligê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>

Explicação:

    Nó de estrutura:Isso define uma estrutura de nó que representa uma célula da grade. Ele contém as coordenadas xey do nó, o custo g do nó inicial até aquele nó, o valor heurístico h (custo estimado daquele nó até o nó de destino) e um ponteiro para o nó de destino.
  1. nó inicial do caminho.
  2. Calcular heurística:Esta função calcula uma heurística usando a distância euclidiana entre um nó e o alvo AStarSearch: Esta função executa o algoritmo de pesquisa A*. Ele pega as coordenadas de início e destino, uma grade, e retorna um vetor de pares que representa as coordenadas do caminho mais curto do início ao fim.Primário:A função principal do programa obtém grades de entrada, origem e coordenadas de destino do usuário. Em seguida, ele chama AStarSearch para encontrar o caminho mais curto e imprime o resultado. Nó de estrutura: define uma estrutura de nó que representa uma célula da grade. Ele contém as coordenadas x e y do nó, o custo g do nó inicial até aquele nó, o valor heurístico h (custo estimado desse nó até o nó de destino) e um ponteiro para o nó inicial do caminho.Calcular heurística:Esta função calcula heurística usando a distância euclidiana entre um nó e o alvo AStarSearch: Esta função executa o algoritmo de pesquisa A*. Ele pega as coordenadas de início e destino, uma grade, e retorna um vetor de pares que representa as coordenadas do caminho mais curto do início ao fim.

Saída de amostra

 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 para Algoritmo de Pesquisa A* em Inteligê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* Complexidade do algoritmo de pesquisa em inteligência artificial

O algoritmo de pesquisa A* (pronuncia-se 'A-star') é um algoritmo de busca de caminho e travessia de gráfico popular e amplamente utilizado em inteligência artificial. Encontrar o caminho mais curto entre dois nós em um ambiente gráfico ou baseado em grade geralmente é comum. O algoritmo combina os elementos de busca do melhor primeiro de Dijkstra e gananciosos para explorar o espaço de busca e, ao mesmo tempo, garantir a otimização de forma eficiente. Vários fatores determinam a complexidade do algoritmo de busca A*. Tamanho do gráfico (nós e arestas): O número de nós e arestas de um gráfico afeta muito a complexidade do algoritmo. Mais nós e arestas significam mais opções possíveis para explorar, o que pode aumentar o tempo de execução do algoritmo.

poda alfa-beta

Função heurística: A* usa uma função heurística (geralmente denotada como h(n)) para estimar o custo do nó atual até o nó de destino. A precisão desta heurística afeta muito a eficiência da busca A*. Uma boa heurística pode ajudar a guiar a busca para um objetivo mais rapidamente, enquanto uma heurística ruim pode levar a buscas desnecessárias.

    Estruturas de dados:A* mantém duas estruturas de dados principais: uma lista aberta (fila prioritária) e uma lista fechada (ou pool visitado). A eficiência dessas estruturas de dados, juntamente com a implementação escolhida (por exemplo, heaps binários de fila de prioridade), afeta o desempenho do algoritmo.Fator de ramificação:O número médio de seguidores de cada nó afeta o número de nós expandidos durante a busca. Um fator de ramificação mais alto pode levar a mais exploração, o que aumentaOtimização e completude:A* garante tanto a otimalidade (encontrar o caminho mais curto) quanto a completude (encontrar uma solução que existe). No entanto, esta garantia acarreta uma compensação em termos de complexidade computacional, uma vez que o algoritmo deve explorar diferentes caminhos para obter um desempenho ideal. Em relação à complexidade do tempo, a função heurística escolhida afeta A* no pior caso. Com uma heurística aceita (que nunca superestima o verdadeiro custo para atingir a meta), A* expande o menor número de nós entre os algoritmos de otimização. A complexidade de tempo do pior caso de A * é exponencial no pior caso O (b ^ d), onde 'b' é o fator de ramificação efetivo (número médio de seguidores por nó) e 'd' é o fator ideal

Na prática, entretanto, A* geralmente tem um desempenho significativamente melhor devido à influência de uma função heurística que ajuda a guiar o algoritmo para caminhos promissores. No caso de uma heurística bem projetada, o fator de ramificação efetivo é muito menor, o que leva a uma abordagem mais rápida da solução ótima.