下载文档原格式
第七章搜索策略搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接矢系到智能系统的性能与运行效率，因而尼尔逊把它列入人工智能研究的四个核心问题之一。
第七章搜索策略•7 • "I基本概念・73与/或图的搜索第略♦7」博弈树a索24第七章搜索策略]• 7.1吐木概念・7.2欢态空｛11册搜宓览术• 73 I 刀或图的牠索策略X 7.1. 1什么是搜索根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，从而使问题匮8 满得到解决的过程称为搜索。
,7」.1什么最搜索 ■ 7 |二状念I 间灰小 > 7J-3 U 咸 THJDidJ.«七章授索彙昭3茎本播念搜索分为盲目搜索利启发式搜索°肓仔如（或称非启发式搜索）是按预定的控制策略进 行搜索，在搜索过程中获得的中间信息不用来改进搜索策 略。
启笈式掇转（或称非盲目搜索）是在搜索中加入了与 问题有矢的启发性信息•用以指导搜索朝着最有希望的方 向前进，加速问题的求解过程井且找到最优解。
-7.1.2状态图表示法K 什么是状态图例题7.1设仆二个钱币，氏初始状态为（反、正、反），欲得的 目标状态为（正、正、正）或（反•反、反）。
目标状态问题是允许每次只能且必须H 转一个钱币，连翻三次， 问能否达到目标状态？初始状态/④止®®®®®®®【解】要求解这个问题■可通过引入一个3维变量将问题表示出来。
设3维变量为：其中:qi=O表示正，qjT表示反(iT,2,3)共有八种组合：Qo=( O3O5O) Q1 ={ 0,0,1)□2= (0,150) □3=(0,1,1)€>4=( 1)0,0)八5= (1 >0,1)Q6 = (lJ5O)Q7={1JJ)每个组合就视为一个芳点。
初始状态为Q5,目表状态为Q济Q?810dJ 图可得解有7个，a ah, aha ,haa , hbh, hcc . ebc , ccb其中：“表示a 的变化.b 表示蚯的变化，C 表示Cb 的变化•-7.1.2状态图表不法把这种描述得到的有向图称为状态（空间）图. 其屮的节点代表一种格局（或称为状态）•而两节点之 间的连线表示两节点之间的联系•它可视为某种操作、规 则、变换等。
人工智能搜索算法1. 介绍人工智能（Artificial Intelligence，AI）搜索算法是指通过计算机程序对问题空间进行搜索，以找到最优解或接近最优解的方法。
在许多领域，如信息检索，机器学习，自然语言处理等，人工智能搜索算法都发挥着重要的作用。
本文将介绍人工智能搜索算法的基本原理和常见的搜索算法。
2. 搜索问题搜索问题是指在一个给定的问题空间中寻找目标解的问题。
问题空间由问题的状态和操作构成。
状态是问题解的表示形式，操作则是从一个状态到另一个状态的转换。
搜索问题的目标是找到一系列操作，使得从初始状态到目标状态的转换。
3. 盲目搜索算法3.1 深度优先搜索算法深度优先搜索算法（Depth-First Search，DFS）是一种经典的搜索算法，它通过栈的方式实现。
算法从起始状态开始，依次选择一个操作，然后转移到下一个状态，直到找到目标解或者无法转移到下一个状态为止。
def dfs(problem, state):if problem.goal_test(state):return statefor action in problem.actions(state):child = problem.result(state, action)result = dfs(problem, child)if result is not None:return resultreturn None3.2 广度优先搜索算法广度优先搜索算法（Breadth-First Search，BFS）是另一种常见的搜索算法，它通过队列的方式实现。
算法从起始状态开始，逐层地扩展状态空间，直到找到目标解。
def bfs(problem, state):queue = [state]while len(queue) !=0:state = queue.pop(0)if problem.goal_test(state):return statefor action in problem.actions(state):child = problem.result(state, action)queue.append(child)return None4. 启发式搜索算法4.1 A*算法A算法是一种常用的启发式搜索算法，它通过估计从当前状态到目标状态的代价来选择下一步操作。
