logo

A* Algoritmo de Búsqueda en Inteligencia Artificial

Introducción al algoritmo de búsqueda A* en IA

A* (pronunciado 'A-star') es un potente algoritmo de búsqueda de rutas y recorrido de gráficos ampliamente utilizado en inteligencia artificial e informática. Se utiliza principalmente para encontrar el camino más corto entre dos nodos en un gráfico, dado el costo estimado de llegar desde el nodo actual al nodo de destino. La principal ventaja del algoritmo es su capacidad para proporcionar una ruta óptima explorando el gráfico de una manera más informada en comparación con los algoritmos de búsqueda tradicionales como el algoritmo de Dijkstra.

El algoritmo A* combina las ventajas de otros dos algoritmos de búsqueda: el algoritmo de Dijkstra y Greedy Best-First Search. Al igual que el algoritmo de Dijkstra, A* garantiza que el camino encontrado sea lo más corto posible pero lo hace de manera más eficiente al dirigir su búsqueda a través de una heurística similar a Greedy Best-First Search. Una función heurística, denotada como h(n), estima el costo de llegar desde cualquier nodo n hasta el nodo de destino.

La idea principal de A* es evaluar cada nodo en función de dos parámetros:

comparación de cadenas en java
    gramo(norte):el costo real para llegar desde el nodo inicial al nodo n. Representa la suma de los costos de los nodos n bordes salientes.h(n):Costo heurístico (también conocido como 'costo de estimación') desde el nodo n hasta el nodo de destino n. Esta función heurística específica del problema debe ser aceptable, lo que significa que nunca sobreestima el costo real de lograr el objetivo. La función de evaluación del nodo n se define como f(n) = g(n) h(n).

El algoritmo A* selecciona los nodos a explorar en función del valor más bajo de f(n), prefiriendo los nodos con el costo total estimado más bajo para alcanzar la meta. El algoritmo A* funciona:

  1. Cree una lista abierta de nodos encontrados pero no explorados.
  2. Cree una lista cerrada para contener nodos ya explorados.
  3. Agregue un nodo inicial a la lista abierta con un valor inicial de g
  4. Repita los siguientes pasos hasta que la lista abierta esté vacía o llegue al nodo de destino:
    1. Encuentre el nodo con el valor f más pequeño (es decir, el nodo con el menor g(n) h(n)) en la lista abierta.
    2. Mueva el nodo seleccionado de la lista abierta a la lista cerrada.
    3. Cree todos los descendientes válidos del nodo seleccionado.
    4. Para cada sucesor, calcule su valor g como la suma del valor g del nodo actual y el costo de pasar del nodo actual al nodo sucesor. Actualice el valor g del rastreador cuando encuentre una ruta mejor.
    5. Si el seguidor no está en la lista abierta, agréguelo con el valor g calculado y calcule su valor h. Si ya está en la lista abierta, actualice su valor g si la nueva ruta es mejor.
    6. Repita el ciclo. El algoritmo A* termina cuando se alcanza el nodo objetivo o cuando la lista abierta se vacía, lo que indica que no hay rutas desde el nodo inicial hasta el nodo objetivo. El algoritmo de búsqueda A* se utiliza ampliamente en diversos campos, como la robótica, los videojuegos, el enrutamiento de redes y los problemas de diseño, porque es eficiente y puede encontrar rutas óptimas en gráficos o redes.

Sin embargo, elegir una función heurística adecuada y aceptable es esencial para que el algoritmo funcione correctamente y proporcione una solución óptima.

Algoritmos de búsqueda informados

Historia del algoritmo de búsqueda A* en Inteligencia Artificial

