Вступ до алгоритму пошуку A* в AI

A* (вимовляється як «А-зірка») — це потужний алгоритм обходу графів і пошуку шляхів, який широко використовується в галузі штучного інтелекту та інформатики. Він в основному використовується для пошуку найкоротшого шляху між двома вузлами в графі, враховуючи приблизну вартість переходу від поточного вузла до вузла призначення. Основною перевагою алгоритму є його здатність забезпечувати оптимальний шлях шляхом дослідження графа більш поінформованим способом порівняно з традиційними алгоритмами пошуку, такими як алгоритм Дейкстри.

Алгоритм A* поєднує в собі переваги двох інших алгоритмів пошуку: алгоритму Дейкстри та Greedy Best-First Search. Подібно до алгоритму Дейкстри, A* гарантує, що знайдений шлях буде якомога коротшим, але робить це ефективніше, спрямовуючи пошук за допомогою евристики, схожої на жадібний пошук найкращого першого. Евристична функція, позначена h(n), оцінює вартість переходу від будь-якого даного вузла n до вузла призначення.

Основна ідея A* полягає в тому, щоб оцінити кожен вузол на основі двох параметрів:

які місяці в Q3

g(n):фактична вартість переходу від початкового вузла до вузла n. Він являє собою суму вартості вузла n вихідних ребер.h(n):Евристична вартість (також відома як «вартість оцінки») від вузла n до вузла призначення n. Ця евристична функція для конкретної проблеми має бути прийнятною, тобто вона ніколи не переоцінює фактичні витрати на досягнення мети. Функція оцінки вузла n визначається як f(n) = g(n) h(n).

Алгоритм A* вибирає вузли для дослідження на основі найнижчого значення f(n), віддаючи перевагу вузлам із найменшою оціночною сумарною вартістю для досягнення мети. Алгоритм A* працює:

1. Створіть відкритий список знайдених, але не досліджених вузлів.
2. Створіть закритий список для зберігання вже досліджених вузлів.
3. Додайте початковий вузол до відкритого списку з початковим значенням g
4. Повторюйте наступні кроки, доки відкритий список не стане порожнім або ви досягнете цільового вузла:
   1. Знайдіть у відкритому списку вузол із найменшим значенням f (тобто вузол із меншим g(n) h(n)).
   2. Перемістити вибраний вузол із відкритого списку до закритого.
   3. Створіть усіх дійсних нащадків вибраного вузла.
   4. Для кожного наступника обчисліть його значення g як суму значення g поточного вузла та вартості переходу від поточного вузла до наступного вузла. Оновіть g-значення трекера, коли знайдено кращий шлях.
   5. Якщо підписника немає у відкритому списку, додайте його з обчисленим g-значенням і обчисліть його h-значення. Якщо він уже є у відкритому списку, оновіть його значення g, якщо новий шлях кращий.
   6. Повторіть цикл. Алгоритм A* припиняє роботу, коли досягається цільовий вузол або коли відкритий список спорожняється, вказуючи на відсутність шляхів від початкового вузла до цільового вузла. Алгоритм пошуку A* широко використовується в різних сферах, таких як робототехніка, відеоігри, мережева маршрутизація та проблеми проектування, оскільки він ефективний і може знаходити оптимальні шляхи на графіках або мережах.

Однак вибір відповідної та прийнятної евристичної функції є важливим, щоб алгоритм працював правильно та забезпечував оптимальне рішення.

Історія алгоритму пошуку A* в системі штучного інтелекту

Він був розроблений Пітером Хартом, Нільсом Нільссоном і Бертрамом Рафаелем у Стенфордському дослідницькому інституті (тепер SRI International) як розширення алгоритму Дейкстри та інших пошукових алгоритмів того часу. A* був вперше опублікований у 1968 році та швидко отримав визнання за свою важливість і ефективність у спільнотах штучного інтелекту та інформатики. Ось короткий огляд найважливіших віх в історії пошукового алгоритму A*:

