關於人工智能中的知情搜索

知情搜索是一種搜索算法，它使用特定領域的知識來指導其在問題空間中的搜索。 從導航系統到遊戲，從自然語言處理到供應鏈管理，人工智能中的更多信息搜索顯著減少了解決不同問題所需的時間和計算資源。

通過使用特定領域的知識來指導搜索，明智的搜索算法可以快速消除不相關或不太有希望的路徑，從而使搜索專注於最有希望的選項。 為此， AI 中的這些類型的搜索算法使用啟發式方法來提高搜索的效率和速度。

報名參加世界頂尖大學的機器學習課程。 獲得碩士、行政 PGP 或高級證書課程，以快速推進您的職業生涯。

本文將討論人工智能中信息搜索的概念、其啟發式功能、算法示例及其優缺點。

啟發式功能

簡而言之，啟發式函數是一種解決問題的方法，它使用經驗法則或“最佳猜測”來估計搜索問題中到目標狀態的距離或成本。 啟發式函數估計目標狀態與當前狀態的距離，可用於指導搜索算法朝著目標前進。

知情搜索算法使用這些功能作為額外的信息來源，以就採取哪條路徑做出明智的決定。 由於這個原因，啟發式函數在知情搜索算法中是必不可少的。

啟發式函數的真實例子

為了更好地理解啟發式函數，這裡有一些真實的例子：

• 在經典的“滑動方塊拼圖”遊戲中，一個簡單的啟發式函數可能是計算與目標配置相比當前配置中錯位的方塊數量。 錯位的方塊越多，當前狀態離目標狀態就越遠。
• 在國際象棋中，啟發式功能可以是根據棋盤上的每個棋子的相對強度和位置為其分配一個值，並使用這些值的總和來估計當前玩家的優勢或劣勢。 此啟發式函數可用於引導搜索算法朝著可能導致更好位置的移動方向發展。

解決了這個問題，現在讓我們繼續前進，了解人工智能中一些最常用的知情搜索算法示例。

知情搜索算法示例

兩種最常用的知情搜索算法包括最佳優先搜索和 A* 搜索。 讓我們通過一些示例、優點、缺點及其 Python 實現來理解這兩種算法：

1. 最佳優先搜索

最佳優先搜索是一種搜索算法，它根據啟發式函數首先擴展最有希望的節點。 該算法從初始節點開始並檢查其所有子節點，選擇具有最低啟發值的子節點作為下一個要探索的節點。 這個過程一直持續到找到目標節點或探索完所有節點。

最佳優先搜索——示例

下面是一個簡單的例子來說明最佳優先搜索：

假設您正試圖找到從您家到附近雜貨店的最短路線。 您知道從附近的幾個地點到雜貨店的距離，但不知道要走的確切路線。 要使用最佳優先搜索解決此問題，您可以：

1. 從您的家庭位置開始，根據附近位置到雜貨店的距離計算每個附近位置的啟發值。
2. 選擇具有最低啟發值的附近位置作為下一個要探索的節點。
3. 從該附近位置計算其每個子節點位置的啟發值，並選擇具有最低啟發值的節點作為下一個要探索的節點。
4. 重複此過程，直到您到達雜貨店。

最佳優先搜索——Python 實現

以下是如何在 Python 中實現最佳優先搜索算法：

導入堆

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

# 初始化邊界和探索集

frontier = [(heuristic_func(start_state, goal_state), start_state)]

探索=設置（）

# 初始化路徑和代價

路徑 = {}

成本 = {}

路徑 [開始狀態] = 無

成本[開始狀態] = 0

而邊界：

# 從邊界獲取具有最低啟發值的節點

(h, current_state) = heapq.heappop(frontier)

如果當前狀態 == 目標狀態：

# 如果達到目標狀態則返迴路徑

返迴路徑

探索.add（當前狀態）

# 從當前狀態生成可能的動作

對於 actions_func(current_state) 中的操作：

下一個狀態 = 動作（當前狀態）

# 計算新路徑的成本

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

如果 next_state 不在探索中且 next_state 不在 [state for (h, state) in frontier] 中：

# 將新狀態添加到邊界

heapq.heappush(frontier, (heuristic_func(next_state, goal_state), next_state))

路徑 [下一個狀態] = 當前狀態

成本[下一個狀態] = new_cost

# 如果目標狀態不可到達則返回 None

返回無

如您所見，您需要定義以下函數：

• heuristic_func(current_state, goal_state)：此函數將當前狀態和目標狀態作為輸入，並返回從當前狀態到達目標狀態的成本估計。
• actions_func(current_state)：此函數將當前狀態作為輸入並返回可從當前狀態採取的操作列表。
• cost_func(current_state, action, next_state)：該函數將當前狀態、動作和下一狀態作為輸入，並返回從當前狀態到下一狀態採取動作的成本。

最佳優先搜索示例

開始狀態 = (0, 0)

目標狀態 = (4, 4)

def heuristic_func(current_state, goal_state):

返回 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(lambda state: (state[0]-1, state[1]))

如果 current_state[0] < 4:

actions.append(lambda state: (state[0]+1, state[1]))

如果 current_state[1] > 0:

actions.append(lambda state: (state[0], state[1]-1))

如果 current_state[1] < 4:

