人工智能状态空间搜索策略

第七章搜索策略搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接矢系到智能系统的性能与运行效率，因而尼尔逊把它列入人工智能研究的四个核心问题之一。

第七章搜索策略•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算法是一种常用的启发式搜索算法，它通过估计从当前状态到目标状态的代价来选择下一步操作。

第五章搜索策略习题参考解答5.1 练习题5.1 什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？5.2 用状态空间法表示问题时，什么是问题的解？求解过程的本质是什么？什么是最优解？最优解唯一吗？5.3 请写出状态空间图的一般搜索过程。

在搜索过程中OPEN表和CLOSE表的作用分别是什么？有何区别？5.4 什么是盲目搜索？主要有几种盲目搜索策略？5.5 宽度优先搜索与深度优先搜索有何不同？在何种情况下，宽度优先搜索优于深度优先搜索？在何种情况下，深度优先搜索优于宽度优先搜索？5.6 用深度优先搜索和宽度优先搜索分别求图5.10所示的迷宫出路。

图5.10 习题5.6的图5.7 修道士和野人问题。

设有3个修道士和3个野人来到河边，打算用一条船从河的左岸渡到河的右岸去。

但该船每次只能装载两个人，在任何岸边野人的数目都不得超过修道士的人数，否则修道士就会被野人吃掉。

假设野人服从任何一种过河安排，请使用状态空间搜索法，规划一使全部6人安全过河的方案。

（提示：应用状态空间表示和搜索方法时，可用(N m,N c)来表示状态描述，其中N m和N c分别为传教士和野人的人数。

初始状态为(3,3)，而可能的中间状态为(0,1),(0,2),(0,3), (1,1),(2,1),(2,2),(3,0),(3,1),(3,2)等。

）5.8 用状态空间搜索法求解农夫、狐狸、鸡、小米问题。

农夫、狐狸、鸡、小米都在一条河的左岸，现在要把它们全部送到右岸去。

农夫有一条船，过河时，除农夫外，船上至多能载狐狸、鸡和小米中的一样。

狐狸要吃鸡，鸡要吃小米，除非农夫在那里。

试规划出一个确保全部安全的过河计划。

（提示：a.用四元组(农夫，狐狸，鸡，米)表示状态，其中每个元素都可为0或1，0表示在左岸，1表示在右岸；b.把每次过河的一种安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。

）5.9 设有三个大小不等的圆盘A 、B 、C 套在一根轴上，每个圆盘上都标有数字1、2、3、4，并且每个圆盘都可以独立地绕轴做逆时针转动，每次转动90°，初始状态S 0和目标状态S g 如图5.11所示，用宽度优先搜索法和深度优先搜索法求从S 0到S g 的路径。

搜索策略部分参考答案1 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：(1) 船太小，农夫每次只能带一样东西过河；(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。

请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。

题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。

(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。

解：第一步，定义问题的描述形式用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。

第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。

由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。

第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。

由于农夫必须在船上，故对农夫的表示省略。