人工知能におけるインフォームド サーチのすべて

インフォームド検索は、ドメイン固有の知識を使用して問題空間を検索する検索アルゴリズムの一種です。 ナビゲーション システムからゲームのプレイ、自然言語処理からサプライ チェーン管理まで、人工知能による情報に基づいた検索により、さまざまな問題の解決に必要な時間と計算リソースが大幅に削減されました。

ドメイン固有の知識を使用して検索をガイドすることにより、十分な情報に基づいた検索アルゴリズムが、無関係またはあまり見込みのないパスを迅速に排除し、検索が最も有望なオプションに集中できるようにします。 これを行うために、 AI のこれらのタイプの検索アルゴリズムはヒューリスティックを使用して、検索の効率と速度を向上させます。

世界のトップ大学の機械学習コースに登録してください。 マスター、エグゼクティブ PGP、または上級認定プログラムを取得して、キャリアを加速させましょう。

この記事では、人工知能におけるインフォームド サーチの概念、そのヒューリスティック機能、アルゴリズムの例、およびそれらの長所と短所について説明します。

ヒューリスティック機能

簡単に言えば、ヒューリスティック関数は、経験則または「最良の推測」を使用して、検索問題の目標状態までの距離またはコストを推定する問題解決アプローチです。 ヒューリスティック関数は、目標状態が現在の状態からどれだけ離れているかを推定します。これは、検索アルゴリズムを目標に導くために使用できます。

情報に基づいた検索アルゴリズムは、これらの関数を追加の情報源として使用して、どのパスを使用するかについて情報に基づいた決定を下します。 このため、ヒューリスティック関数はインフォームド サーチ アルゴリズムに不可欠です。

ヒューリスティック関数の実例

ヒューリスティック関数をよりよく理解するために、いくつかの実際の例を次に示します。

• 古典的な「スライド タイル パズル」ゲームでは、単純なヒューリスティック関数を使用して、目標構成と比較して現在の構成で場違いなタイルの数を数えることができます。 場違いなタイルが多いほど、現在の状態は目標の状態から離れています。
• チェスでは、ヒューリスティック関数によって、ボード上の各駒に相対的な強さと位置に基づいて値を割り当て、それらの値の合計を使用して現在のプレーヤーの有利または不利を推定することができます。 このヒューリスティック関数を使用して、検索アルゴリズムを、より良いポジションになる可能性が高い動きに導くことができます。

それが解決したら、次は先に進み、人工知能におけるインフォームド サーチ アルゴリズムの最もよく使用される例のいくつかを理解しましょう。

インフォームド検索アルゴリズムの例

最も一般的に使用されるインフォームド サーチ アルゴリズムには、ベスト ファースト サーチと A* サーチの 2 つがあります。 これら 2 つのアルゴリズムを、いくつかの例、利点、欠点、およびそれらの Python 実装とともに理解しましょう。

1. ベストファーストサーチ

最良の最初の検索は、ヒューリスティック関数に従って、最も有望なノードを最初に拡張する検索アルゴリズムです。 アルゴリズムは最初のノードから開始し、そのすべての子ノードを調べて、ヒューリスティック値が最も低い子を次に探索するノードとして選択します。 このプロセスは、目標ノードが見つかるか、すべてのノードが探索されるまで続きます。

最良の最初の検索 - 図示された例

最適な最初の検索を示す簡単な例を次に示します。

自宅から近くの食料品店までの最短ルートを見つけようとしているとします。 近くのいくつかの場所から食料品店までの距離はわかっていますが、正確なルートはわかりません。 最適優先検索を使用してこの問題を解決するには、次のことができます。

1. 自宅の場所から始めて、食料品店までの距離に基づいて近くの各場所のヒューリスティック値を計算します。
2. 探索する次のノードとして、ヒューリスティック値が最も低い近くの場所を選択します。
3. その近くの場所から各子の場所のヒューリスティック値を計算し、探索する次のノードとしてヒューリスティック値が最も低いものを選択します。
4. 食料品店に到着するまで、このプロセスを繰り返します。

最適な最初の検索 – Python 実装

Python で最適な最初の検索アルゴリズムを実装する方法は次のとおりです。

インポート ヒープq

def best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# フロンティアと探索セットの初期化

フロンティア = [(heuristic_func(start_state, goal_state), start_state)]

探検=セット（）

# パスとコストを初期化

パス = {}

コスト = {}

パス[開始状態] = なし

コスト[開始状態] = 0

