第5章搜索策略

人工智能原理及应用第5章搜索求解策略PrinciplesandApplicationsofArtificialIntelligence第5章搜索求解策略

5.1

搜索的概念

5.2

状态空间表示法

5.3

盲目的图搜索策略

5.4

启发式图搜索策略搜索的概念问题求解：解空间搜索

已知解空间未知解空间搜索的概念问题求解：解空间搜索

连续搜索空间搜索的概念问题求解：解空间搜索

连续搜索空间离散搜索空间旅行商问题、背包问题、作业流水线调度问题…围棋对弈、象棋对弈、投资博弈…机器人路径规划、灾难逃生规划、战场火力配置规划…搜索的概念问题求解：解空间搜索

解的表示形式搜索的策略穷举搜索启发式搜索搜索的概念搜索：从问题初始状态到目标状态的一条路线正向搜索:从初始状态出发逆向搜索:从目标状态出发

选择应用操作算子初始状态新状态目标状态？终止YN搜索的概念搜索：从问题初始状态到目标状态的一条路线盲目搜索:按固定步骤进行搜索启发式搜索:运用领域知识指导搜索过程

选择应用操作算子初始状态新状态目标状态？终止YN搜索的概念搜索：从问题初始状态到目标状态的一条路线是否一定能找到一个解？是否能找到最优解？搜索是否会终止？搜索所需的时间和空间复杂性？

选择应用操作算子初始状态新状态目标状态？终止YN状态空间表示法基本定义状态(State):描述问题在任一时刻所处状况的一种数据结构初始状态S0/目标状态集G操作(Operator):状态之间的转换函数状态空间(StateSpace):四元组<S,O,S0,G>

状态空间表示法（例）八数码问题问题描述:33的棋盘上，放有1~8的数字，另有一格为空。空格上下左右的数字可移动到空格。问从某个状态出发，如何确定移动序列，最终到达图示的目标状态。状态结构:长度为9的向量（数组）S0=[2,3,1,5,0,8,4,6,7]G={[1,2,3,8,0,4,7,6,5]}操作Left:A[p0]A[p01] (p0%3>0)Right:A[p0]A[p0+1] (p0%3<2)Up:A[p0]A[p03] (p03)Down:A[p0]

A[p0+3] (p0<6)2315846712384765初始状态目标状态状态空间表示法（例）修道士与野人问题问题描述:河的左岸有3个修道士、3个野人和一条船。修道士和野人都会划船，船上每次最多只能坐两个人；任何岸边只要野人的数目多于修道士数目，修道士就会被野人吃掉。安排一个安全的方案将修道士和野人都渡到河的右岸。状态结构:?操作:?状态空间表示法（例）修道士与野人问题问题描述:河的左岸有3个修道士、3个野人和一条船。修道士和野人都会划船，船上每次最多只能坐两个人；任何岸边只要野人的数目多于修道士数目，修道士就会被野人吃掉。安排一个安全的方案将修道士和野人都渡到河的右岸。状态结构:三元组<m,c,b>S0=[3,3,1]G={[0,0,0]}操作:Lij,RijL01L10L11L02L20R01R10R11R02R20状态空间表示法（例）修道士与野人问题问题描述:河的左岸有3个修道士、3个野人和一条船。修道士和野人都会划船，船上每次最多只能坐两个人；任何岸边只要野人的数目多于修道士数目，修道士就会被野人吃掉。安排一个安全的方案将修道士和野人都渡到河的右岸。状态空间表示法状态空间的图描述结点：状态边：状态转换操作求解过程：寻找图中从初始状态到目标状态的一条路径（操作序列）搜索算法：操作序列的选择方法状态空间表示法（例）旅行商问题问题描述:寻找从网络图中的一个结点出发、历经其它结点并最终回到原结点的一条最短路径。状态结构:?操作:?状态空间表示法（例）最短路径问题问题描述:寻找从网络图中的两个结点之间的一条最短路径。状态结构:?操作:?状态空间表示法（例）最短路径问题问题描述:寻找从网络图中的两个结点之间的一条最短路径。SP(a,e)SP(b,e)SP(c,e)SP(d,e)181028SP(c,e)SP(d,e)2433(b,e)15状态空间表示法与/或树（问题归约法）将复杂问题分解（归约）为一系列较简单的问题，通过对简单问题的求解来实现对原问题的求解。与树:从所有子问题的解可得出原问题的解或树:从任一子问题的解可得出原问题的解状态空间表示法与/或树（问题归约法）盲目的图搜索策略盲目搜索:按预定方向进行搜索Open:待展开的结点列表Closed:已展开过的结点列表初始化:将S0状态放入Open表达到目标状态？搜索成功YNOpen表为空?搜索失败从Open表中取出一个当前结点扩展当前结点,将未出现的子结点加入Open表YN盲目的图搜索策略盲目搜索:按预定方向进行搜索宽度优先搜索:Open表先进先出初始化:将S0状态放入Open表达到目标状态？搜索成功YNOpen表为空?搜索失败从Open表中取出一个当前结点扩展当前结点,将未出现的子结点加入Open表YN盲目的图搜索策略盲目搜索:按预定方向进行搜索宽度优先搜索:Open表先进先出深度优先搜索:Open表先进后出初始化:将S0状态放入Open表达到目标状态？搜索成功YNOpen表为空?搜索失败从Open表中取出一个当前结点扩展当前结点,将未出现的子结点加入Open表YN启发式图搜索策略启发式搜索:利用问题领域知识指导搜索过程代价优先搜索:Open表按结点代价函数排列初始化:将S0状态放入Open表达到目标状态？搜索成功YNOpen表为空?搜索失败从Open表中取出一个当前结点扩展当前结点,将未出现的子结点加入Open表YN启发式图搜索策略启发式搜索:利用问题领域知识指导搜索过程代价优先搜索:Open表按结点代价函数排列abcd181028启发式图搜索策略启发式搜索:利用问题领域知识指导搜索过程代价优先搜索:Open表按结点代价函数排列abcd181028d20b24启发式图搜索策略启发式搜索:利用问题领域知识指导搜索过程代价优先搜索:Open表按结点代价函数排列abcd181028e15cd2416d20启发式图搜索策略启发式搜索:利用问题领域知识指导搜索过程代价优先搜索:Open表按结点代价函数排列abcd181028e15e12bc1620d20启发式图搜索策略A搜索算法代价优先搜索:Open表按结点代价函数排列估价函数:f(n)=g(n)+h(n)初始化:将S0状态放入Open表达到目标状态？搜索成功YNOpen表为空?搜索失败从Open表中取出一个当前结点扩展当前结点未出现的子结点:加入Open表已在Open表中但代价更小:更新Open表已在Closed表中但代价更小:移入Open表YN启发式图搜索策略A*搜索算法代价优先搜索:Open表按结点代价函数排列估价函数:f(n)=g(n)+h(n)满足h(n)h*(n),其中h*(n)为状态n到目标状态的最优路径代价启发式图搜索策略A*搜索算法可采纳:存在最短求解路径时，必能找到它单调性:h(c)h(p)