Алгоритми раннього пошуку:До розробки A* існували різні алгоритми пошуку графів, включаючи пошук у глибину (DFS) і пошук у ширину (BFS). Хоча ці алгоритми допомагали знаходити шляхи, вони не гарантували оптимальність і не враховували евристику для керування пошукомАлгоритм Дейкстри:У 1959 році голландський комп’ютерний вчений Едсгер В. Дейкстра представив алгоритм Дейкстри, який знаходив найкоротший шлях у зваженому графі з невід’ємними вагами ребер. Алгоритм Дейкстри був ефективним, але через його вичерпний характер він мав обмеження при використанні на великих графіках абоІнформований пошук:Алгоритми пошуку на основі знань (також відомі як евристичний пошук) були розроблені для включення евристичної інформації, такої як оцінені витрати, для ефективного керування процесом пошуку. Одним із таких алгоритмів був Greedy Best-First Search, але він не гарантував оптимальності для пошуку найкоротшого шляху.A* розвиток:У 1968 році Пітер Харт, Нільс Нільссон і Бертрам Рафаель представили алгоритм A* як комбінацію алгоритму Дейкстри та Жадібного пошуку найкращого першого. A* використовував евристичну функцію, щоб оцінити вартість від поточного вузла до вузла призначення, об’єднавши її з фактичною вартістю досягнення поточного вузла. Це дозволило A* більш усвідомлено досліджувати графік, уникаючи непотрібних шляхів і гарантуючи оптимальне рішення.Праведність і досконалість:Автори A* показали, що алгоритм ідеальний (завжди знаходить рішення, якщо воно існує) і оптимальний (знаходить найкоротший шлях) за певних умов.Широке впровадження та прогрес:A* швидко набув популярності в AI та IT-спільнотах завдяки своїй ефективності. Дослідники та розробники розширили та застосували алгоритм A* до різних галузей, включаючи робототехніку, відеоігри, інженерію та мережеву маршрутизацію. Протягом багатьох років було запропоновано декілька варіацій і оптимізацій алгоритму A*, наприклад Інкрементний A* і Паралельний A*. Сьогодні алгоритм пошуку A* все ще залишається фундаментальним і широко використовуваним алгоритмом у штучному інтелекті та обході графів. Він продовжує відігравати важливу роль у різних сферах застосування та досліджень. Його вплив на штучний інтелект і його внесок у пошук шляхів і проблеми оптимізації зробили його наріжним алгоритмом у дослідженні інтелектуальних систем.

Як працює алгоритм пошуку A* у системі штучного інтелекту?

Алгоритм пошуку A* (вимовляється як «літера A») — це популярний і широко використовуваний алгоритм обходу графів у штучному інтелекті та інформатиці. Він використовується для пошуку найкоротшого шляху від початкового вузла до вузла призначення у зваженому графі. A* — це обґрунтований алгоритм пошуку, який використовує евристику для ефективного керування пошуком. Алгоритм пошуку A* працює наступним чином:

Алгоритм починається з пріоритетної черги для зберігання вузлів, які потрібно дослідити. Він також створює дві структури даних g(n): вартість найкоротшого шляху від початкового вузла до вузла n і h(n), оцінену вартість (евристична) від вузла n до вузла призначення. Часто це розумна евристика, тобто вона ніколи не переоцінює фактичну вартість досягнення мети. Помістіть початковий вузол у чергу пріоритетів і встановіть його g(n) на 0. Якщо черга пріоритетів не пуста, видаліть вузол із найнижчим f(n) із черги пріоритетів. f(n) = g(n) h(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* зберігає порядок пріоритетів для вибору вузлів із меншим значенням f(n) (g(n) і h(n)) для розширення. Це дозволяє спочатку досліджувати багатообіцяючі шляхи, що зменшує простір пошуку та призводить до швидшої конвергенції.Ефективність пам'яті:На відміну від деяких інших алгоритмів пошуку, таких як пошук у ширину, A* зберігає лише обмежену кількість вузлів у пріоритетній черзі, що робить його ефективним з використанням пам’яті, особливо для великих графів.Настроювана евристика:Продуктивність A* можна налаштувати шляхом вибору різних евристичних функцій. Більш освічена евристика може призвести до швидшої конвергенції та менш розширених вузлів.Широко досліджено:A* — це добре налагоджений алгоритм із десятиліттями досліджень і практичних застосувань. Було розроблено багато оптимізацій і варіацій, що робить його надійним і добре зрозумілим інструментом усунення несправностей.Пошук в Інтернеті:A* можна використовувати для пошуку шляху в Інтернеті, де алгоритм постійно оновлює шлях відповідно до змін у середовищі або появи нових. Це дозволяє приймати рішення в реальному часі в динамічних сценаріях.

Недоліки алгоритму пошуку A* в системі штучного інтелекту

Незважаючи на те, що алгоритм пошуку A* (літера A) є широко використовуваною та потужною технікою для розв’язання проблем ШІ та обходу графів, він має недоліки та обмеження. Ось деякі з основних недоліків алгоритму пошуку:

Евристична точність:Продуктивність алгоритму A* значною мірою залежить від точності евристичної функції, яка використовується для оцінки вартості від поточного вузла до вузла. Якщо евристика є неприйнятною (ніколи не переоцінює фактичну вартість) або непослідовною (задовольняє нерівність трикутника), A* може не знайти оптимальний шлях або може досліджувати більше вузлів, ніж необхідно, що впливає на його ефективність і точність.Використання пам'яті:A* вимагає, щоб усі відвідані вузли зберігалися в пам’яті для відстеження досліджених шляхів. Використання пам’яті іноді може стати серйозною проблемою, особливо коли маєте справу з великим простором для пошуку або обмеженими ресурсами пам’яті.Часова складність:Хоча A* загалом ефективний, його часова складність може бути проблемою для великих пошукових просторів або графіків. У гіршому випадку A* може знадобитися експоненціально довше, щоб знайти оптимальний шлях, якщо евристика не підходить для проблеми.Вузьке місце в пункті призначення:У конкретних сценаріях алгоритм A* має досліджувати вузли, розташовані далеко від місця призначення, перш ніж остаточно досягти регіону призначення. Ця проблема виникає, коли евристика потребує ефективного спрямування пошуку до мети.Прив'язка вартості:A* стикається з труднощами, коли кілька вузлів мають однакове f-значення (суму фактичної вартості та евристичної вартості). Використана стратегія може вплинути на оптимальність і ефективність виявленого шляху. Якщо не поводитися належним чином, це може призвести до дослідження непотрібних вузлів і сповільнити роботу алгоритму.Складність у динамічному середовищі:У динамічних середовищах, де вартість ребер або вузлів може змінюватися під час пошуку, A* може бути непридатним, оскільки він погано адаптується до таких змін. Переформулювання з нуля може бути дорогим з обчислювальної точки зору, і алгоритми D* (Dynamic A*) були розроблені для вирішення цієї проблеми.Досконалість у нескінченному просторі:A* може не знайти рішення в нескінченному просторі станів. У таких випадках він може працювати нескінченно, досліджуючи постійно зростаючу кількість вузлів, не знаходячи рішення. Незважаючи на ці недоліки, A* все ще є надійним і широко використовуваним алгоритмом, оскільки він може ефективно знаходити оптимальні шляхи в багатьох практичних ситуаціях, якщо евристична функція добре розроблена, а простір пошуку є керованим. Були запропоновані різні варіації та варіанти A*, щоб пом’якшити деякі його обмеження.

Застосування алгоритму пошуку A* в штучному інтелекті

Алгоритм пошуку A* (літера A) є широко використовуваним і надійним алгоритмом пошуку шляхів у штучному інтелекті та інформатиці. Його ефективність і оптимальність роблять його придатним для різних застосувань. Ось кілька типових застосувань алгоритму пошуку A* в штучному інтелекті:

Пошук шляху в іграх:A* часто використовується у відеоіграх для переміщення персонажів, навігації ворогів ШІ та пошуку найкоротшого шляху від одного місця до іншого на карті гри. Його здатність знаходити оптимальний шлях на основі вартості та евристики робить його ідеальним для програм реального часу, таких як ігри.Робототехніка та автономні транспортні засоби:A* використовується в робототехніці та автономній навігації транспортних засобів, щоб спланувати оптимальний маршрут для досягнення роботів пункту призначення, уникаючи перешкод і враховуючи витрати на місцевість. Це вкрай важливо для ефективного та безпечного пересування в природному середовищі.Розгадування лабіринту:A* може ефективно знаходити найкоротший шлях у лабіринті, що робить його цінним у багатьох програмах, пов’язаних із вирішенням лабіринтів, наприклад розв’язуванням головоломок або навігацією складними структурами.Планування маршруту та навігація:У системах GPS і картографічних програмах A* можна використовувати для пошуку оптимального маршруту між двома точками на карті з урахуванням таких факторів, як відстань, умови руху та топологія дорожньої мережі.Розгадування головоломок:A* може розв’язувати різні головоломки з діаграмами, такі як розсувні головоломки, судоку та завдання з 8 головоломок. Розподіл ресурсів: у сценаріях, коли ресурси повинні бути розподілені оптимально, A* може допомогти знайти найефективніший шлях розподілу, мінімізуючи витрати та максимізуючи ефективність.Маршрутизація мережі:A* можна використовувати в комп’ютерних мережах для пошуку найбільш ефективного маршруту для пакетів даних від джерела до вузла призначення.Обробка природної мови (NLP):У деяких завданнях НЛП А* може генерувати зв’язні та контекстні відповіді, шукаючи можливі послідовності слів на основі їх вірогідності та релевантності.Планування шляху в робототехніці:A* можна використовувати для планування шляху робота від однієї точки до іншої з урахуванням різноманітних обмежень, таких як уникнення перешкод або мінімізація споживання енергії.ШІ гри:A* також використовується для прийняття розумних рішень щодо неігрових персонажів (NPC), наприклад для визначення найкращого способу досягнення мети або координації рухів у командній грі.

Це лише кілька прикладів того, як алгоритм пошуку 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 &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)>