actions.append(lambda state: (state[0], state[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* 搜索

A*搜索是一種搜索算法，它使用從起始節點到達節點的成本和到達目標節點的剩餘成本的估計來指導其搜索。 該算法從初始節點開始並檢查其所有子節點，選擇具有最低組合成本和估計剩餘成本的子節點作為下一個要探索的節點。 這個過程一直持續到找到目標節點或探索完所有節點。

A* 搜索——示例

讓我們重新看一下前面的示例，您試圖找到從您家到附近雜貨店的最短路線。 現在，您可以：

1. 從您家的位置開始，計算到達每個附近位置的總成本，即從您家到該位置的距離與從該位置到達雜貨店的估計剩餘成本之和。
2. 選擇總成本最低的附近位置作為下一個要探索的節點。
3. 從該附近位置計算其每個子位置的總成本，即從該位置到子位置的距離、從起始節點到達該位置的成本以及到達雜貨店的估計剩餘成本的總和從那個孩子的位置。 選擇總成本最低的子位置作為下一個要探索的節點。
4. 重複此過程，直到您到達雜貨店。

這裡需要注意的重要一點是，A* Search 是一種最優搜索算法，可以保證找到到達目標狀態的最短路徑。 它在搜索空間大的問題上非常有效，廣泛用於視頻遊戲、機器人和路線規劃。 但是，它需要定義明確的啟發式函數才能有效。 出於這個原因，該算法可能會佔用大量內存，並且在具有許多節點的複雜問題中速度會變慢。

A* 搜索——Python 實現

以下是如何使用 Python 編程實現 A* 搜索算法：

導入堆

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

# 初始化邊界和探索集

frontier = [(heuristic_func(start_state, goal_state), start_state)]

探索=設置（）

# 初始化路徑和成本

路徑 = {}

成本 = {}

路徑 [開始狀態] = 無

成本[開始狀態] = 0

而邊界：

# 從邊界獲取 f 值最低的節點

(f, current_state) = heapq.heappop(frontier)

如果當前狀態 == 目標狀態：

# 如果達到目標狀態則返迴路徑

返迴路徑

探索.add（當前狀態）

# 從當前狀態生成可能的動作

對於 actions_func(current_state) 中的操作：

下一個狀態 = 動作（當前狀態）

# 計算新路徑的成本

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

如果 next_state 不在探索中且 next_state 不在 [state for (f, state) in frontier] 中：

# 將新狀態添加到邊界

heapq.heappush(frontier, (new_cost + heuristic_func(next_state, goal_state), next_state))

路徑 [下一個狀態] = 當前狀態

成本[下一個狀態] = new_cost

elif next_state in [state for (f, state) in frontier] and new_cost < cost[next_state]:

# 更新邊界中現有狀態的成本

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

frontier[index] = (new_cost + heuristic_func(next_state, goal_state), next_state)

路徑 [下一個狀態] = 當前狀態

成本[下一個狀態] = new_cost

# 如果目標狀態不可到達則返回 None

返回無

頂級機器學習課程和 AI 在線課程

A* 搜索示例

以下是如何將 astar_search 函數與這些函數一起使用的示例：

開始狀態 = (0, 0)

目標狀態 = (4, 4)

def heuristic_func(current_state, goal_state):

返回 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(lambda state: (state[0]-1, state[1]))

如果 current_state[0] < 4:

actions.append(lambda state: (state[0]+1, state[1]))

如果 current_state[1] > 0:

actions.append(lambda state: (state[0], state[1]-1))

如果 current_state[1] < 4:

actions.append(lambda state: (state[0], state[1]+1))

返回操作

def cost_func(current_state, action, next_state):

返回 1

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

如果路徑：

# 構造從起始狀態到目標狀態的路徑

當前狀態 = 目標狀態

while current_state != start_state:

打印（當前狀態）

當前狀態=路徑[當前狀態]

打印（開始狀態）

別的：

print(“目標狀態不可到達。”)

A* 搜索的優勢

• 它是領先的啟發式技術之一。
• 可以利用 A* 搜索來解決複雜的搜索問題

趨勢機器學習技能

A* 搜索的缺點

• A* 搜索性能在很大程度上依賴於啟發式算法的準確性。
• 搜索效率低。

流行的人工智能和機器學習博客和免費課程

帶走

知情搜索算法在人工智能中是必不可少的，因為它們允許計算機高效且有效地搜索目標狀態。 這些算法使用啟發式函數來估計每個可能移動的成本，並將搜索過程引導至目標狀態。 Best First Search 和 A* Search 是廣泛應用於各個領域的知情搜索算法的例子。 然而，定義明確的啟發式函數對於知情搜索算法的成功至關重要。

如果您有興趣了解有關人工智能和機器學習的更多信息，請查看利物浦約翰摩爾斯大學提供的機器學習和人工智能碩士課程。 該計劃涵蓋各種機器學習和人工智能主題，包括知情搜索等算法。 通過參加此計劃，您可以獲得在各種 AI 相關職業中取得成功所需的技能和知識。

您還可以查看upGrad 在管理、數據科學、機器學習、數字營銷和技術方面提供的免費課程。所有這些課程都有一流的學習資源、每週現場講座、行業作業和課程結業證書——全部免費！