人工智能入门 课件 3.符号智能与问题求解

搜索与问题求解AI:SearchandProblemSolving2大纲什么是搜索?问题表示–状态空间与与或图

–

它们体现了两种问题求解的思路!博弈搜索–极大极小算法–α-β剪枝AI:SearchandProblemSolving3PartⅠ:什么是搜索?AI:SearchandProblemSolving4Theseus怎样找到逃出Minotaur的迷宫的路?Ariadne的线索:AI:SearchandProblemSolving5什么是搜索?以可以接受的计算代价，在问题所有解答中找出最优解或可行解。理想的搜索算法：尽可能快地找到最优解.求解的效果与效率之间存在矛盾完备性,最优性,复杂性AI:SearchandProblemSolving6PartⅡ:问题表示AI:SearchandProblemSolving7例子:2-阶梵塔问题初始状态目标状态1目标状态2规则:1.每次移动一个金片2.大的金片不能放在小的金片上面.AI:SearchandProblemSolving8步骤1表示所有的状态,包括初始状态和目标状态初始状态目标状态步骤2表示状态转换函数AI:SearchandProblemSolving9将金片A从柱i移动到柱

j

将金片B从柱i移动到柱

j

所有函数:步骤3构造状态空间AI:SearchandProblemSolving10步骤4

搜索该图以找到问题解答AI:SearchandProblemSolving112.1状态空间S:状态集合F:状态转换函数（或行动）的集合

C:状态转换函数代价的集合(如果不求最优解，可以不考虑此因素)I:初始状态集合G:目标状态集合一个状态空间对应于一个图,其中从初始状态到目标状态的路径就是问题的一个解。AI:SearchandProblemSolving12基于状态空间的问题求解步骤1

表示所有状态，标出其中的初始状态和目标状态.步骤2

表示所有状态转换函数步骤3

以状态为节点，以状态转换函数为边，构成一个图。步骤4

搜索该图以发现对应于最优解或可行解的路径。AI:SearchandProblemSolving13例子:八数码问题状态?

动作?

初始与目标状态?

动作代价?

AI:SearchandProblemSolving14例子:八数码问题状态?

数字与空格的位置动作?

空格上、下、左、右移动初始与目标状态?

如图动作代价?

每移动一下代价为1AI:SearchandProblemSolving15与或图实现问题归约的数据结构-每一个节点对应于一个问题-“与”节点=分解-“或”节点=转换-端节点*终止节点=本原问题*其他端节点=不可解问题-可解节点与不可解节点

AI:SearchandProblemSolving16基于与或图的问题求解找出一个解图，它是代表原始问题求解方案的一个子图步骤1.表示每个问题。步骤2.对问题进行归约，用与或图表示归约过程。步骤3.从端节点向上回溯，直到根节点，标注各个节点可解或不可解。步骤4.如果根节点被标注为可解，输出相应的解图。AI:SearchandProblemSolving17例子:3-阶梵塔问题初始状态目标状态AI:SearchandProblemSolving18步骤1.表示问题

问题状态:

原始问题:(1,1,1)(3,3,3)步骤2.问题归约

将原始问题分解为:-子问题1=(1,1,1)(1,2,2)-子问题2=(1,2,2)(3,2,2)√-子问题3=(3,2,2)(3,3,3)

继续分解子问题2和3

AI:SearchandProblemSolving19步骤3.搜索该图，以决定根节点可解或不可解.步骤4.输出整个图作为解答.(如何解释?)AI:SearchandProblemSolving20PartⅣ:博弈搜索图片来自：/DL88250AI:SearchandProblemSolving213.1博弈树代表博弈过程的数据结构

-2个玩家(MAX和MIN)-确定性的-轮流进行-零和的-信息完备AI:SearchandProblemSolving22游戏状态：(K1,K2,….,Kn,MINorMAX)每堆钱币个数当前走步方每次MIN或MAX选择一堆钱币并且把它分成数目不等的两堆。