cost(p,c),h(G)=0启发性:h(n)越大，启发性越好启发式图搜索策略其它启发策略局部最优:扩展当前节点时，选择估价最小的一个后继节点作为下一个考察节点分支限界:如代价函数单调增长，设已找到的最优解代价为c*，则剪去所有代价已超过c*的结点abcd181028ed1520b24cd2416与／或树搜索策略可解标示:由可解子节点来确定父节点为可解节点不可解标示:由不可解子节点来确定父节点为不可解节点将初始问题放入Open表当前问题为叶结点？可解性标示YNOpen表为空?搜索失败从Open表中取出一个当前结点分解当前问题,将未出现的子结点加入Open表YN搜索成功YN确定S0可解性?与／或树搜索策略深度优先广度优先代价优先博弈树搜索策略博弈树的搜索过程博弈具有“二人零和、全信息、非偶然”的特征。

（1）二人零和：对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN败；MIN方胜，MAX方败；和局。

（2）全信息：在对垒过程中，任何一方都了解当前的格局及过去的历史。 （3）非偶然：任何一方在采取行动前都要根据当前的实际情况，进行得失分忻，选取对自己最为有利而对对方最为不利的对策，不存在掷骰子之类的“碰运气”因素。即双方都是理智地决定自己的行动。

博弈树搜索策略博弈树的搜索过程如果站在某一方（如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵“与／或树”。描述博弈过程的与或树称为博弈树。 （1）博弈的初始格局是初始节点。 （2）在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流地扩展节点。 （3）所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。博弈树搜索策略极大极小分析法极大极小分析法的基本思想是： （1）设博弈的双方中一方为A，另一方为B。极大极小分析法是为其中的一方（例如A方）寻找一个最优行动方案的方法。 （2）为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较。 （3）为了计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分，称为静态估值。 （4）当端节点的估值计算出来后，再推算出父节点的得分。 （5）如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。

博弈树搜索策略极大极小分析法博弈树的启发式搜索算法：

（1）k=1，初始棋局Sk=S1;

（2）如果棋局Sk是终止节点棋局，则算法成功终止；否则，由棋局Sk生成A方所有可能的或关系子节点Si(i=1,2,…,n)。（3）对每一个或关系子节点Si，生成其B方所有可能的与关系子节点Sj

(i=1,2,…,n)

。生成节点数为n×m+1的部分博弈树。（4）计算每个与关系子节点Si的启发函数值Sj。博弈树搜索策略极大极小分析法（5）分别由m个与关系子节点倒推计算其父节点（与节点）的启发函数值:

（6）由n个或关系子节点倒推计算其父节点Sk（或节点）的启发函数值：（7）A方从Sk的n个或关系子节点中选择节点i作为最优行动方案，获得棋局Si。 （8）B方从Si的m个与关系子节点中选择节点j作为最优行动方案，获得棋局Sj。（9）若节点j是端节点，则算法终止；否则令k=j，转步骤（2）。博弈树搜索策略极大极小分析法一字棋游戏。设有一个三行三列的棋盘，如图5-27所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设A方的棋子用×标记，B方的棋子用○标记，并规定A方先走步。

博弈树搜索策略极大极小分析法【解】（1）启发函数定义

A方的启发函数定义为

B方的启发函数定义为 其中，ea(Si)为形成棋局Si时，A方棋子×可能占满行、列和对角线的数目；eb(Si)为形成棋局Si时，B方棋子○可能占满行、列和对角线的数目。博弈树搜索策略极大极小分析法（2）A方第一回合博弈树

博弈树搜索策略-剪枝

（1）对于一个与节点MIN，若能估计出其倒推值的上