logo

A* Алгоритъм за търсене в изкуствения интелект

Въведение в алгоритъма за търсене A* в AI

A* (произнася се „А-звезда“) е мощен алгоритъм за обхождане на графика и намиране на пътя, широко използван в областта на изкуствения интелект и компютърните науки. Използва се главно за намиране на най-краткия път между два възела в графика, като се има предвид прогнозната цена за достигане от текущия възел до целевия възел. Основното предимство на алгоритъма е способността му да предоставя оптимален път чрез изследване на графиката по по-информиран начин в сравнение с традиционните алгоритми за търсене като алгоритъма на Дейкстра.

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

Основната идея на A* е да се оцени всеки възел въз основа на два параметъра:

пример за списък в java
    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 г. холандският компютърен учен Edsger W. Dijkstra въвежда алгоритъма на Dijkstra, който намира най-краткия път в претеглена графика с неотрицателни тегла на ръба. Алгоритъмът на Дейкстра беше ефективен, но поради изчерпателния си характер имаше ограничения, когато се използва върху по-големи графики илиИнформирано търсене:Алгоритмите за търсене, базирани на знания (известни също като евристично търсене), са разработени, за да включват евристична информация, като прогнозни разходи, за ефективно насочване на процеса на търсене. Greedy Best-First Search беше един такъв алгоритъм, но не гарантираше оптималност за намиране на най-краткия път.A* развитие:През 1968 г. Питър Харт, Нилс Нилсон и Бертрам Рафаел представят алгоритъма A* като комбинация от алгоритъма на Дейкстра и Greedy Best-First Search. A* използва евристична функция, за да оцени цената от текущия възел до целевия възел, като я комбинира с действителната цена за достигане на текущия възел. Това позволи на A* да изследва по-съзнателно графиката, избягвайки ненужните пътища и гарантирайки оптимално решение.Правда и съвършенство:Авторите на A* показаха, че алгоритъмът е перфектен (винаги намира решение, ако такова съществува) и оптимален (намира най-краткия път) при определени условия.Широко разпространено приемане и напредък:A* бързо придоби популярност в AI и IT общностите поради своята ефективност и изследователи и разработчици разшириха и приложиха алгоритъма 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):В някои NLP задачи A* може да генерира съгласувани и контекстуални отговори чрез търсене на възможни последователности от думи въз основа на тяхната вероятност и уместност.Планиране на пътя в роботиката:A* може да се използва за планиране на пътя на робот от една точка до друга, като се вземат предвид различни ограничения, като избягване на препятствия или минимизиране на консумацията на енергия.Игра AI:A* също се използва за вземане на интелигентни решения за герои, които не са играчи (NPC), като например определяне на най-добрия начин за постигане на цел или координиране на движенията в отборна игра.

Това са само няколко примера за това как алгоритъмът за търсене A* намира приложения в различни области на изкуствения интелект. Неговата гъвкавост, ефективност и оптимизация го правят ценен инструмент за много проблеми.

история на версиите на android

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. начален възел на пътя.
  2. Изчисляване на евристика:Тази функция изчислява евристика, използвайки евклидовото разстояние между възел и целта 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* (произнася се „А-звезда“) е популярен и широко използван алгоритъм за обхождане на графика и търсене на път в изкуствения интелект. Намирането на най-краткия път между два възела в среда, базирана на графика или мрежа, обикновено е обичайно. Алгоритъмът съчетава елементите за търсене на Dijkstra и алчните най-добри първи елементи за изследване на пространството за търсене, като същевременно гарантира оптималност ефективно. Няколко фактора определят сложността на алгоритъма за търсене A*. Размер на графиката (възли и ръбове): Броят на възлите и ръбовете на графиката значително влияе върху сложността на алгоритъма. Повече възли и ръбове означават повече възможни опции за изследване, което може да увеличи времето за изпълнение на алгоритъма.

Евристична функция: A* използва евристична функция (често означавана h(n)), за да оцени цената от текущия възел до целевия възел. Прецизността на тази евристика значително влияе върху ефективността на търсенето A*. Добрата евристика може да помогне за по-бързото насочване на търсенето към цел, докато лошата евристика може да доведе до ненужно търсене.

    Структури на данни:A* поддържа две основни структури на данни: отворен списък (приоритетна опашка) и затворен списък (или посетен пул). Ефективността на тези структури от данни, заедно с избраното имплементиране (напр. двоични купчини на приоритетна опашка), влияе върху производителността на алгоритъма.Разклонителен фактор:Средният брой последователи за всеки възел влияе върху броя възли, разширени по време на търсенето. По-високият коефициент на разклоняване може да доведе до повече проучване, което се увеличаваОптималност и пълнота:A* гарантира както оптималност (намиране на най-краткия път), така и пълнота (намиране на решение, което съществува). Тази гаранция обаче идва с компромис по отношение на изчислителната сложност, тъй като алгоритъмът трябва да изследва различни пътища за оптимална производителност. По отношение на времевата сложност, избраната евристична функция засяга A* в най-лошия случай. С приета евристика (която никога не надценява истинската цена за постигане на целта), A* разширява най-малкото възли сред оптимизационните алгоритми. Времевата сложност на A * в най-лошия случай е експоненциална в най-лошия случай O(b ^ d), където „b“ е ефективният коефициент на разклоняване (среден брой последователи на възел), а „d“ е оптималният

На практика обаче A* често се представя значително по-добре поради влиянието на евристична функция, която помага за насочването на алгоритъма към обещаващи пътища. В случай на добре проектирана евристика, ефективният фактор на разклоняване е много по-малък, което води до по-бърз подход към оптималното решение.