一方フロンティア:

# フロンティアからヒューリスティック値が最も低いノードを取得

(h, current_state) = heapq.heappop(フロンティア)

現在の状態 == 目標の状態の場合:

# ゴール状態に到達したらパスを返す

復路

explored.add(現在の状態)

# 現在の状態から可能なアクションを生成する

actions_func(current_state) のアクションの場合:

next_state = アクション (現在の状態)

# 新しいパスのコストを計算

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

next_state が探索されておらず、next_state が [フロンティアの (h, state) の状態] にない場合:

# 新しい状態をフロンティアに追加

heapq.heappush(フロンティア, (heuristic_func(next_state, goal_state), next_state))

パス[次の状態] = 現在の状態

コスト[next_state] = new_cost

# 目標状態に到達できない場合は None を返す

返却なし

ご覧のとおり、次の関数を定義する必要があります。

• heuristic_func(current_state, goal_state):この関数は、現在の状態と目標の状態を入力として受け取り、現在の状態から目標の状態に到達するコストの推定値を返します。
• actions_func(current_state):この関数は、現在の状態を入力として受け取り、現在の状態から実行できるアクションのリストを返します。
• cost_func(current_state, action, next_state):この関数は、現在の状態、アクション、および次の状態を入力として取り、現在の状態から次の状態へのアクションのコストを返します。

ベスト ファースト サーチの例

start_state = (0, 0)

目標状態 = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(current_state[0] – goal_state[0]) + abs(current_state[1] – goal_state[1])

def actions_func(current_state):

アクション = []

current_state[0] > 0 の場合:

actions.append(ラムダ状態: (状態[0]-1、状態[1]))

current_state[0] < 4 の場合:

actions.append(ラムダ状態: (状態[0]+1, 状態[1]))

current_state[1] > 0 の場合:

actions.append(ラムダ状態: (状態[0], 状態[1]-1))

current_state[1] < 4 の場合:

actions.append(ラムダ状態: (状態[0], 状態[1]+1))

返品アクション

def cost_func(current_state, action, next_state):

リターン 1

path = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

パスの場合:

# 開始状態から目標状態へのパスを構築する

現在の状態 = 目標の状態

while current_state != start_state:

印刷 (現在の状態)

現在の状態 = パス[現在の状態]

印刷 (開始状態)

それ以外：

print(“目標の状態に到達できません。”)

ベスト ファースト サーチの利点

• 幅優先探索と比較して、最良優先探索の時間計算量は低くなります。
• 最良の最初の検索は、BFS アルゴリズムと DFS アルゴリズムの両方の利点を取得して実装します。

ベスト ファースト サーチの短所

• 考えられているよりも長い距離をカバーすることがあります。
• ループに陥る可能性は非常に高いです。

検索

* 検索は、開始ノードからノードに到達するためのコストと、目標ノードに到達するための残りのコストの見積もりの​​両方を使用して、その検索をガイドする検索アルゴリズムです。 アルゴリズムは最初のノードから開始し、そのすべての子ノードを調べて、組み合わせたコストと残りの推定コストが最も低い子を、次に探索するノードとして選択します。 このプロセスは、目標ノードが見つかるか、すべてのノードが探索されるまで続きます。

A* 検索 – 図示された例

自宅から近くの食料品店までの最短ルートを見つけようとしている前の例をもう一度見てみましょう。 これで、次のことができます。

1. 自宅の場所から開始し、自宅からその場所までの距離と、その場所から食料品店に到達するための推定残りの費用の合計として、近くの各場所に到達するための総費用を計算します。
2. 探索する次のノードとして、総コストが最も低い近くの場所を選択します。
3. その近くの場所から、その場所から子の場所までの距離、開始ノードからその場所に到達するためのコスト、および食料品店に到達するための推定残りのコストの合計として、その子の場所のそれぞれの合計コストを計算します。その子の場所から。 調査する次のノードとして、総コストが最も低い子ロケーションを選択します。
4. 食料品店に到着するまで、このプロセスを繰り返します。

ここで注意すべき重要なことは、A* 検索は、目標状態への最短経路を見つけることを保証する最適な検索アルゴリズムであるということです。 これは、探索空間が大きい問題で効率的であり、ビデオ ゲーム、ロボット工学、ルート計画で広く使用されています。 ただし、有効にするには、明確に定義されたヒューリスティック関数が必要です。 このため、このアルゴリズムはメモリを大量に消費し、多数のノードが含まれる複雑な問題では速度が低下する可能性があります。