Програма 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>&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>

Пояснення:

Вузол структури:Це визначає структуру вузла, яка представляє комірку сітки. Він містить координати x і y вузла, вартість g від початкового вузла до цього вузла, евристичне значення h (розрахункова вартість від цього вузла до вузла призначення) і покажчик на
1. початковий вузол шляху.
Розрахувати евристику:Ця функція обчислює евристику, використовуючи евклідову відстань між вузлом і цільовою AStarSearch: Ця функція запускає алгоритм пошуку A*. Він приймає координати початку та пункту призначення, сітку та повертає вектор пар, що представляють координати найкоротшого шляху від початку до кінця.Основний:Основна функція програми отримує від користувача координати вхідної сітки, вихідної точки та мети. Потім він викликає AStarSearch, щоб знайти найкоротший шлях і друкує результат. Вузол структури: це визначає структуру вузла, яка представляє комірку сітки. Він містить координати x і y вузла, вартість g від початкового вузла до цього вузла, евристичне значення h (розрахункова вартість від цього вузла до вузла призначення) і покажчик на початковий вузол шляху.Розрахувати евристику:Ця функція обчислює евристику, використовуючи евклідову відстань між вузлом і цільовою AStarSearch: Ця функція запускає алгоритм пошуку A*. Він приймає координати початку та пункту призначення, сітку та повертає вектор пар, що представляють координати найкоротшого шляху від початку до кінця.

Зразок результату

 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 

Програма на Java для алгоритму пошуку 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 &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* Складність алгоритму пошуку в штучному інтелекті

Алгоритм пошуку A* (вимовляється як «А-зірка») — це популярний і широко використовуваний алгоритм обходу графів і пошуку шляху в системі штучного інтелекту. Знаходження найкоротшого шляху між двома вузлами в середовищі на основі графіка або сітки зазвичай є звичайним. Алгоритм поєднує елементи пошуку Дейкстри та жадібні елементи пошуку «найкращий перший», щоб досліджувати простір пошуку, одночасно забезпечуючи ефективну оптимальність. Кілька факторів визначають складність алгоритму пошуку A*. Розмір графа (вузлів і ребер): кількість вузлів і ребер графа сильно впливає на складність алгоритму. Більше вузлів і ребер означає більше можливих варіантів для дослідження, що може збільшити час виконання алгоритму.

програма успадкування на python

Евристична функція: A* використовує евристичну функцію (часто позначається h(n)), щоб оцінити вартість від поточного вузла до вузла призначення. Точність цієї евристики значною мірою впливає на ефективність пошуку A*. Хороша евристика може допомогти швидше спрямувати пошук до мети, тоді як погана евристика може призвести до непотрібного пошуку.

Структури даних:A* підтримує дві основні структури даних: відкритий список (пріоритетна черга) і закритий список (або відвідуваний пул). Ефективність цих структур даних разом із обраною реалізацією (наприклад, двійкові купи пріоритетної черги) впливає на продуктивність алгоритму.Фактор відділення:Середня кількість підписників для кожного вузла впливає на кількість вузлів, розширених під час пошуку. Вищий коефіцієнт розгалуження може призвести до більшої кількості досліджень, що збільшуєтьсяОптимальність і повнота:A* гарантує як оптимальність (пошук найкоротшого шляху), так і повноту (пошук рішення, яке існує). Однак ця гарантія має компроміс з точки зору обчислювальної складності, оскільки алгоритм повинен досліджувати різні шляхи для оптимальної продуктивності. Що стосується часової складності, обрана евристична функція впливає на A* в найгіршому випадку. Завдяки прийнятій евристиці (яка ніколи не переоцінює справжню вартість досягнення мети), A* розширює найменшу кількість вузлів серед алгоритмів оптимізації. Найгірша часова складність A * є експоненціальною в найгіршому випадку O(b ^ d), де 'b' — ефективний коефіцієнт розгалуження (середня кількість послідовників на вузол), а 'd' — оптимальний

На практиці, однак, A* часто працює значно краще через вплив евристичної функції, яка допомагає скеровувати алгоритм перспективними шляхами. У випадку добре розробленої евристики ефективний коефіцієнт розгалуження значно менший, що призводить до швидшого наближення до оптимального рішення.