Fue desarrollado por Peter Hart, Nils Nilsson y Bertram Raphael en el Instituto de Investigación de Stanford (ahora SRI International) como una extensión del algoritmo de Dijkstra y otros algoritmos de búsqueda de la época. A* se publicó por primera vez en 1968 y rápidamente ganó reconocimiento por su importancia y eficacia en las comunidades de inteligencia artificial y ciencias de la computación. A continuación se ofrece una breve descripción de los hitos más críticos en la historia del algoritmo de búsqueda A*:

    Algoritmos de búsqueda temprana:Antes del desarrollo de A*, existían varios algoritmos de búsqueda de gráficos, incluida la búsqueda en profundidad (DFS) y la búsqueda en amplitud (BFS). Aunque estos algoritmos ayudaron a encontrar caminos, no garantizaron la optimización ni consideraron heurísticas para guiar la búsqueda.Algoritmo de Dijkstra:En 1959, el informático holandés Edsger W. Dijkstra introdujo el algoritmo de Dijkstra, que encontró el camino más corto en un gráfico ponderado con pesos de borde no negativos. El algoritmo de Dijkstra era eficiente, pero debido a su naturaleza exhaustiva, tenía limitaciones cuando se usaba en gráficos más grandes oBúsqueda informada:Se han desarrollado algoritmos de búsqueda basados ​​en el conocimiento (también conocidos como búsqueda heurística) para incorporar información heurística, como costos estimados, para guiar el proceso de búsqueda de manera eficiente. Greedy Best-First Search era uno de esos algoritmos, pero no garantizaba la optimización para encontrar el camino más corto.Un* desarrollo:En 1968, Peter Hart, Nils Nilsson y Bertram Raphael introdujeron el algoritmo A* como una combinación del algoritmo de Dijkstra y Greedy Best-First Search. A* utilizó una función heurística para estimar el costo desde el nodo actual hasta el nodo de destino combinándolo con el costo real de llegar al nodo actual. Esto permitió a A* explorar el gráfico de manera más consciente, evitando caminos innecesarios y garantizando una solución óptima.Justicia y Perfección:Los autores de A* demostraron que el algoritmo es perfecto (siempre encuentra una solución si existe) y óptimo (encuentra el camino más corto) bajo ciertas condiciones.Adopción y progreso generalizados:A* rápidamente ganó popularidad en las comunidades de IA y TI debido a su eficiencia. Los investigadores y desarrolladores han ampliado y aplicado el algoritmo A* a varios campos, incluidos la robótica, los videojuegos, la ingeniería y el enrutamiento de redes. A lo largo de los años se han propuesto varias variaciones y optimizaciones del algoritmo A*, como Incremental A* y Parallel A*. Hoy en día, el algoritmo de búsqueda A* sigue siendo un algoritmo fundamental y ampliamente utilizado en inteligencia artificial y recorrido de gráficos. Sigue desempeñando un papel esencial en diversas aplicaciones y campos de investigación. Su impacto en la inteligencia artificial y su contribución a los problemas de optimización y búsqueda de rutas lo han convertido en un algoritmo fundamental en la investigación de sistemas inteligentes.

¿Cómo funciona el algoritmo de búsqueda A* en Inteligencia Artificial?

El algoritmo de búsqueda A* (pronunciado 'letra A') es un algoritmo de recorrido de gráficos popular y ampliamente utilizado en inteligencia artificial e informática. Se utiliza para encontrar la ruta más corta desde un nodo inicial hasta un nodo destino en un gráfico ponderado. A* es un algoritmo de búsqueda informado que utiliza heurísticas para guiar la búsqueda de manera eficiente. El algoritmo de búsqueda A* funciona de la siguiente manera:

El algoritmo comienza con una cola de prioridad para almacenar los nodos a explorar. También crea una instancia de dos estructuras de datos g(n): el costo de la ruta más corta hasta el momento desde el nodo inicial al nodo n y h(n), el costo estimado (heurístico) desde el nodo n hasta el nodo de destino. A menudo es una heurística razonable, lo que significa que nunca sobreestima el costo real de lograr un objetivo. Coloque el nodo inicial en la cola de prioridad y establezca su g (n) en 0. Si la cola de prioridad no está vacía, elimine el nodo con la f (n) más baja de la cola de prioridad. f(norte) = gramo(norte) h(norte). Si el nodo eliminado es el nodo de destino, el algoritmo finaliza y se encuentra la ruta. De lo contrario, expanda el nodo y cree sus vecinos. Para cada nodo vecino, calcule su valor g(n) inicial, que es la suma del valor g del nodo actual y el costo de pasar del nodo actual a un nodo vecino. Si el nodo vecino no está en orden de prioridad o el valor g(n) original es menor que su valor g actual, actualice su valor g y establezca su nodo principal en el nodo actual. Calcule el valor f(n) del nodo vecino y agréguelo a la cola de prioridad.