A* 検索 – Python 実装

Python プログラミングを使用して A* 検索アルゴリズムを実装する方法を次に示します。

インポート ヒープq

def astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# フロンティアと探索セットの初期化

フロンティア = [(heuristic_func(start_state, goal_state), start_state)]

探検=セット（）

# パスとコストを初期化

パス = {}

コスト = {}

パス[開始状態] = なし

コスト[開始状態] = 0

一方フロンティア:

# フロンティアから f 値が最も低いノードを取得

(f, current_state) = heapq.heappop(フロンティア)

現在の状態 == 目標の状態の場合:

# ゴール状態に到達したらパスを返す

復路

explored.add(現在の状態)

# 現在の状態から可能なアクションを生成する

actions_func(current_state) のアクションの場合:

next_state = アクション (現在の状態)

# 新しいパスのコストを計算

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

next_state が探索されておらず、next_state が [フロンティアの (f, state) の状態] にない場合:

# 新しい状態をフロンティアに追加

heapq.heappush(フロンティア, (new_cost + heuristic_func(next_state, goal_state), next_state))

パス[次の状態] = 現在の状態

コスト[next_state] = new_cost

[フロンティアの (f, state) の状態] の elif next_state および new_cost < cost[next_state]:

# フロンティアの既存の状態のコストを更新

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

フロンティア[インデックス] = (new_cost + heuristic_func(next_state, goal_state), next_state)

パス[次の状態] = 現在の状態

コスト[next_state] = new_cost

# 目標状態に到達できない場合は None を返す

返却なし

トップの機械学習コースとオンライン AI コース

A* 検索の例

これらの関数で astar_search 関数を使用する方法の例を次に示します。

start_state = (0, 0)

目標状態 = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(current_state[0] – goal_state[0]) + abs(current_state[1] – goal_state[1])

def actions_func(current_state):

アクション = []

current_state[0] > 0 の場合:

actions.append(ラムダ状態: (状態[0]-1、状態[1]))

current_state[0] < 4 の場合:

actions.append(ラムダ状態: (状態[0]+1, 状態[1]))

current_state[1] > 0 の場合:

actions.append(ラムダ状態: (状態[0], 状態[1]-1))

current_state[1] < 4 の場合:

actions.append(ラムダ状態: (状態[0], 状態[1]+1))

返品アクション

def cost_func(current_state, action, next_state):

リターン 1

パス = astar_search(start_state、goal_state、heuristic_func、actions_func、cost_func)

パスの場合:

# 開始状態から目標状態へのパスを構築する

現在の状態 = 目標の状態

while current_state != start_state:

印刷 (現在の状態)

現在の状態 = パス[現在の状態]

印刷 (開始状態)

それ以外：

print(“目標の状態に到達できません。”)

A* 検索の利点

• これは主要なヒューリスティック手法の 1 つです。
• A* 検索を活用して、複雑な検索問題を解決できます

注目の機械学習スキル

A* 検索の欠点

• A* 検索のパフォーマンスは、ヒューリスティック アルゴリズムの精度に大きく依存します。
• 検索効率が悪い。

人気の AI と ML のブログと無料コース

取り除く

インフォームド サーチ アルゴリズムは、コンピューターが目標状態を効率的かつ効果的に検索できるようにするため、人工知能に不可欠です。 これらのアルゴリズムはヒューリスティック関数を使用して、考えられる各動きのコストを見積もり、検索プロセスを目標状態に導きます。 ベスト ファースト サーチと A* サーチは、さまざまな分野で広く使用されているインフォームド サーチ アルゴリズムの例です。 ただし、適切に定義されたヒューリスティック関数は、情報に基づいた検索アルゴリズムの成功にとって重要です。

人工知能と機械学習について詳しく知りたい場合は、リバプール ジョン ムーアズ大学が提供する upGrad の機械学習と人工知能プログラムの修士号を確認してください。 このプログラムでは、インフォームド サーチなどのアルゴリズムを含む、さまざまな機械学習と AI のトピックを扱います。 このプログラムを受講することで、さまざまな AI 関連のキャリアで成功するために必要なスキルと知識を得ることができます。

upGrad が提供する管理、データ サイエンス、機械学習、デジタル マーケティング、テクノロジーの無料コースもご覧ください。 これらのコースにはすべて、一流の学習リソース、毎週のライブ講義、業界の課題、コース修了証明書があり、すべて無料です。