AI의 A* 검색 알고리즘 소개
A*('A-스타'로 발음)는 인공 지능과 컴퓨터 과학에서 널리 사용되는 강력한 그래프 탐색 및 경로 찾기 알고리즘입니다. 현재 노드에서 목적지 노드까지의 예상 비용을 고려하여 그래프에서 두 노드 사이의 최단 경로를 찾는 데 주로 사용됩니다. 알고리즘의 가장 큰 장점은 Dijkstra 알고리즘과 같은 기존 검색 알고리즘에 비해 더 많은 정보를 바탕으로 그래프를 탐색하여 최적의 경로를 제공할 수 있다는 것입니다.
알고리즘 A*는 Dijkstra 알고리즘과 Greedy Best-First Search라는 두 가지 다른 검색 알고리즘의 장점을 결합합니다. Dijkstra의 알고리즘과 마찬가지로 A*는 발견된 경로가 가능한 한 짧도록 보장하지만 Greedy Best-First Search와 유사한 휴리스틱을 통해 검색을 지시하여 보다 효율적으로 수행합니다. h(n)으로 표시된 휴리스틱 함수는 특정 노드 n에서 대상 노드까지 이동하는 데 드는 비용을 추정합니다.
A*의 주요 아이디어는 두 가지 매개변수를 기반으로 각 노드를 평가하는 것입니다.
언제나 모키토
알고리즘 A*는 f(n)의 가장 낮은 값을 기반으로 탐색할 노드를 선택하며, 목표를 달성하기 위해 예상 총 비용이 가장 낮은 노드를 선호합니다. A* 알고리즘은 다음과 같이 작동합니다.
- 발견되었지만 탐색되지 않은 노드의 공개 목록을 만듭니다.
- 이미 탐색한 노드를 보관할 닫힌 목록을 만듭니다.
- 초기 값 g를 사용하여 열린 목록에 시작 노드를 추가합니다.
- 열린 목록이 비어 있거나 대상 노드에 도달할 때까지 다음 단계를 반복합니다.
- 열린 목록에서 f-값이 가장 작은 노드(즉, 작은 g(n) h(n)를 갖는 노드)를 찾습니다.
- 선택한 노드를 열린 목록에서 닫힌 목록으로 이동합니다.
- 선택한 노드의 유효한 하위 항목을 모두 만듭니다.
- 각 후속 노드에 대해 현재 노드의 g 값과 현재 노드에서 후속 노드로 이동하는 비용의 합으로 g 값을 계산합니다. 더 나은 경로가 발견되면 추적기의 g 값을 업데이트합니다.
- 팔로어가 열린 목록에 없으면 계산된 g-값을 추가하고 h-값을 계산합니다. 이미 열려 있는 목록에 있는 경우 새 경로가 더 좋으면 g 값을 업데이트하세요.
- 주기를 반복하십시오. 알고리즘 A*는 대상 노드에 도달하거나 열린 목록이 비워지면 종료되어 시작 노드에서 대상 노드까지의 경로가 없음을 나타냅니다. A* 검색 알고리즘은 효율적이고 그래프나 네트워크에서 최적의 경로를 찾을 수 있기 때문에 로봇 공학, 비디오 게임, 네트워크 라우팅, 설계 문제 등 다양한 분야에서 널리 사용됩니다.
그러나 알고리즘이 올바르게 수행되고 최적의 솔루션을 제공하려면 적합하고 수용 가능한 휴리스틱 기능을 선택하는 것이 필수적입니다.
인공지능의 A* 검색 알고리즘의 역사
이는 스탠포드 연구소(현재 SRI International)의 Peter Hart, Nils Nilsson 및 Bertram Raphael에 의해 Dijkstra 알고리즘 및 당시의 기타 검색 알고리즘의 확장으로 개발되었습니다. A*는 1968년에 처음 출판되었으며 인공 지능 및 컴퓨터 과학 커뮤니티에서 그 중요성과 효율성에 대해 빠르게 인정을 받았습니다. 다음은 검색 알고리즘 A*의 역사에서 가장 중요한 이정표에 대한 간략한 개요입니다.
A* 검색 알고리즘은 인공 지능에서 어떻게 작동합니까?
A*('문자 A'로 발음) 검색 알고리즘은 인공 지능과 컴퓨터 과학에서 인기 있고 널리 사용되는 그래프 탐색 알고리즘입니다. 가중치 그래프에서 시작 노드부터 목표 노드까지의 최단 경로를 찾는 데 사용됩니다. A*는 휴리스틱을 사용하여 검색을 효율적으로 안내하는 정보 검색 알고리즘입니다. 검색 알고리즘 A*는 다음과 같이 작동합니다.
알고리즘은 탐색할 노드를 저장하는 우선순위 큐로 시작합니다. 또한 두 가지 데이터 구조 g(n), 즉 시작 노드에서 노드 n까지의 최단 경로 비용과 h(n), 노드 n에서 대상 노드까지의 추정 비용(휴리스틱)을 인스턴스화합니다. 이는 합리적인 경험적 방법인 경우가 많습니다. 즉, 목표 달성에 드는 실제 비용을 결코 과대평가하지 않는다는 의미입니다. 초기 노드를 우선순위 큐에 넣고 g(n)을 0으로 설정합니다. 우선순위 큐가 비어 있지 않으면 f(n)이 가장 낮은 노드를 우선순위 큐에서 제거합니다. f(n) = g(n) h(n). 삭제된 노드가 대상 노드이면 알고리즘이 종료되고 경로를 찾습니다. 그렇지 않으면 노드를 확장하고 이웃을 만듭니다. 각 이웃 노드에 대해 현재 노드의 g 값과 현재 노드에서 이웃 노드로 이동하는 비용의 합인 초기 g(n) 값을 계산합니다. 이웃 노드의 우선순위가 없거나 원래 g(n) 값이 현재 g 값보다 작은 경우 해당 g 값을 업데이트하고 상위 노드를 현재 노드로 설정합니다. 이웃 노드로부터 f(n) 값을 계산하여 우선순위 큐에 추가합니다.
대상 노드를 찾지 못한 채 순환이 끝나면 그래프에는 처음부터 끝까지 경로가 없습니다. A*의 효율성에 대한 핵심은 모든 노드의 목표에 도달하는 데 남은 비용에 대한 추정치를 제공하는 휴리스틱 함수 h(n)를 사용하는 것입니다. 실제 비용 g(n)와 경험적 비용 h(n)를 결합함으로써 알고리즘은 유망한 경로를 효과적으로 탐색하고 최단 경로로 이어질 가능성이 있는 노드의 우선 순위를 지정합니다. A* 알고리즘의 효율성은 휴리스틱 기능의 선택에 크게 좌우된다는 점에 유의하는 것이 중요합니다. 허용 가능한 휴리스틱은 알고리즘이 항상 최단 경로를 찾도록 보장하지만, 더 많은 정보와 정확한 휴리스틱을 사용하면 수렴 속도가 빨라지고 검색 공간이 줄어들 수 있습니다.
인공지능에서 A* 검색 알고리즘의 장점
A* 검색 알고리즘은 인공 지능 및 문제 해결 시나리오에서 여러 가지 이점을 제공합니다.
인공지능에서 A* 검색 알고리즘의 단점
A*(문자 A) 검색 알고리즘은 AI 경로 찾기 및 그래프 탐색 문제를 해결하기 위해 널리 사용되는 강력한 기술이지만 단점과 한계가 있습니다. 검색 알고리즘의 주요 단점은 다음과 같습니다.
인공지능에 A* 검색 알고리즘 적용
검색 알고리즘 A*(문자 A)는 인공 지능 및 컴퓨터 과학에서 널리 사용되는 강력한 길 찾기 알고리즘입니다. 효율성과 최적성으로 인해 다양한 응용 분야에 적합합니다. 인공 지능에서 A* 검색 알고리즘의 몇 가지 일반적인 응용 프로그램은 다음과 같습니다.
이는 A* 검색 알고리즘이 인공 지능의 다양한 영역에서 응용 프로그램을 찾는 방법에 대한 몇 가지 예일 뿐입니다. 유연성, 효율성 및 최적화로 인해 많은 문제에 대한 귀중한 도구가 됩니다.
인공지능의 A* 검색 알고리즘을 위한 C 프로그램
#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 >= 0) && (row = 0) && (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 'cab ride') 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>& 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->f() > rhs->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->x == goals && current->y == goal) { // Reconstruct the path while (current! = nullptr) { path. push_back(make_pair(current->x, current->y)); current = current->parent; } Reverse (path. Begin(), path.end ()); break; } // Mark the current node as visited (in the closed list) Closed-list [current->x] [current->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->y + dy [i]; } break; } successor->parent = current; open List.push(successor); } // Cleanup memory for (Node* node: open List) { delete node; } return path; } int main () { int rows, cols; cout <> rows; cout <> cols; vector<vector> grid (rows, vector(cols)); cout << 'Enter the grid (0 for empty, 1 for obstacle):' << endl; for (int i = 0; i < rows; i++) { for (int j = 0; j> grid[i][j]; } } int startX, startY, goalX, goalY; cout <> startX >> start; cout <> goals >> goals; vector<pair> path = AStarSearch (startX, startY, goal, goal, grid); if (! path. Empty ()) { cout << 'Shortest path from (' << startX << ',' << start << ') to (' << goal << ',' << goal << '):' << endl; for (const auto& point: path) { cout << '(' << point. first << ',' << point. second << ') '; } cout << endl; } else { cout << 'No path found!' << 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'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 && nx = 0 && 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 'A-star') 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'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's number of nodes and edges greatly affects the algorithm'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'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 'b' is the effective branching factor (average number of followers per node) and 'd' 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)> 인공 지능의 A* 검색 알고리즘을 위한 C++ 프로그램
#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>& 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->f() > rhs->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->x == goals && current->y == goal) { // Reconstruct the path while (current! = nullptr) { path. push_back(make_pair(current->x, current->y)); current = current->parent; } Reverse (path. Begin(), path.end ()); break; } // Mark the current node as visited (in the closed list) Closed-list [current->x] [current->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->y + dy [i]; } break; } successor->parent = current; open List.push(successor); } // Cleanup memory for (Node* node: open List) { delete node; } return path; } int main () { int rows, cols; cout <> rows; cout <> cols; vector<vector> grid (rows, vector(cols)); cout << 'Enter the grid (0 for empty, 1 for obstacle):' << endl; for (int i = 0; i < rows; i++) { for (int j = 0; j> grid[i][j]; } } int startX, startY, goalX, goalY; cout <> startX >> start; cout <> goals >> goals; vector<pair> path = AStarSearch (startX, startY, goal, goal, grid); if (! path. Empty ()) { cout << 'Shortest path from (' << startX << ',' << start << ') to (' << goal << ',' << goal << '):' << endl; for (const auto& point: path) { cout << '(' << point. first << ',' << point. second << ') '; } cout << endl; } else { cout << 'No path found!' << endl; } return 0; } </pair></vector></vector></node*,></pair></vector></pair> 설명:
- 경로의 시작 노드.
샘플 출력
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
인공지능의 A* 검색 알고리즘을 위한 Java 프로그램
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 && nx = 0 && 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 'A-star') 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'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's number of nodes and edges greatly affects the algorithm'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'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 'b' is the effective branching factor (average number of followers per node) and 'd' 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* 인공 지능의 검색 알고리즘 복잡성
A*('A-star'로 발음) 검색 알고리즘은 인공 지능에서 인기 있고 널리 사용되는 그래프 순회 및 경로 검색 알고리즘입니다. 그래프나 그리드 기반 환경에서는 두 노드 사이의 최단 경로를 찾는 것이 일반적입니다. 알고리즘은 Dijkstra와 탐욕스러운 최고 우선 검색 요소를 결합하여 최적성을 효율적으로 보장하면서 검색 공간을 탐색합니다. 여러 요인이 A* 검색 알고리즘의 복잡성을 결정합니다. 그래프 크기(노드 및 에지): 그래프의 노드 및 에지 수는 알고리즘의 복잡성에 큰 영향을 미칩니다. 노드와 에지가 많을수록 탐색할 수 있는 옵션이 많아지고, 이는 알고리즘의 실행 시간을 늘릴 수 있음을 의미합니다.
휴리스틱 함수: A*는 휴리스틱 함수(종종 h(n)로 표시됨)를 사용하여 현재 노드에서 대상 노드까지의 비용을 추정합니다. 이 휴리스틱의 정확성은 A* 검색의 효율성에 큰 영향을 미칩니다. 좋은 휴리스틱은 검색을 더 빠르게 목표로 안내하는 데 도움이 되는 반면, 나쁜 휴리스틱은 불필요한 검색으로 이어질 수 있습니다.
그러나 실제로 A*는 알고리즘을 유망한 경로로 안내하는 데 도움이 되는 경험적 기능의 영향으로 인해 훨씬 더 나은 성능을 발휘하는 경우가 많습니다. 잘 설계된 휴리스틱의 경우 유효 분기 인자가 훨씬 작아서 최적의 솔루션에 더 빠르게 접근할 수 있습니다.
호랑이 사자 차이