AI における情報に基づいた検索アルゴリズム

AI における A* 検索アルゴリズムの概要

A* (「A スター」と発音) は、人工知能とコンピューターサイエンスで広く使用されている強力なグラフトラバーサルおよび経路探索アルゴリズムです。これは主に、現在のノードから宛先ノードまでの推定コストを考慮して、グラフ内の 2 つのノード間の最短パスを見つけるために使用されます。このアルゴリズムの主な利点は、ダイクストラのアルゴリズムなどの従来の検索アルゴリズムと比較して、より情報に基づいた方法でグラフを探索することにより、最適なパスを提供できることです。

アルゴリズム A* は、他の 2 つの検索アルゴリズム、ダイクストラのアルゴリズムと Greedy Best-First Search の利点を組み合わせたものです。ダイクストラのアルゴリズムと同様に、A* は見つかったパスができるだけ短いことを保証しますが、Greedy Best-First Search と同様のヒューリスティックを通じて検索を指示することで、より効率的にパスを見つけます。 h(n) で示されるヒューリスティック関数は、任意のノード n から宛先ノードに到達するコストを推定します。

A* の主な考え方は、次の 2 つのパラメーターに基づいて各ノードを評価することです。

mysqlの一意のキー

おやすみなさい）：最初のノードからノード n までにかかる実際のコスト。これは、ノード n の発信エッジのコストの合計を表します。h(n):ノード n から宛先ノード n までのヒューリスティックコスト (「推定コスト」とも呼ばれる)。この問題固有のヒューリスティック関数は許容できるものでなければなりません。これは、目標を達成するための実際のコストを決して過大評価しないことを意味します。ノード n の評価関数は f(n) = g(n) h(n) として定義されます。

アルゴリズム A* は、f(n) の最小値に基づいて調査対象のノードを選択し、目標に到達するために推定総コストが最も低いノードを優先します。 A* アルゴリズムは次のように動作します。

見つかったが探索されていないノードのオープンリストを作成します。
すでに探索されたノードを保持する閉じたリストを作成します。
初期値 g を使用して、開始ノードを開いているリストに追加します。
開いているリストが空になるか、ターゲットノードに到達するまで、次の手順を繰り返します。
1. 開いたリストで最小の f 値を持つノード (つまり、マイナー g(n) h(n) を持つノード) を見つけます。
2. 選択したノードを開いたリストから閉じたリストに移動します。
3. 選択したノードの有効な子孫をすべて作成します。
4. 各後続ノードについて、現在のノードの g 値と現在のノードから後続ノードへの移動コストの合計として g 値を計算します。より適切なパスが見つかったら、トラッカーの g 値を更新します。
5. フォロワーが開いているリストにない場合は、計算された g 値を追加し、h 値を計算します。すでに開いているリストにある場合、新しいパスの方が優れている場合は、その g 値を更新します。
6. サイクルを繰り返します。アルゴリズム A* は、ターゲットノードに到達するか、開いているリストが空になり、開始ノードからターゲットノードへのパスがないことを示すときに終了します。 A* 検索アルゴリズムは効率的で、グラフやネットワーク内の最適なパスを見つけることができるため、ロボット工学、ビデオゲーム、ネットワークルーティング、設計問題などのさまざまな分野で広く使用されています。

ただし、アルゴリズムが正しく実行され、最適なソリューションが提供されるためには、適切で許容可能なヒューリスティック関数を選択することが不可欠です。

人工知能における A* 検索アルゴリズムの歴史

これは、スタンフォード研究所 (現在の SRI インターナショナル) の Peter Hart、Nils Nilsson、Bertram Raphael によって、ダイクストラのアルゴリズムや当時の他の検索アルゴリズムの拡張として開発されました。 A* は 1968 年に初めて出版され、人工知能とコンピューターサイエンスのコミュニティでその重要性と有効性がすぐに認識されました。以下に、検索アルゴリズム A* の歴史の中で最も重要なマイルストーンの概要を示します。

