logo

Algorytm wyszukiwania A* w sztucznej inteligencji

Wprowadzenie do algorytmu wyszukiwania A* w sztucznej inteligencji

A* (wymawiane „gwiazda A”) to potężny algorytm przechodzenia przez graf i odnajdywania ścieżki, szeroko stosowany w sztucznej inteligencji i informatyce. Służy głównie do znalezienia najkrótszej ścieżki między dwoma węzłami na wykresie, biorąc pod uwagę szacunkowy koszt dotarcia z bieżącego węzła do węzła docelowego. Główną zaletą algorytmu jest jego zdolność do zapewnienia optymalnej ścieżki poprzez eksplorację wykresu w bardziej świadomy sposób w porównaniu z tradycyjnymi algorytmami wyszukiwania, takimi jak algorytm Dijkstry.

Algorytm A* łączy w sobie zalety dwóch innych algorytmów wyszukiwania: algorytmu Dijkstry i Greedy Best-First Search. Podobnie jak algorytm Dijkstry, A* zapewnia, że ​​znaleziona ścieżka jest tak krótka, jak to możliwe, ale robi to bardziej efektywnie, kierując wyszukiwanie za pomocą heurystyki podobnej do Greedy Best-First Search. Funkcja heurystyczna, oznaczona h(n), szacuje koszt dotarcia z dowolnego węzła n do węzła docelowego.

Główną ideą A* jest ocena każdego węzła na podstawie dwóch parametrów:

rhel kontra centos
    g(n):rzeczywisty koszt dotarcia z węzła początkowego do węzła n. Reprezentuje sumę kosztów węzła n wychodzących krawędzi.h(n):Koszt heurystyczny (znany również jako „koszt szacunkowy”) od węzła n do węzła docelowego n. Ta funkcja heurystyczna specyficzna dla problemu musi być akceptowalna, co oznacza, że ​​nigdy nie zawyża rzeczywistego kosztu osiągnięcia celu. Funkcja oceny węzła n jest zdefiniowana jako f(n) = g(n) h(n).

Algorytm A* wybiera węzły do ​​eksploracji w oparciu o najniższą wartość f(n), preferując węzły o najniższym szacunkowym koszcie całkowitym, aby osiągnąć cel. Algorytm A* działa:

  1. Utwórz otwartą listę znalezionych, ale nie zbadanych węzłów.
  2. Utwórz zamkniętą listę zawierającą już zbadane węzły.
  3. Dodaj węzeł początkowy do otwartej listy z początkową wartością g
  4. Powtarzaj poniższe kroki, aż otwarta lista będzie pusta lub dotrzesz do węzła docelowego:
    1. Znajdź węzeł z najmniejszą wartością f (tj. węzeł z mniejszym g(n) h(n)) na otwartej liście.
    2. Przenieś wybrany węzeł z listy otwartej na listę zamkniętą.
    3. Utwórz wszystkich prawidłowych potomków wybranego węzła.
    4. Dla każdego następcy oblicz jego wartość g jako sumę wartości g bieżącego węzła i kosztu przejścia z bieżącego węzła do węzła następczego. Zaktualizuj wartość g modułu śledzącego, gdy zostanie znaleziona lepsza ścieżka.
    5. Jeśli obserwującego nie ma na otwartej liście, dodaj go do obliczonej wartości g i oblicz jego wartość h. Jeśli znajduje się już na otwartej liście, zaktualizuj jej wartość g, jeśli nowa ścieżka jest lepsza.
    6. Powtórz cykl. Algorytm A* kończy się, gdy osiągnięty zostanie węzeł docelowy lub gdy otwarta lista opróżni się, wskazując brak ścieżek od węzła początkowego do węzła docelowego. Algorytm wyszukiwania A* jest szeroko stosowany w różnych dziedzinach, takich jak robotyka, gry wideo, routing sieciowy i problemy projektowe, ponieważ jest wydajny i pozwala znaleźć optymalne ścieżki na grafach lub w sieciach.

Jednak wybór odpowiedniej i akceptowalnej funkcji heurystycznej jest niezbędny, aby algorytm działał poprawnie i zapewniał optymalne rozwiązanie.

Świadome algorytmy wyszukiwania

Historia algorytmu wyszukiwania A* w sztucznej inteligencji