Si el ciclo termina sin encontrar el nodo destino, el gráfico no tiene recorrido de principio a fin. La clave de la eficiencia de A* es el uso de una función heurística h(n) que proporciona una estimación del coste restante para alcanzar el objetivo de cualquier nodo. Al combinar el costo real g (n) con el costo heurístico h (n), el algoritmo explora efectivamente caminos prometedores, priorizando los nodos que probablemente conduzcan al camino más corto. Es importante señalar que la eficiencia del algoritmo A* depende en gran medida de la elección de la función heurística. Las heurísticas aceptables garantizan que el algoritmo siempre encuentre el camino más corto, pero unas heurísticas más informadas y precisas pueden conducir a una convergencia más rápida y un espacio de búsqueda reducido.

Ventajas del algoritmo de búsqueda A* en Inteligencia Artificial

El algoritmo de búsqueda A* ofrece varias ventajas en escenarios de inteligencia artificial y resolución de problemas:

    Solucion optima:A* garantiza encontrar la ruta óptima (la más corta) desde el nodo inicial hasta el nodo destino en el gráfico ponderado dada una función heurística aceptable. Esta optimización es una ventaja decisiva en muchas aplicaciones donde encontrar el camino más corto es esencial.Lo completo:Si existe una solución, A* la encontrará, siempre que la gráfica no tenga un costo infinito. Esta propiedad de integridad garantiza que A* pueda aprovechar una solución si existe.Eficiencia:A* es eficiente si se utiliza una función heurística eficiente y aceptable. La heurística guía la búsqueda hacia un objetivo centrándose en caminos prometedores y evitando exploraciones innecesarias, lo que hace que A* sea más eficiente que los algoritmos de búsqueda no conscientes, como la búsqueda en amplitud o la búsqueda en profundidad.Versatilidad:A* es ampliamente aplicable a diversas áreas problemáticas, incluida la orientación, la planificación de rutas, la robótica, el desarrollo de juegos y más. A* se puede utilizar para encontrar soluciones óptimas de manera eficiente siempre que se pueda definir una heurística significativa.Búsqueda optimizada:A* mantiene un orden de prioridad para seleccionar los nodos con el valor menor de f(n) (g(n) y h(n)) para la expansión. Esto le permite explorar primero caminos prometedores, lo que reduce el espacio de búsqueda y conduce a una convergencia más rápida.Eficiencia de la memoria:A diferencia de otros algoritmos de búsqueda, como la búsqueda en amplitud, A* almacena solo un número limitado de nodos en la cola de prioridad, lo que lo hace eficiente en memoria, especialmente para gráficos grandes.Heurísticas ajustables:El rendimiento de A* se puede ajustar seleccionando diferentes funciones heurísticas. Unas heurísticas más informadas pueden conducir a una convergencia más rápida y a nodos menos expandidos.Ampliamente investigado:A* es un algoritmo bien establecido con décadas de investigación y aplicaciones prácticas. Se han desarrollado muchas optimizaciones y variaciones, lo que la convierte en una herramienta de resolución de problemas confiable y bien entendida.Búsqueda Web:A* se puede utilizar para la búsqueda de rutas basada en web, donde el algoritmo actualiza constantemente la ruta según los cambios en el entorno o la aparición de nuevos. Permite la toma de decisiones en tiempo real en escenarios dinámicos.

Desventajas del algoritmo de búsqueda A* en inteligencia artificial