初期の検索アルゴリズム:A* が開発される前は、深さ優先検索 (DFS) や幅優先検索 (BFS) など、さまざまなグラフ検索アルゴリズムが存在していました。これらのアルゴリズムはパスの検索に役立ちましたが、最適性を保証したり、検索をガイドするためのヒューリスティックを考慮したりすることはありませんでした。ダイクストラのアルゴリズム:1959 年、オランダのコンピュータ科学者 Edsger W. Dijkstra は、非負のエッジ重みを持つ重み付きグラフで最短経路を見つけるダイクストラアルゴリズムを導入しました。ダイクストラのアルゴリズムは効率的でしたが、網羅的な性質のため、より大きなグラフやグラフで使用する場合には制限がありました。情報に基づいた検索:知識ベースの検索アルゴリズム (ヒューリスティック検索とも呼ばれます) は、推定コストなどのヒューリスティック情報を組み込んで、検索プロセスを効率的にガイドするために開発されています。 Greedy Best-First Search はそのようなアルゴリズムの 1 つでしたが、最短パスを見つけるための最適性は保証されませんでした。A* 開発:1968 年に、Peter Hart、Nils Nilsson、Bertram Raphael は、ダイクストラのアルゴリズムと Greedy Best-First Search を組み合わせた A* アルゴリズムを導入しました。 A* は、ヒューリスティック関数を使用して、現在のノードに到達する実際のコストと組み合わせることにより、現在のノードから宛先ノードまでのコストを推定しました。これにより、A* はより意識的にグラフを探索し、不必要なパスを回避し、最適な解決策を保証できるようになりました。正義と完全さ:A* の作成者は、アルゴリズムが特定の条件下で完全 (解が存在する場合は常に解を見つける) であり、最適 (最短経路を見つける) であることを示しました。広範な採用と進歩:A* は、その効率性により AI および IT コミュニティで急速に人気を博し、研究者や開発者は A* アルゴリズムをロボット工学、ビデオゲーム、エンジニアリング、ネットワークルーティングなどのさまざまな分野に拡張および適用してきました。 Incremental A* や Parallel A* など、A* アルゴリズムのいくつかのバリエーションと最適化が長年にわたって提案されてきました。現在でも、A* 検索アルゴリズムは、人工知能とグラフトラバーサルの基本的なアルゴリズムであり、広く使用されています。さまざまな用途や研究分野で重要な役割を果たし続けています。人工知能への影響と、経路探索と最適化問題への貢献により、インテリジェントシステム研究の基礎アルゴリズムとなっています。

A* 検索アルゴリズムは人工知能でどのように機能しますか?

A* (「文字 A」と発音) 検索アルゴリズムは、人工知能とコンピューターサイエンスで人気があり、広く使用されているグラフトラバーサルアルゴリズムです。これは、重み付きグラフ内の開始ノードから宛先ノードまでの最短パスを見つけるために使用されます。 A* は、ヒューリスティックを使用して効率的に検索をガイドする、情報に基づいた検索アルゴリズムです。検索アルゴリズム A* は次のように機能します。

このアルゴリズムは、探索対象のノードを格納するための優先キューから始まります。また、2 つのデータ構造 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* は Web ベースのパス検索に使用でき、環境の変化や新しいものの出現に応じてアルゴリズムが常にパスを更新します。これにより、動的なシナリオでのリアルタイムの意思決定が可能になります。

人工知能における A* 検索アルゴリズムの欠点

A* (文字 A) 検索アルゴリズムは、AI のパスファインディングやグラフ走査の問題を解決するために広く使用されている強力な手法ですが、欠点と制限があります。検索アルゴリズムの主な欠点をいくつか次に示します。

文字列をブール値の Java に変換