Został opracowany przez Petera Harta, Nilsa Nilssona i Bertrama Raphaela w Instytucie Badawczym Stanford (obecnie SRI International) jako rozszerzenie algorytmu Dijkstry i innych algorytmów wyszukiwania tamtych czasów. A* została opublikowana po raz pierwszy w 1968 roku i szybko zyskała uznanie ze względu na swoje znaczenie i skuteczność w społecznościach zajmujących się sztuczną inteligencją i informatyką. Oto krótki przegląd najważniejszych kamieni milowych w historii algorytmu wyszukiwania A*:

    Wczesne algorytmy wyszukiwania:Przed opracowaniem A* istniały różne algorytmy wyszukiwania grafów, w tym wyszukiwanie w głąb (DFS) i wyszukiwanie wszerz (BFS). Chociaż algorytmy te pomogły w znalezieniu ścieżek, nie gwarantowały optymalności ani nie uwzględniały heurystyki do kierowania wyszukiwaniemAlgorytm Dijkstry:W 1959 roku holenderski informatyk Edsger W. Dijkstra wprowadził algorytm Dijkstry, który znajdował najkrótszą ścieżkę na grafie ważonym z nieujemnymi wagami krawędzi. Algorytm Dijkstry był skuteczny, ale ze względu na swoją wyczerpującą naturę miał ograniczenia, gdy był używany na większych wykresach lubŚwiadome wyszukiwanie:Algorytmy wyszukiwania oparte na wiedzy (znane również jako wyszukiwanie heurystyczne) zostały opracowane w celu uwzględnienia informacji heurystycznych, takich jak szacunkowe koszty, w celu skutecznego kierowania procesem wyszukiwania. Jednym z takich algorytmów było zachłanne wyszukiwanie Best-First, ale nie gwarantowało ono optymalności w znajdowaniu najkrótszej ścieżki.A* rozwój:W 1968 roku Peter Hart, Nils Nilsson i Bertram Raphael wprowadzili algorytm A* będący połączeniem algorytmu Dijkstry i metody Greedy Best-First Search. A* użył funkcji heurystycznej, aby oszacować koszt od bieżącego węzła do węzła docelowego, łącząc go z rzeczywistym kosztem dotarcia do bieżącego węzła. Pozwoliło to A* na bardziej świadomą eksplorację grafu, unikając niepotrzebnych ścieżek i gwarantując optymalne rozwiązanie.Sprawiedliwość i doskonałość:Autorzy A* wykazali, że algorytm jest doskonały (zawsze znajduje rozwiązanie, jeśli takie istnieje) i optymalny (znajdzie najkrótszą ścieżkę) w określonych warunkach.Powszechne przyjęcie i postęp:A* szybko zyskał popularność w społecznościach zajmujących się sztuczną inteligencją i IT ze względu na swoją wydajność, a badacze i programiści rozszerzyli i zastosowali algorytm A* w różnych dziedzinach, w tym robotyce, grach wideo, inżynierii i routingu sieciowym. Na przestrzeni lat zaproponowano kilka odmian i optymalizacji algorytmu A*, np. przyrostowy A* i równoległy A*. Obecnie algorytm wyszukiwania A* jest nadal podstawowym i szeroko stosowanym algorytmem w sztucznej inteligencji i przeglądaniu grafów. Nadal odgrywa zasadniczą rolę w różnych zastosowaniach i dziedzinach badawczych. Jego wpływ na sztuczną inteligencję oraz wkład w problemy związane ze znajdowaniem ścieżki i optymalizacją uczyniły z niego podstawowy algorytm w badaniach nad inteligentnymi systemami.

Jak działa algorytm wyszukiwania A* w sztucznej inteligencji?

Algorytm wyszukiwania A* (wymawiane jako „litera A”) jest popularnym i szeroko stosowanym algorytmem przeglądania grafów w sztucznej inteligencji i informatyce. Służy do znalezienia najkrótszej ścieżki od węzła początkowego do węzła docelowego na grafie ważonym. A* to świadomy algorytm wyszukiwania, który wykorzystuje heurystykę do skutecznego prowadzenia wyszukiwania. Algorytm wyszukiwania A* działa w następujący sposób:

Algorytm rozpoczyna się od kolejki priorytetowej, w której przechowywane są węzły do ​​eksploracji. Tworzy także dwie struktury danych g(n): koszt najkrótszej jak dotąd ścieżki od węzła początkowego do węzła n oraz h(n), szacowany koszt (heurystyczny) od węzła n do węzła docelowego. Często jest to rozsądna heurystyka, co oznacza, że ​​nigdy nie zawyża rzeczywistego kosztu osiągnięcia celu. Umieść początkowy węzeł w kolejce priorytetowej i ustaw jego g(n) na 0. Jeśli kolejka priorytetowa nie jest pusta, usuń węzeł z najniższym f(n) z kolejki priorytetowej. f(n) = g(n) godz(n). Jeżeli usunięty węzeł jest węzłem docelowym, algorytm kończy się i zostaje znaleziona ścieżka. W przeciwnym razie rozwiń węzeł i utwórz jego sąsiadów. Dla każdego węzła sąsiedniego oblicz jego początkową wartość g(n), która jest sumą wartości g bieżącego węzła i kosztu przejścia z bieżącego węzła do węzła sąsiedniego. Jeśli sąsiedni węzeł nie ma kolejności priorytetów lub pierwotna wartość g(n) jest mniejsza niż jego bieżąca wartość g, zaktualizuj jego wartość g i ustaw jego węzeł nadrzędny na bieżący węzeł. Oblicz wartość f(n) z sąsiedniego węzła i dodaj ją do kolejki priorytetowej.

Jeśli cykl zakończy się bez znalezienia węzła docelowego, graf nie ma ścieżki od początku do końca. Kluczem do efektywności A* jest wykorzystanie funkcji heurystycznej h(n), która pozwala oszacować pozostały koszt osiągnięcia celu dowolnego węzła. Łącząc rzeczywisty koszt g (n) z kosztem heurystycznym h (n), algorytm skutecznie bada obiecujące ścieżki, nadając priorytet węzłom, które prawdopodobnie doprowadzą do najkrótszej ścieżki. Należy zauważyć, że skuteczność algorytmu A* w dużym stopniu zależy od wyboru funkcji heurystycznej. Akceptowalne heurystyki zapewniają, że algorytm zawsze znajduje najkrótszą ścieżkę, ale bardziej świadome i dokładne heurystyki mogą prowadzić do szybszej zbieżności i zmniejszenia przestrzeni poszukiwań.

Zalety algorytmu wyszukiwania A* w sztucznej inteligencji

Algorytm wyszukiwania A* oferuje kilka zalet w scenariuszach sztucznej inteligencji i rozwiązywania problemów:

    Optymalne rozwiązanie:A* zapewnia znalezienie optymalnej (najkrótszej) ścieżki od węzła początkowego do węzła docelowego na grafie ważonym, biorąc pod uwagę akceptowalną funkcję heurystyczną. Ta optymalność jest zdecydowaną zaletą w wielu zastosowaniach, w których istotne jest znalezienie najkrótszej ścieżki.Kompletność:Jeśli rozwiązanie istnieje, A* je znajdzie, pod warunkiem, że graf nie ma nieskończonego kosztu. Ta właściwość kompletności gwarantuje, że A* może skorzystać z rozwiązania, jeśli ono istnieje.Efektywność:A* jest skuteczny, jeśli używana jest wydajna i akceptowalna funkcja heurystyczna. Heurystyki kierują wyszukiwaniem do celu, koncentrując się na obiecujących ścieżkach i unikając niepotrzebnej eksploracji, dzięki czemu A* jest bardziej wydajny niż nieświadome algorytmy wyszukiwania, takie jak przeszukiwanie wszerz lub przeszukiwanie w głąb.Wszechstronność:A* ma szerokie zastosowanie w różnych obszarach problemowych, w tym w znajdowaniu drogi, planowaniu tras, robotyce, tworzeniu gier i nie tylko. A* można wykorzystać do skutecznego znalezienia optymalnych rozwiązań, o ile można zdefiniować znaczącą heurystykę.Zoptymalizowane wyszukiwanie:A* utrzymuje kolejność priorytetów, aby wybrać węzły z mniejszą wartością f(n) (g(n) i h(n)) do rozwinięcia. Dzięki temu może najpierw eksplorować obiecujące ścieżki, co zmniejsza przestrzeń poszukiwań i prowadzi do szybszej konwergencji.Wydajność pamięci:W przeciwieństwie do niektórych innych algorytmów wyszukiwania, takich jak przeszukiwanie wszerz, algorytm A* przechowuje tylko ograniczoną liczbę węzłów w kolejce priorytetowej, co sprawia, że ​​jest wydajny pod względem pamięci, zwłaszcza w przypadku dużych grafów.Przestrajalna heurystyka:Wydajność A* można dostroić, wybierając różne funkcje heurystyczne. Bardziej wykształcona heurystyka może prowadzić do szybszej zbieżności i mniej rozbudowanych węzłów.Szeroko zbadane:A* to algorytm o ugruntowanej pozycji, będący efektem dziesięcioleci badań i zastosowań praktycznych. Opracowano wiele optymalizacji i odmian, dzięki czemu jest to niezawodne i dobrze rozumiane narzędzie do rozwiązywania problemów.Wyszukiwarka internetowa:A* można wykorzystać do internetowego wyszukiwania ścieżek, gdzie algorytm stale aktualizuje ścieżkę w zależności od zmian w środowisku lub pojawienia się nowych. Umożliwia podejmowanie decyzji w czasie rzeczywistym w dynamicznych scenariuszach.

