关于人工智能中的知情搜索

知情搜索是一种搜索算法，它使用特定领域的知识来指导其在问题空间中的搜索。 从导航系统到游戏，从自然语言处理到供应链管理，人工智能中的更多信息搜索显着减少了解决不同问题所需的时间和计算资源。

通过使用特定领域的知识来指导搜索，明智的搜索算法可以快速消除不相关或不太有希望的路径，从而使搜索专注于最有希望的选项。 为此， 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 在管理、数据科学、机器学习、数字营销和技术方面提供的免费课程。所有这些课程都有一流的学习资源、每周现场讲座、行业作业和课程结业证书——全部免费！