ヒューリスティック精度:A* アルゴリズムのパフォーマンスは、現在のノードからノードまでのコストを推定するために使用されるヒューリスティック関数の精度に大きく依存します。ヒューリスティックが受け入れられない場合 (実際のコストを決して過大評価しない)、または一貫性がない場合 (三角不等式を満たす場合)、A*最適なパスが見つからなかったり、必要以上に多くのノードを探索したりして、効率と精度に影響を与える可能性があります。メモリ使用量：A* では、探索されたパスを追跡するために、訪問したすべてのノードをメモリ内に保持する必要があります。特に十分な検索スペースや限られたメモリリソースを扱う場合、メモリ使用量が重大な問題になることがあります。時間計算量:A* は一般に効率的ですが、広大な検索空間やグラフでは時間の複雑さが問題になる可能性があります。最悪の場合、ヒューリスティックが問題に対して不適切な場合、A* が最適なパスを見つけるまでに指数関数的に長い時間がかかる可能性があります。目的地でのボトルネック:特定のシナリオでは、A* アルゴリズムは、最終的に宛先領域に到達する前に、宛先から遠く離れたノードを探索する必要があります。この問題は、ヒューリスティックが検索を効果的に早期に目標に向ける必要がある場合に発生します。コスト拘束:複数のノードが同じ f 値 (実際のコストとヒューリスティックコストの合計) を持つ場合、A* は困難に直面します。使用される戦略は、発見されたパスの最適性と効率に影響を与える可能性があります。正しく処理されないと、不要なノードが探索され、アルゴリズムの速度が低下する可能性があります。動的環境における複雑さ:エッジやノードのコストが検索中に変化する可能性がある動的環境では、A* はそのような変化にうまく適応できないため、適切ではない可能性があります。ゼロから再定式化すると計算コストが高くなる可能性があるため、D* (Dynamic A*) アルゴリズムはこれを解決するために設計されました。無限の空間における完璧さ:A* は無限の状態空間では解を見つけられない可能性があります。このような場合、解決策が見つからないまま、無限に実行され、増え続けるノードを探索する可能性があります。これらの欠点にもかかわらず、A* は依然として堅牢で広く使用されているアルゴリズムです。ヒューリスティック関数が適切に設計されており、検索空間が管理可能であれば、多くの実際的な状況で最適なパスを効果的に見つけることができるからです。 A* の制限の一部を軽減するために、A* のさまざまなバリエーションやバリアントが提案されています。

人工知能における A* 検索アルゴリズムの応用

検索アルゴリズム A* (文字 A) は、人工知能とコンピューターサイエンスで広く使用されている堅牢な経路探索アルゴリズムです。その効率性と最適性により、さまざまな用途に適しています。人工知能における A* 検索アルゴリズムの典型的な応用例をいくつか示します。

ゲームにおけるパスファインディング:A* は、ビデオゲームでキャラクターの移動、敵の AI ナビゲーション、ゲームマップ上のある場所から別の場所への最短経路を見つけるためによく使用されます。コストとヒューリスティックに基づいて最適なパスを見つける機能は、ゲームなどのリアルタイムアプリケーションに最適です。ロボット工学と自動運転車:A* は、障害物を回避し、地形コストを考慮して、ロボットが目的地に到達するための最適なルートを計画するために、ロボット工学や自律車両ナビゲーションで使用されます。これは、自然環境で効率的かつ安全に移動するために非常に重要です。迷路を解く:A* は迷路内の最短経路を効率的に見つけることができるため、パズルを解いたり、複雑な構造をナビゲートしたりするなど、多くの迷路解決アプリケーションで役立ちます。ルート計画とナビゲーション:GPS システムやマッピングアプリケーションでは、A* を使用して、距離、交通状況、道路ネットワークトポロジなどの要素を考慮して、地図上の 2 点間の最適なルートを見つけることができます。パズルを解く:A*は、スライドパズル、数独、8パズル問題など、さまざまな図形パズルを解くことができます。リソース割り当て: リソースを最適に割り当てる必要があるシナリオでは、A* は最も効率的な割り当てパスを見つけて、コストを最小限に抑え、効率を最大化するのに役立ちます。ネットワークルーティング:A* は、ソースノードから宛先ノードまでのデータパケットの最も効率的なルートを見つけるためにコンピュータネットワークで使用できます。自然言語処理 (NLP):一部の NLP タスクでは、A* は、可能性のある単語シーケンスをその可能性と関連性に基づいて検索することにより、一貫した文脈上の応答を生成できます。ロボット工学における経路計画:A* を使用すると、障害物の回避やエネルギー消費の最小化など、さまざまな制約を考慮して、ある地点から別の地点までのロボットの経路を計画できます。ゲーム AI:A* は、目的を達成するための最良の方法を決定したり、チームベースのゲームで動きを調整したりするなど、ノンプレイヤーキャラクター (NPC) に対してインテリジェントな意思決定を行うためにも使用されます。