Wady algorytmu wyszukiwania A* w sztucznej inteligencji

Chociaż algorytm wyszukiwania A* (litera A) jest szeroko stosowaną i potężną techniką rozwiązywania problemów związanych ze znajdowaniem ścieżki AI i przechodzeniem po grafach, ma on wady i ograniczenia. Oto niektóre z głównych wad algorytmu wyszukiwania:

    Dokładność heurystyczna:Wydajność algorytmu A* zależy w dużym stopniu od dokładności funkcji heurystycznej użytej do oszacowania kosztu od bieżącego węzła do Jeśli heurystyka jest nie do zaakceptowania (nigdy nie przeszacowuje rzeczywistego kosztu) lub niespójna (spełnia nierówność trójkąta), A* może nie znaleźć optymalnej ścieżki lub może eksplorować więcej węzłów niż to konieczne, co wpływa na jego wydajność i dokładność.Zużycie pamięci:A* wymaga, aby wszystkie odwiedzane węzły były przechowywane w pamięci, aby śledzić odkryte ścieżki. Użycie pamięci może czasami stać się poważnym problemem, szczególnie w przypadku dużej przestrzeni wyszukiwania lub ograniczonych zasobów pamięci.Złożoność czasowa:Chociaż A* jest ogólnie wydajny, jego złożoność czasowa może stanowić problem w przypadku rozległych przestrzeni poszukiwań lub wykresów. W najgorszym przypadku znalezienie optymalnej ścieżki może zająć A* wykładniczo więcej czasu, jeśli heurystyka jest nieodpowiednia dla problemu.Wąskie gardło w miejscu docelowym:W określonych scenariuszach algorytm A* musi zbadać węzły daleko od miejsca docelowego, zanim ostatecznie dotrze do regionu docelowego. Problem ten pojawia się, gdy heurystyka musi skutecznie ukierunkować poszukiwania na cel już na wczesnym etapie.Wiązanie kosztów:A* napotyka trudności, gdy wiele węzłów ma tę samą wartość f (suma rzeczywistego kosztu i kosztu heurystycznego). Zastosowana strategia może mieć wpływ na optymalność i efektywność odkrytej ścieżki. Jeśli nie zostanie poprawnie obsłużone, może to prowadzić do eksploracji niepotrzebnych węzłów i spowolnienia algorytmu.Złożoność w środowiskach dynamicznych:W dynamicznych środowiskach, w których koszt krawędzi lub węzłów może zmieniać się podczas wyszukiwania, A* może nie być odpowiedni, ponieważ nie dostosowuje się dobrze do takich zmian. Przeformułowanie od zera może być kosztowne obliczeniowo, dlatego algorytmy D* (Dynamic A*) zostały zaprojektowane, aby rozwiązać ten problemDoskonałość w nieskończonej przestrzeni:A* może nie znaleźć rozwiązania w nieskończonej przestrzeni stanów. W takich przypadkach może działać w nieskończoność, eksplorując coraz większą liczbę węzłów bez znalezienia rozwiązania. Pomimo tych niedociągnięć, A* jest nadal solidnym i szeroko stosowanym algorytmem, ponieważ może skutecznie znajdować optymalne ścieżki w wielu praktycznych sytuacjach, jeśli funkcja heurystyczna jest dobrze zaprojektowana, a przestrzeń poszukiwań jest zarządzalna. Zaproponowano różne odmiany i warianty A*, aby złagodzić niektóre jego ograniczenia.

Zastosowania algorytmu wyszukiwania A* w sztucznej inteligencji

