مقدمة لخوارزمية البحث A* في الذكاء الاصطناعي
A* (تُنطق 'A-star') عبارة عن خوارزمية قوية لمسح الرسم البياني وإيجاد المسار تستخدم على نطاق واسع في الذكاء الاصطناعي وعلوم الكمبيوتر. يتم استخدامه بشكل أساسي للعثور على أقصر مسار بين عقدتين في الرسم البياني، مع الأخذ في الاعتبار التكلفة المقدرة للانتقال من العقدة الحالية إلى العقدة الوجهة. الميزة الرئيسية للخوارزمية هي قدرتها على توفير المسار الأمثل من خلال استكشاف الرسم البياني بطريقة أكثر استنارة مقارنة بخوارزميات البحث التقليدية مثل خوارزمية ديكسترا.
تجمع الخوارزمية A* بين مزايا خوارزميتين بحث أخريين: خوارزمية Dijkstra والبحث Greedy Best-First. مثل خوارزمية 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) كامتداد لخوارزمية ديكسترا وخوارزميات البحث الأخرى في ذلك الوقت. تم نشر A* لأول مرة في عام 1968 وسرعان ما اكتسب شهرة كبيرة لأهميته وفعاليته في مجتمعات الذكاء الاصطناعي وعلوم الكمبيوتر. فيما يلي نظرة عامة مختصرة على أهم المعالم في تاريخ خوارزمية البحث A*:
كيف تعمل خوارزمية البحث A* في الذكاء الاصطناعي؟
تعد خوارزمية البحث A* (تنطق 'الحرف A') خوارزمية اجتياز الرسم البياني شائعة ومستخدمة على نطاق واسع في الذكاء الاصطناعي وعلوم الكمبيوتر. يتم استخدامه للعثور على أقصر مسار من عقدة البداية إلى عقدة الوجهة في الرسم البياني الموزون. A* عبارة عن خوارزمية بحث مستنيرة تستخدم الاستدلال لتوجيه البحث بكفاءة. تعمل خوارزمية البحث A* على النحو التالي:
تبدأ الخوارزمية بقائمة انتظار ذات أولوية لتخزين العقد المراد استكشافها. كما أنه يقوم بإنشاء مثيلين للبيانات g(n): تكلفة أقصر مسار حتى الآن من عقدة البداية إلى العقدة n وh(n)، والتكلفة المقدرة (الاسترشادية) من العقدة n إلى العقدة الوجهة. غالبًا ما يكون ذلك بمثابة إرشاد معقول، مما يعني أنه لا يبالغ أبدًا في تقدير التكلفة الفعلية لتحقيق الهدف. ضع العقدة الأولية في قائمة انتظار الأولوية وقم بتعيين g(n) الخاص بها على 0. إذا لم تكن قائمة انتظار الأولوية فارغة، فقم بإزالة العقدة ذات f(n) الأقل من قائمة انتظار الأولوية. و(ن) = ز(ن) ح(ن). إذا كانت العقدة المحذوفة هي العقدة الوجهة، فستنتهي الخوارزمية ويتم العثور على المسار. وإلا، قم بتوسيع العقدة وإنشاء العقد المجاورة لها. لكل عقدة مجاورة، احسب قيمتها الأولية g(n)، وهي مجموع قيمة g للعقدة الحالية وتكلفة الانتقال من العقدة الحالية إلى العقدة المجاورة. إذا لم تكن العقدة المجاورة في ترتيب الأولوية أو كانت قيمة g(n) الأصلية أقل من قيمة g الحالية، فقم بتحديث قيمة g الخاصة بها وقم بتعيين العقدة الأصلية الخاصة بها على العقدة الحالية. احسب قيمة f(n) من العقدة المجاورة وأضفها إلى قائمة انتظار الأولوية.
إذا انتهت الدورة دون العثور على العقدة الوجهة، فلن يكون للرسم البياني مسار من البداية إلى النهاية. مفتاح كفاءة A* هو استخدامه للدالة الإرشادية h(n) التي توفر تقديرًا للتكلفة المتبقية للوصول إلى هدف أي عقدة. من خلال الجمع بين التكلفة الفعلية g (n) والتكلفة الإرشادية h (n)، تستكشف الخوارزمية بشكل فعال المسارات الواعدة، مع إعطاء الأولوية للعقد التي من المحتمل أن تؤدي إلى أقصر مسار. من المهم ملاحظة أن كفاءة خوارزمية A* تعتمد بشكل كبير على اختيار الوظيفة الإرشادية. تضمن الاستدلالات المقبولة أن الخوارزمية تجد دائمًا أقصر مسار، ولكن الاستدلالات الأكثر استنارة ودقة يمكن أن تؤدي إلى تقارب أسرع وتقليل مساحة البحث.
مزايا خوارزمية البحث A* في الذكاء الاصطناعي
توفر خوارزمية البحث A* العديد من المزايا في الذكاء الاصطناعي وسيناريوهات حل المشكلات:
عيوب خوارزمية البحث A* في الذكاء الاصطناعي
على الرغم من أن خوارزمية البحث A* (الحرف A) هي تقنية قوية ومستخدمة على نطاق واسع لحل مشكلات تحديد مسارات الذكاء الاصطناعي واجتياز الرسم البياني، إلا أن لها عيوبًا وقيودًا. فيما يلي بعض العيوب الرئيسية لخوارزمية البحث:
تطبيقات خوارزمية البحث A* في الذكاء الاصطناعي
خوارزمية البحث A* (الحرف A) هي خوارزمية قوية ومستخدمة على نطاق واسع في مجال الذكاء الاصطناعي وعلوم الكمبيوتر. كفاءتها وأمثلها تجعلها مناسبة لمختلف التطبيقات. فيما يلي بعض التطبيقات النموذجية لخوارزمية البحث A* في الذكاء الاصطناعي:
هذه مجرد أمثلة قليلة لكيفية عثور خوارزمية البحث A* على التطبيقات في مجالات مختلفة من الذكاء الاصطناعي. إن مرونتها وكفاءتها وتحسينها تجعلها أداة قيمة للعديد من المشكلات.
برنامج C لخوارزمية البحث A* في الذكاء الاصطناعي
#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)> برنامج C++ لخوارزمية البحث A* في الذكاء الاصطناعي
#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* في الذكاء الاصطناعي
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-star') هي خوارزمية اجتياز الرسم البياني وبحث المسار الشائعة والمستخدمة على نطاق واسع في الذكاء الاصطناعي. عادةً ما يكون العثور على أقصر مسار بين عقدتين في الرسم البياني أو البيئة القائمة على الشبكة أمرًا شائعًا. تجمع الخوارزمية بين عناصر البحث الخاصة بـ Dijkstra وعناصر البحث الأفضل أولاً لاستكشاف مساحة البحث مع ضمان الأمثلية بكفاءة. هناك عدة عوامل تحدد مدى تعقيد خوارزمية البحث A*. حجم الرسم البياني (العقد والحواف): يؤثر عدد العقد والحواف في الرسم البياني بشكل كبير على تعقيد الخوارزمية. المزيد من العقد والحواف يعني المزيد من الخيارات الممكنة للاستكشاف، مما قد يزيد من وقت تنفيذ الخوارزمية.
دالة إرشادية: تستخدم A* دالة إرشادية (غالبًا ما يُشار إليها بـ h(n)) لتقدير التكلفة من العقدة الحالية إلى العقدة الوجهة. تؤثر دقة هذا الاستدلال بشكل كبير على كفاءة البحث A*. يمكن أن يساعد الاستدلال الجيد في توجيه البحث إلى الهدف بسرعة أكبر، في حين أن الاستدلال السيئ يمكن أن يؤدي إلى بحث غير ضروري.
ومع ذلك، من الناحية العملية، غالبًا ما يكون أداء A* أفضل بكثير بسبب تأثير الوظيفة الإرشادية التي تساعد في توجيه الخوارزمية إلى مسارات واعدة. في حالة الاستدلال المصمم جيدًا، يكون عامل التفرع الفعال أصغر بكثير، مما يؤدي إلى نهج أسرع للحل الأمثل.