これらは、A* 検索アルゴリズムが人工知能のさまざまな分野でアプリケーションを見つける方法のほんの一例です。その柔軟性、効率性、最適化により、多くの問題に対する貴重なツールとなります。

人工知能における A* 検索アルゴリズム用の C プログラム

 #include #include #define ROWS 5 #define COLS 5 // Define a structure for a grid cell typedef struct { int row, col; } Cell; // Define a structure for a node in the A* algorithm typedef struct { Cell position; int g, h, f; struct Node* parent; } Node; // Function to calculate the Manhattan distance between two cells int heuristic(Cell current, Cell goal) { return abs(current.row - goal.row) + abs(current.col - goal.col); } // Function to check if a cell is valid (within the grid and not an obstacle) int isValid(int row, int col, int grid[ROWS][COLS]) { return (row &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)>

人工知能における A* 検索アルゴリズム用の C++ プログラム

 #include #include #include using namespace std; struct Node { int x, y; // Coordinates of the node int g; // Cost from the start node to this node int h; // Heuristic value (estimated cost from this node to the goal node) Node* parent; // Parent node in the path Node (int x, int y): x(x), y(y), g(0), h(0), parent(nullptr) {} // Calculate the total cost (f = g + h) int f () const { return g + h; } }; // Heuristic function (Euclidean distance) int calculateHeuristic (int x, int y, int goals, int goal) { return static cast (sqrt (pow (goals - x, 2) + pow (goal - y, 2))); } // A* search algorithm vector<pair> AStarSearch (int startX, int startY, int goals, int goal, vector<vector>&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>

説明：

パスの開始ノード。

サンプル出力

 Enter the number of rows: 5 Enter the number of columns: 5 Enter the grid (0 for empty, 1 for obstacle): 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 Enter the start coordinates (x y): 0 0 Enter the goal coordinates (x y): 4 4