Algorytm wyszukiwania A* (litera A) jest szeroko stosowanym i niezawodnym algorytmem wyszukiwania ścieżek w sztucznej inteligencji i informatyce. Jego wydajność i optymalność sprawiają, że nadaje się do różnych zastosowań. Oto kilka typowych zastosowań algorytmu wyszukiwania A* w sztucznej inteligencji:

    Odnajdywanie ścieżki w grach:A* jest często używany w grach wideo do poruszania się postaci, nawigacji wroga przez sztuczną inteligencję i znajdowania najkrótszej ścieżki z jednej lokalizacji do drugiej na mapie gry. Jego zdolność do znajdowania optymalnej ścieżki na podstawie kosztów i heurystyki sprawia, że ​​idealnie nadaje się do zastosowań czasu rzeczywistego, takich jak gry.Robotyka i pojazdy autonomiczne:A* jest stosowany w robotyce i nawigacji pojazdów autonomicznych do planowania optymalnej trasy dla robotów dotarcia do celu, omijając przeszkody i biorąc pod uwagę koszty terenu. Ma to kluczowe znaczenie dla sprawnego i bezpiecznego poruszania się w środowisku naturalnym.Rozwiązywanie labiryntów:A* może skutecznie znaleźć najkrótszą ścieżkę w labiryncie, co czyni go przydatnym w wielu zastosowaniach związanych z rozwiązywaniem labiryntów, takich jak rozwiązywanie zagadek lub nawigacja po skomplikowanych strukturach.Planowanie tras i nawigacja:W systemach GPS i aplikacjach mapowych A* można wykorzystać do znalezienia optymalnej trasy między dwoma punktami na mapie, biorąc pod uwagę takie czynniki, jak odległość, warunki na drodze i topologia sieci drogowej.Rozwiązywanie zagadek:A* potrafi rozwiązywać różne łamigłówki oparte na diagramach, takie jak łamigłówki przesuwane, Sudoku i zadanie z 8 łamigłówkami. Alokacja zasobów: W scenariuszach, w których zasoby muszą zostać optymalnie przydzielone, A* może pomóc w znalezieniu najbardziej efektywnej ścieżki alokacji, minimalizując koszty i maksymalizując wydajność.Routing sieciowy:A* można używać w sieciach komputerowych do znajdowania najbardziej efektywnej trasy pakietów danych od węzła źródłowego do węzła docelowego.Przetwarzanie języka naturalnego (NLP):W niektórych zadaniach NLP A* może generować spójne i kontekstowe odpowiedzi, wyszukując możliwe sekwencje słów na podstawie ich prawdopodobieństwa i trafności.Planowanie ścieżki w robotyce:A* można wykorzystać do zaplanowania ścieżki robota z jednego punktu do drugiego, biorąc pod uwagę różne ograniczenia, takie jak omijanie przeszkód lub minimalizacja zużycia energii.Sztuczna inteligencja gry:A* służy także do podejmowania inteligentnych decyzji dotyczących postaci niezależnych (NPC), takich jak określanie najlepszego sposobu osiągnięcia celu lub koordynowanie ruchów w grze zespołowej.

To tylko kilka przykładów tego, jak algorytm wyszukiwania A* znajduje zastosowania w różnych obszarach sztucznej inteligencji. Jego elastyczność, wydajność i optymalizacja czynią go cennym narzędziem do rozwiązywania wielu problemów.

mapowanie w maszynopisie

Program C dla algorytmu wyszukiwania A* w sztucznej inteligencji

 #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)>

Program w C++ dla algorytmu wyszukiwania A* w sztucznej inteligencji

 #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>