当MIN或MAX不能完成任务时,就输了。

首先,n=1,k1=7,MIN为走步方例：分钱币游戏AI:SearchandProblemSolving23(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)分钱币游戏的博弈树MAX的必胜招?AI:SearchandProblemSolving24游戏中的每一步MAX

和

MIN

总是采取对自己最有利的行动。为了能够胜利,MAX应该每一步选择最有利的行动,同时认为

MIN

也会每一步都采取对MIN最好的行动(也就是说，对MAX最坏)

在想象对手为最强对手的情况下采取最好的行动！在结构上，博弈树是与或图！AI:SearchandProblemSolving25(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)作为与或图进行搜索作为与或图进行搜索?AI:SearchandProblemSolving26

实际条件的限制

如中国象棋:共有

10160

种状态。假设每秒搜索

103

个节点，需要

10145

年找到一个最优走步。(最新估计宇宙年龄为

1010年)解决办法

截断策略:限制博弈树的搜索深度

估价函数:从MAX的角度出发估计博弈状态，值越大，该状态对MAX越有利。

3.2极大极小搜索AI:SearchandProblemSolving27选择移动到具有最高极大极小值的位置!例：两个玩家的游戏AI:SearchandProblemSolving28例:一字棋估价函数:e(P)=e(+P)－e(-P)

对于对称状态只存储其中一种e(P)＝6-4＝2AI:SearchandProblemSolving29MAX第一次走步AI:SearchandProblemSolving30MAX第二次走步AI:SearchandProblemSolving31最后状态AI:SearchandProblemSolving323.3α-β剪枝通过剪掉博弈树中不必要的分支提高搜索的效率。使用深度限制搜索(DLS)策略AI:SearchandProblemSolving33α-β剪枝例1AI:SearchandProblemSolving34α-β剪枝例1AI:SearchandProblemSolving35α-β剪枝例1AI:SearchandProblemSolving36α-β剪枝例1AI:SearchandProblemSolving37α-β剪枝例1α-β剪枝例2AI:SearchandProblemSolving38S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≤0≥0＝0≤-6＝0≤0＝4＊＊＊＊＊＊AI:SearchandProblemSolving39什么是α-β?α

是MAX顶点倒推值的最小边界如果

v

比α更小,MAX将不搜索它。

剪掉这一枝β

定义方式类似，但针对MIN节点AI:SearchandProblemSolving40确定性博弈程序现状

西洋跳棋:1994年，Chinook终结了人类世界冠军MarionTinsley长达40年的统治。

国际象棋:1997年，DeepBlue在六回合制比赛中打败了人类世界冠军GarryKasparov.

黑白棋:人类高手拒绝与机器比赛，因为机器下棋水平实在是太好了。

围棋:人类高手同样拒绝与机器比赛，因为机器下棋水平实在是太差了。AI:SearchandProblemSolving41深蓝AI:SearchandProblemSolving42总结状态空间-五个要素(S,F,C,I,G)-问题的解是从初始顶点到目标顶点的一条路径与或图-问题规约

-目标是确定根节点是否可解-问题的解是让根节点可解的一个子图AI:SearchandProblemSolving43搜索算法的效果和效率是一对矛盾。在设计和评价搜索算法时，需要综合考虑算法的完备性、最优性和复杂性。具体设计策略有盲目搜索与启发式搜索之分，全局搜索和局部搜索之分，以及搜索最优解和可行解之分。

图搜索算法的一般结构是不断扩展顶点，直到发现目标顶点（状态空间）或者确定初始顶点的可解性（与或图）。总结AI:SearchandProblemSolving44不同图搜索算法的主要区别在于顶点的扩展顺序不同。盲目搜索不考虑问题特性,包括广度优先搜索、深度优先搜索、有界深度优先搜索和迭代加深深度优先搜索。启发式搜索算法根据问题所提供的启发式信息，用估价函数估计顶点的搜索效率，选择估计效率最高的顶点进行扩展。A*算法是影