Aunque el algoritmo de búsqueda A* (letra A) es una técnica poderosa y ampliamente utilizada para resolver problemas de recorrido de gráficos y búsqueda de rutas de IA, tiene desventajas y limitaciones. Estas son algunas de las principales desventajas del algoritmo de búsqueda:

    Precisión heurística:El rendimiento del algoritmo A* depende en gran medida de la precisión de la función heurística utilizada para estimar el costo desde el nodo actual hasta el Si la heurística es inaceptable (nunca sobreestima el costo real) o inconsistente (satisface la desigualdad del triángulo), A* Es posible que no encuentre una ruta óptima o que explore más nodos de los necesarios, lo que afectará su eficiencia y precisión.Uso de memoria:A* requiere que todos los nodos visitados se mantengan en la memoria para realizar un seguimiento de las rutas exploradas. El uso de la memoria a veces puede convertirse en un problema importante, especialmente cuando se trata de un espacio de búsqueda amplio o recursos de memoria limitados.Complejidad del tiempo:Aunque A* es generalmente eficiente, su complejidad temporal puede ser una preocupación para grandes espacios de búsqueda o gráficos. En el peor de los casos, A* puede tardar exponencialmente más en encontrar el camino óptimo si la heurística no es apropiada para el problema.Cuello de botella en el destino:En escenarios específicos, el algoritmo A* necesita explorar nodos alejados del destino antes de llegar finalmente a la región de destino. Este problema ocurre cuando la heurística necesita dirigir la búsqueda hacia la meta de manera temprana y efectiva.Vinculación de costos:A* enfrenta dificultades cuando varios nodos tienen el mismo valor f (la suma del costo real y el costo heurístico). La estrategia utilizada puede afectar la optimización y eficiencia del camino descubierto. Si no se maneja correctamente, puede provocar que se exploren nodos innecesarios y ralentizar el algoritmo.Complejidad en entornos dinámicos:En entornos dinámicos donde el costo de los bordes o nodos puede cambiar durante la búsqueda, A* puede no ser adecuado porque no se adapta bien a dichos cambios. La reformulación desde cero puede ser costosa desde el punto de vista computacional, y los algoritmos D* (Dynamic A*) fueron diseñados para resolver esto.Perfección en el espacio infinito:Es posible que A* no encuentre una solución en un espacio de estados infinito. En tales casos, puede ejecutarse indefinidamente, explorando un número cada vez mayor de nodos sin encontrar una solución. A pesar de estas deficiencias, A* sigue siendo un algoritmo robusto y ampliamente utilizado porque puede encontrar rutas óptimas de manera efectiva en muchas situaciones prácticas si la función heurística está bien diseñada y el espacio de búsqueda es manejable. Se han propuesto varias variaciones y variantes de A* para aliviar algunas de sus limitaciones.

Aplicaciones del Algoritmo de Búsqueda A* en Inteligencia Artificial

El algoritmo de búsqueda A* (letra A) es un algoritmo de búsqueda de rutas robusto y ampliamente utilizado en inteligencia artificial e informática. Su eficiencia y optimización lo hacen adecuado para diversas aplicaciones. A continuación se muestran algunas aplicaciones típicas del algoritmo de búsqueda A* en inteligencia artificial:

    Búsqueda de caminos en los juegos:A* se utiliza a menudo en videojuegos para el movimiento de personajes, la navegación de la IA enemiga y para encontrar el camino más corto de un lugar a otro en el mapa del juego. Su capacidad para encontrar la ruta óptima en función del costo y la heurística lo hace ideal para aplicaciones en tiempo real como los juegos.Robótica y Vehículos Autónomos:A* se utiliza en robótica y navegación de vehículos autónomos para planificar una ruta óptima para que los robots lleguen a un destino, evitando obstáculos y considerando los costos del terreno. Esto es crucial para un movimiento eficiente y seguro en entornos naturales.Resolución de laberintos:A* puede encontrar eficientemente el camino más corto a través de un laberinto, lo que lo hace valioso en muchas aplicaciones de resolución de laberintos, como resolver acertijos o navegar por estructuras complejas.Planificación de rutas y navegación:En sistemas GPS y aplicaciones de mapeo, A* se puede utilizar para encontrar la ruta óptima entre dos puntos en un mapa, considerando factores como la distancia, las condiciones del tráfico y la topología de la red de carreteras.Resolución de acertijos:A* puede resolver varios acertijos de diagramas, como rompecabezas deslizantes, Sudoku y el problema de 8 acertijos. Asignación de recursos: en escenarios donde los recursos deben asignarse de manera óptima, A* puede ayudar a encontrar la ruta de asignación más eficiente, minimizando los costos y maximizando la eficiencia.Enrutamiento de red:A* se puede utilizar en redes informáticas para encontrar la ruta más eficiente para paquetes de datos desde un nodo de origen a un nodo de destino.Procesamiento del lenguaje natural (PNL):En algunas tareas de PNL, A* puede generar respuestas coherentes y contextuales buscando posibles secuencias de palabras en función de su probabilidad y relevancia.Planificación de rutas en robótica:A* se puede utilizar para planificar la trayectoria de un robot de un punto a otro, considerando diversas limitaciones, como evitar obstáculos o minimizar el consumo de energía.IA del juego:A* también se utiliza para tomar decisiones inteligentes para personajes no jugadores (NPC), como determinar la mejor manera de alcanzar un objetivo o coordinar movimientos en un juego en equipo.