Wyjaśnienie:

    Węzeł konstrukcyjny:Definiuje to strukturę węzła reprezentującą komórkę siatki. Zawiera współrzędne x i y węzła, koszt g od węzła początkowego do tego węzła, wartość heurystyczną h (szacowany koszt od tego węzła do węzła docelowego) oraz wskaźnik do
  1. węzeł początkowy ścieżki.
  2. Oblicz heurystykę:Ta funkcja oblicza heurystykę przy użyciu odległości euklidesowej pomiędzy węzłem a celem AStarSearch: Ta funkcja uruchamia algorytm wyszukiwania A*. Pobiera współrzędne początkowe i docelowe, siatkę i zwraca wektor par reprezentujących współrzędne najkrótszej ścieżki od początku do końca.Podstawowy:Główna funkcja programu pobiera od użytkownika siatki wejściowe, początek i współrzędne celu. Następnie wywołuje AStarSearch, aby znaleźć najkrótszą ścieżkę i wypisuje wynik. Węzeł struktury: definiuje strukturę węzła reprezentującą komórkę siatki. Zawiera współrzędne x i y węzła, koszt g od węzła początkowego do tego węzła, wartość heurystyczną h (szacowany koszt od tego węzła do węzła docelowego) oraz wskaźnik do węzła początkowego ścieżki.Oblicz heurystykę:Ta funkcja oblicza heurystykę przy użyciu odległości euklidesowej pomiędzy węzłem a celem AStarSearch: Ta funkcja uruchamia algorytm wyszukiwania A*. Pobiera współrzędne początkowe i docelowe, siatkę i zwraca wektor par reprezentujących współrzędne najkrótszej ścieżki od początku do końca.

Przykładowe wyjście

 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 

Program Java dla algorytmu wyszukiwania A* w sztucznej inteligencji

 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* Złożoność algorytmu wyszukiwania w sztucznej inteligencji

Algorytm wyszukiwania A* (wymawiane „gwiazda A”) jest popularnym i szeroko stosowanym algorytmem przeszukiwania grafów i wyszukiwania ścieżek w sztucznej inteligencji. Znalezienie najkrótszej ścieżki między dwoma węzłami na grafie lub w środowisku opartym na siatce jest zwykle powszechne. Algorytm łączy elementy wyszukiwania Dijkstry i zachłannego wyszukiwania „najpierw najlepiej”, aby eksplorować przestrzeń poszukiwań, jednocześnie skutecznie zapewniając optymalność. O złożoności algorytmu wyszukiwania A* decyduje kilka czynników. Rozmiar wykresu (węzły i krawędzie): liczba węzłów i krawędzi wykresu ma duży wpływ na złożoność algorytmu. Więcej węzłów i krawędzi oznacza więcej możliwych opcji do zbadania, co może wydłużyć czas wykonania algorytmu.

Funkcja heurystyczna: A* wykorzystuje funkcję heurystyczną (często oznaczaną jako h(n)) do oszacowania kosztu od bieżącego węzła do węzła docelowego. Precyzja tej heurystyki ma ogromny wpływ na efektywność wyszukiwania A*. Dobra heurystyka może pomóc szybciej poprowadzić poszukiwania do celu, podczas gdy zła heurystyka może prowadzić do niepotrzebnych poszukiwań.

    Struktury danych:A* utrzymuje dwie główne struktury danych: listę otwartą (kolejkę priorytetową) i listę zamkniętą (lub pulę odwiedzanych). Wydajność tych struktur danych wraz z wybraną implementacją (np. stertami binarnymi kolejki priorytetowej) wpływa na wydajność algorytmu.Współczynnik oddziału:Średnia liczba obserwujących dla każdego węzła wpływa na liczbę węzłów rozwiniętych podczas wyszukiwania. Wyższy współczynnik rozgałęzienia może prowadzić do większej eksploracji, która wzrastaOptymalność i kompletność:A* gwarantuje zarówno optymalność (znalezienie najkrótszej ścieżki), jak i kompletność (znalezienie istniejącego rozwiązania). Gwarancja ta wiąże się jednak z pewnym kompromisem pod względem złożoności obliczeniowej, ponieważ algorytm musi badać różne ścieżki w celu uzyskania optymalnej wydajności. Jeśli chodzi o złożoność czasową, wybrana funkcja heurystyczna wpływa na A* w najgorszym przypadku. Przy przyjętej heurystyce (która nigdy nie przecenia prawdziwego kosztu osiągnięcia celu), A* rozszerza najmniejszą liczbę węzłów spośród algorytmów optymalizacyjnych. Złożoność czasowa A * w najgorszym przypadku jest wykładnicza w najgorszym przypadku O(b ^ d), gdzie „b” to efektywny współczynnik rozgałęzienia (średnia liczba obserwujących na węzeł), a „d” to optymalny

Jednak w praktyce A* często działa znacznie lepiej ze względu na wpływ funkcji heurystycznej, która pomaga poprowadzić algorytm na obiecujące ścieżki. W przypadku dobrze zaprojektowanej heurystyki efektywny współczynnik rozgałęzienia jest znacznie mniejszy, co prowadzi do szybszego dojścia do optymalnego rozwiązania.