人工知能における A* 検索アルゴリズム用の Java プログラム

 import java. util.*; class Node { int x, y; // Coordinates of the node int g; // Cost from the start node to the current node int h; // Heuristic value (estimated cost from the current node to goal node) int f; // Total cost f = g + h Node parent; // Parent node in the path public Node (int x, int y) { this. g = x; this. f = y; this. Parent = null; } } public class AStarSearch { // Heuristic function (Manhattan distance) private static int heuristic (Node current, Node goal) { return Math. Abs (current.x - goal.x) + Math. Abs(current.y - goal.y); } // A* search algorithm public static List aStarSearch(int [][] grid, Node start, Node goal) { int rows = grid. Length; int cols = grid [0].length; // Add the start node to the open set opened.add(start); while (! openSet.isEmpty()) { // Get the node with the lowest f value from the open set Node current = openSet.poll(); // If the current node is the goal node, reconstruct the path and return it if (current == goal) { List path = new ArrayList(); while (current != null) { path.add(0, current); current = current.parent; } return path; } // Move the current node from the open set to the closed set closedSet.add(current); // Generate neighbors of the current node int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; for (int i = 0; i = 0 &amp;&amp; nx = 0 &amp;&amp; ny = neighbor.g) { // Skip this neighbor as it is already in the closed set with a lower or equal g value continue; } if (!openSet.contains(neighbor) || tentativeG <neighbor.g) { update the neighbor\'s values neighbor.g="tentativeG;" neighbor.h="heuristic(neighbor," goal); neighbor.f="neighbor.g" + neighbor.h; neighbor.parent="current;" if (!openset.contains(neighbor)) add neighbor to open set not already present openset.add(neighbor); } is empty and goal reached, there no path return null; public static void main(string[] args) int[][] grid="{" {0, 0, 0}, 1, 0} }; node start="new" node(0, 0); node(4, 4); list start, (path !="null)" system.out.println(\'path found:\'); for (node : path) system.out.println(\'(\' node.x \', \' node.y \')\'); else system.out.println(\'no found.\'); < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Node Class:</td> We start by defining a nodeclass representing each grid cell. Each node contains coordinates (x, y), an initial node cost (g), a heuristic value (h), a total cost (f = g h), and a reference to the parent node of the path. </tr><tr><td>Heuristicfunction:</td> The heuristic function calculates the Manhattan distance between a node and a destination The Manhattan distance is a heuristic used to estimate the cost from the current node to the destination node. </tr><tr><td>Search algorithm* function:</td> A Star Search is the primary implementation of the search algorithm A*. It takes a 2D grid, a start node, and a destination node as inputs and returns a list of nodes representing the path from the start to the destination node. </tr><tr><td>Priority Queue and Closed Set:</td> The algorithm uses a priority queue (open Set) to track thenodes to be explored. The queue is ordered by total cost f, so the node with the lowest f value is examined The algorithm also uses a set (closed set) to track the explored nodes. </tr><tr><td>The main loop of the algorithm:</td> The main loop of the A* algorithm repeats until there are no more nodes to explore in the open Set. In each iteration, the node f with the lowest total cost is removed from the opener, and its neighbors are created. </tr><tr><td>Creating neighbors:</td> The algorithm creates four neighbors (up, down, left, right) for each node and verifies that each neighbor is valid (within the network boundaries and not as an obstacle). If the neighbor is valid, it calculates the initial value g from the source node to that neighbor and the heuristic value h from that neighbor to the destination The total cost is then calculated as the sum of f, g, and h. </tr><tr><td>Node evaluation:</td> The algorithm checks whether the neighbor is already in the closed set and, if so, whether the initial cost g is greater than or equal to the existing cost of the neighbor If true, the neighbor is omitted. Otherwise, the neighbor values are updated and added to the open Set if it is not already there. </tr><tr><td>Pathreconstruction:</td> When the destination node is reached, the algorithm reconstructs the path from the start node to the destination node following the main links from the destination node back to the start node. The path is returned as a list of nodes </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Path found: (0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (4, 2) (4, 3) (4, 4) </pre> <h2>A* Search Algorithm Complexity in Artificial Intelligence</h2> <p>The A* (pronounced &apos;A-star&apos;) search algorithm is a popular and widely used graph traversal and path search algorithm in artificial intelligence. Finding the shortest path between two nodes in a graph or grid-based environment is usually common. The algorithm combines Dijkstra&apos;s and greedy best-first search elements to explore the search space while ensuring optimality efficiently. Several factors determine the complexity of the A* search algorithm. Graph size (nodes and edges): A graph&apos;s number of nodes and edges greatly affects the algorithm&apos;s complexity. More nodes and edges mean more possible options to explore, which can increase the execution time of the algorithm.</p> <p>Heuristic function: A* uses a heuristic function (often denoted h(n)) to estimate the cost from the current node to the destination node. The precision of this heuristic greatly affects the efficiency of the A* search. A good heuristic can help guide the search to a goal more quickly, while a bad heuristic can lead to unnecessary searching.</p> <ol class="points"> <tr><td>Data Structures:</td> A* maintains two maindata structures: an open list (priority queue) and a closed list (or visited pool). The efficiency of these data structures, along with the chosen implementation (e.g., priority queue binary heaps), affects the algorithm&apos;s performance. </tr><tr><td>Branch factor:</td> The average number of followers for each node affects the number of nodes expanded during the search. A higher branching factor can lead to more exploration, which increases </tr><tr><td>Optimality and completeness:</td> A* guarantees both optimality (finding the shortest path) and completeness (finding a solution that exists). However, this guarantee comes with a trade-off in terms of computational complexity, as the algorithm must explore different paths for optimal performance. Regarding time complexity, the chosen heuristic function affects A* in the worst case. With an accepted heuristic (which never overestimates the true cost of reaching the goal), A* expands the fewest nodes among the optimization algorithms. The worst-case time complexity of A * is exponential in the worst-case O(b ^ d), where &apos;b&apos; is the effective branching factor (average number of followers per node) and &apos;d&apos; is the optimal </tr></ol> <p>In practice, however, A* often performs significantly better due to the influence of a heuristic function that helps guide the algorithm to promising paths. In the case of a well-designed heuristic, the effective branching factor is much smaller, which leads to a faster approach to the optimal solution.</p> <hr></neighbor.g)>

A* 人工知能における検索アルゴリズムの複雑さ

A* (「A スター」と発音) 検索アルゴリズムは、人工知能で人気があり広く使用されているグラフトラバーサルおよびパス検索アルゴリズムです。グラフまたはグリッドベースの環境で 2 つのノード間の最短パスを見つけることは通常一般的です。このアルゴリズムは、ダイクストラ法と貪欲な最良優先探索要素を組み合わせて、最適性を効率的に確保しながら探索空間を探索します。 A* 検索アルゴリズムの複雑さは、いくつかの要因によって決まります。グラフサイズ (ノードとエッジ): グラフのノードとエッジの数は、アルゴリズムの複雑さに大きく影響します。ノードとエッジが増えると、探索できるオプションが増えることになり、アルゴリズムの実行時間が長くなる可能性があります。

ヒューリスティック関数: A* はヒューリスティック関数 (多くの場合 h(n) で示される) を使用して、現在のノードから宛先ノードまでのコストを推定します。このヒューリスティックの精度は、A* 検索の効率に大きく影響します。優れたヒューリスティックは、検索をより迅速に目標に導くのに役立ちますが、悪いヒューリスティックは不必要な検索につながる可能性があります。

データ構造:A* は、オープンリスト (優先キュー) とクローズドリスト (または訪問済みプール) の 2 つのメインデータ構造を維持します。これらのデータ構造の効率は、選択された実装 (優先キューのバイナリヒープなど) とともに、アルゴリズムのパフォーマンスに影響します。分岐係数:各ノードの平均フォロワー数は、検索中に展開されるノードの数に影響します。分岐係数が高くなると、より多くの探索が行われる可能性があり、最適性と完全性:A* は、最適性 (最短パスの検索) と完全性 (存在する解決策の検索) の両方を保証します。ただし、アルゴリズムは最適なパフォーマンスを得るためにさまざまなパスを探索する必要があるため、この保証には計算の複雑さの点でトレードオフが伴います。時間計算量に関しては、選択したヒューリスティック関数が最悪の場合に A* に影響します。受け入れられたヒューリスティック (目標に到達するための実際のコストを決して過大評価しない) を使用して、A* は最適化アルゴリズムの中で最も少ないノードを拡張します。 A * の最悪の場合の時間計算量は、最悪の場合の O(b ^ d) で指数関数的になります。ここで、「b」は有効な分岐係数 (ノードごとの平均フォロワー数)、「d」は最適な分岐係数です。

ただし、実際には、アルゴリズムを有望なパスに導くのに役立つヒューリスティック関数の影響により、A* のパフォーマンスが大幅に向上することがよくあります。適切に設計されたヒューリスティックの場合、有効な分岐係数ははるかに小さくなり、最適なソリューションへのアプローチがより速くなります。