Estos son sólo algunos ejemplos de cómo el algoritmo de búsqueda A* encuentra aplicaciones en diversas áreas de la inteligencia artificial. Su flexibilidad, eficiencia y optimización lo convierten en una herramienta valiosa para muchos problemas.

unión izquierda vs unión derecha

Programa C para el Algoritmo de Búsqueda A* en Inteligencia 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 el algoritmo de búsqueda A* en Inteligencia Artificial

 #include #include #include using namespace std; struct Node { int x, y; // Coordinates of the node int g; // Cost from the start node to this node int h; // Heuristic value (estimated cost from this node to the goal node) Node* parent; // Parent node in the path Node (int x, int y): x(x), y(y), g(0), h(0), parent(nullptr) {} // Calculate the total cost (f = g + h) int f () const { return g + h; } }; // Heuristic function (Euclidean distance) int calculateHeuristic (int x, int y, int goals, int goal) { return static cast (sqrt (pow (goals - x, 2) + pow (goal - y, 2))); } // A* search algorithm vector<pair> AStarSearch (int startX, int startY, int goals, int goal, vector<vector>&amp; grid) { vector<pair> path; int rows = grid. size (); int cols = grid [0].size (); // Create the open and closed lists Priority queue <node*, vector, function> open List([](Node* lhs, Node* rhs) { return lhs-&gt;f() &gt; rhs-&gt;f(); }); vector<vector> closed List (rows, vector (cols, false)); // Push the start node to the open list openList.push(start Node); // Main A* search loop while (! Open-list. Empty ()) { // Get the node with the lowest f value from the open list Node* current = open-list. Top (); openest. pop (); // Check if the current node is the goal node if (current-&gt;x == goals &amp;&amp; current-&gt;y == goal) { // Reconstruct the path while (current! = nullptr) { path. push_back(make_pair(current-&gt;x, current-&gt;y)); current = current-&gt;parent; } Reverse (path. Begin(), path.end ()); break; } // Mark the current node as visited (in the closed list) Closed-list [current-&gt;x] [current-&gt;y] = true; // Generate successors (adjacent nodes) int dx [] = {1, 0, -1, 0}; int dy [] = {0, 1, 0, -1}; for (int i = 0; i x + dx [i]; int new Y = current-&gt;y + dy [i]; } break; } successor-&gt;parent = current; open List.push(successor); } // Cleanup memory for (Node* node: open List) { delete node; } return path; } int main () { int rows, cols; cout &lt;&gt; rows; cout &lt;&gt; cols; vector<vector> grid (rows, vector(cols)); cout &lt;&lt; &apos;Enter the grid (0 for empty, 1 for obstacle):&apos; &lt;&lt; endl; for (int i = 0; i &lt; rows; i++) { for (int j = 0; j&gt; grid[i][j]; } } int startX, startY, goalX, goalY; cout &lt;&gt; startX &gt;&gt; start; cout &lt;&gt; goals &gt;&gt; goals; vector<pair> path = AStarSearch (startX, startY, goal, goal, grid); if (! path. Empty ()) { cout &lt;&lt; &apos;Shortest path from (&apos; &lt;&lt; startX &lt;&lt; &apos;,&apos; &lt;&lt; start &lt;&lt; &apos;) to (&apos; &lt;&lt; goal &lt;&lt; &apos;,&apos; &lt;&lt; goal &lt;&lt; &apos;):&apos; &lt;&lt; endl; for (const auto&amp; point: path) { cout &lt;&lt; &apos;(&apos; &lt;&lt; point. first &lt;&lt; &apos;,&apos; &lt;&lt; point. second &lt;&lt; &apos;) &apos;; } cout &lt;&lt; endl; } else { cout &lt;&lt; &apos;No path found!&apos; &lt;&lt; endl; } return 0; } </pair></vector></vector></node*,></pair></vector></pair>

Explicación:

    Nodo de estructura:Esto define una estructura de nodo que representa una celda de la cuadrícula. Contiene las coordenadas x e y del nodo, el costo g desde el nodo inicial hasta ese nodo, el valor heurístico h (costo estimado desde ese nodo hasta el nodo de destino) y un puntero al
  1. Nodo inicial del camino.
  2. Calcular heurística:Esta función calcula una heurística utilizando la distancia euclidiana entre un nodo y el objetivo AStarSearch: Esta función ejecuta el algoritmo de búsqueda A*. Toma las coordenadas de inicio y destino, una cuadrícula, y devuelve un vector de pares que representan las coordenadas del camino más corto de principio a fin.Primario:La función principal del programa toma cuadrículas de entrada, coordenadas de origen y destino del usuario. Luego llama a AStarSearch para encontrar la ruta más corta e imprime el resultado. Nodo de estructura: define una estructura de nodo que representa una celda de la cuadrícula. Contiene las coordenadas xey del nodo, el costo g desde el nodo inicial hasta ese nodo, el valor heurístico h (costo estimado desde ese nodo hasta el nodo de destino) y un puntero al nodo inicial de la ruta.Calcular heurística:Esta función calcula la heurística utilizando la distancia euclidiana entre un nodo y el objetivo AStarSearch: esta función ejecuta el algoritmo de búsqueda A*. Toma las coordenadas de inicio y destino, una cuadrícula, y devuelve un vector de pares que representan las coordenadas del camino más corto de principio a fin.

Salida de muestra

 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 el Algoritmo de Búsqueda A* en Inteligencia 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* Complejidad del algoritmo de búsqueda en inteligencia artificial

El algoritmo de búsqueda A* (pronunciado 'A-star') es un algoritmo de búsqueda de rutas y recorrido de gráficos popular y ampliamente utilizado en inteligencia artificial. Generalmente es común encontrar el camino más corto entre dos nodos en un entorno gráfico o basado en cuadrícula. El algoritmo combina los elementos de búsqueda de Dijkstra y los codiciosos mejores primero para explorar el espacio de búsqueda y al mismo tiempo garantizar la optimización de manera eficiente. Varios factores determinan la complejidad del algoritmo de búsqueda A*. Tamaño del gráfico (nodos y aristas): la cantidad de nodos y aristas de un gráfico afecta en gran medida la complejidad del algoritmo. Más nodos y aristas significan más opciones posibles para explorar, lo que puede aumentar el tiempo de ejecución del algoritmo.

Función heurística: A* utiliza una función heurística (a menudo denominada h(n)) para estimar el costo desde el nodo actual hasta el nodo de destino. La precisión de esta heurística afecta en gran medida la eficiencia de la búsqueda A*. Una buena heurística puede ayudar a guiar la búsqueda hacia un objetivo más rápidamente, mientras que una mala heurística puede conducir a búsquedas innecesarias.

    Estructuras de datos:A* mantiene dos estructuras de datos principales: una lista abierta (cola de prioridad) y una lista cerrada (o grupo visitado). La eficiencia de estas estructuras de datos, junto con la implementación elegida (por ejemplo, montones binarios de cola de prioridad), afecta el rendimiento del algoritmo.Factor de sucursal:La cantidad promedio de seguidores para cada nodo afecta la cantidad de nodos expandidos durante la búsqueda. Un factor de ramificación más alto puede conducir a una mayor exploración, lo que aumentaOptimidad e integridad:A* garantiza tanto la optimización (encontrar el camino más corto) como la integridad (encontrar una solución que exista). Sin embargo, esta garantía tiene una contrapartida en términos de complejidad computacional, ya que el algoritmo debe explorar diferentes caminos para lograr un rendimiento óptimo. En cuanto a la complejidad temporal, la función heurística elegida afecta a A* en el peor de los casos. Con una heurística aceptada (que nunca sobreestima el costo real de alcanzar la meta), A* expande la menor cantidad de nodos entre los algoritmos de optimización. La complejidad temporal del peor de los casos de A * es exponencial en el peor de los casos O(b ^ d), donde 'b' es el factor de ramificación efectivo (número promedio de seguidores por nodo) y 'd' es el óptimo

En la práctica, sin embargo, A* suele funcionar significativamente mejor debido a la influencia de una función heurística que ayuda a guiar el algoritmo hacia caminos prometedores. En el caso de una heurística bien diseñada, el factor de ramificación efectivo es mucho menor, lo que conduce a un acercamiento más rápido a la solución óptima.