人工智能导论--第二章_搜索与问_...

1、第二章搜索、问题求解与博弈问题求解能力是人类智能的基木组成部分,研究 并实现问题求解是人工智能的重耍研究内容之一。 知识（问题）的表不是问题求解的基础，两种普遍采用的问题表示去法：状态空间农水与或图农示搜索（优化）:在问题表示基础上，在合理的时 间范围内，从问题所仃可能的解屮找到一个瑕优解或町行解，是问题求解中的核心我术。启发式搜索人工科能的木质特征之一。计算机博弈涉及问题表示、搜索技术等AI核心问 题，现何砂计邦机礴弈卞质上是将f専弈问题转变为一个或图技索问题进行处理。主要内容2.1搜索概述2.2问题求解 2.2.1状态空间 2.2.2与或图2.3搜索技术图搜索些例子2.4机器廨弈-搭积木科

2、力游戏：冇一个农夫带一条狼、一只羊和一筐菜要从河 的左岸乘船到右岸，但受下列条件限制：船太小，农夫每次只能帯一样东西过河没冇农夫看管，则狼姿吃羊，羊箜吃菜请设计一个过河方案，使得农夫、狼.羊、菜 都不能受损地过河。类似问题：野人和传教上问题下棋（扑克、西洋跳棋、国际象棋、彖棋 等）（属于博弈）2.1搜索概述2.1搜索概述如來问题冇解，一定能找到一个解 如果问题存在最优解，则一定能找到这个时间和空间复杂性，在保证最优性和完备人工智能的多个研究领域从求解现实问题的过程来 看，都可抽彖为一个“问题求解”过程 问题求解过程实际上就是一个搜索过程最优性和计算法复杂性是搜素中的一对矛盾，搜索 必须考虑的三

3、个问题：采川肓H搜索还是启发式搜索-冇H搜嗦：不考虑问题本f的tvn.通过遍切问题解的集合來d 找可行解或最优解。-启发式捜索：利用与问题有关的启发式信息來确宦搜索方向，以 加快搜索过程。进行局部搜索还是金集搜索搜索可行解还是最优解评价一个搜索算法的因素：完备性：最优性：般优解复杂性：性的前提卜，算法的复杂性越小越好。n前的搜索算法还不能同时满足以上三个耍求。 为了进行搜索，首先必须用某种形式把问题表 示山來：状态空间表示法和与或图表示法就是 用来衣示问题及其搜索过程的两种常用方法。2.2问题求解2.2.1状态空间表示法:状态空间表示法和与或图表示法不仅是问题表示 的方法，也分别代表了两种问题

4、求解的思路-状态空间将问题求解所涉及的每个町能的步骤表 示成一个状态，全部状态以及状态之间的所右转 换构成一个以图的形式表示的状态空间。问题的 求解过程是在状态空间中搜索一条最优的或町行 的从初始状态到H标状态的路径的过程。与或图表示法的基础是问题归约，通过一系列分 解或变换，将复杂问题逐步转化为比较简单的间 题，直至可以直接求解的本原问题。与或图的求 解过程是在与或图中搜索一个将原始问题变换为 简单问题在变换为木原问题的、垠优的或叮行的 川约步骤的过程。-状态空间表示法是用“状态”和“算了 來表示问题的一种方法-状态：用来描述问题求解过程中不同时刻的状 况算了：表示对状态的操作，算子的每次使

5、用就 使问题由一种状态变换为另一种状态当达到H标状态时，由初始状态到H标状态所 用算了的序列就是问题的一个解J 2.2.1状态空间表示法-U态足描述问擲水解过程屮任一时刻状况的数据结构，一 鮫用一如菱圧儒石序组合表示：Sk(Sko，Ski，.)-为给每一分暈以确1的值时，就得到一个具体的状态算子.引起状态中某些分虽发牛变化，从而使问题山一个状态变 为另一f状态的操作称为算子。产生式系统中，毎一矣产 牛式规则就是一个煤了-状态空间.山问璽的全部状态及一切可用笄符所构成的集合称为问题 的状怎空间，一能用三元组表示：(SFCIG)S：所冇状态构成的集合-F：用丁状态转换的算r的集合-C：状态转换代价

6、的聚合-1:初始状态的集合.G; U标状态的集合丄例:二阶Hanoi Tower (梵塔)问题X有三根柱了，右；林丁上穿右人 B两个盘片， 盘A小丁盘B,盘A位于盘B的上面。要求把这两个 盘片全部移到另根柱了上，而a规定每次只能移 动一片，任何时刻都不能使盘B位丁盘A的上面。.设Sk=(SkwSki)衣示问题的状态，Sko表示盘片A所在的柱 号，Ski&示盘片B所在的柱号全部町能的状态：SO=(1JLS1=(1,2X S2=(13)zS3=(2Ah S4=2), S5二3), S6=(3JL S7=(3,2X S8=(33).问題的初始状态集合S=SO, H标集介为G=S4,58算了分别川A(

7、i,j), B(i,j)衣示A(ij):盘片A从杆i移到B(iJ):盘片B从柱i移到用全部可能的5?r：A(b2), A(l,3), A(24), A(2,3), A(3,1), A(3,2),B1,2), B(13), B(2,1), B(2,3), B(3J), B(3,2)列:二阶Hanoi Tower （梵塔）间题鬲4状态,12种算了构成的状态空间转移图：右2.2.1状态空间表示法恵结：用状态空间方法农示问题时，tt先必须定义状态的描述形 式，通过使用这种描述形式町把问题的切状;S都衣示H 來。其次，还安定义一组算符，通过使用算符可把问题由 一种状态转变为勢一种状态。问题的求解过程是一

8、个不断把算符作用丁状态的过程.如 果在便用某个算符肩得到的新状态是H标状态，就得到问 题的一个解：从初贻状态到H标状态所用算符构成的序列。算符的一次速用，就15问题由种状态餐变为另种状态。 这就得到了名个解。把便用算符最少的解栋为最优解。 对任何-个状态，可使用的算符可能不止一个，因而山一 个状态生成的后继状态轨町能自名个。当对这些后继状f 成更进-參U态时，幷尢应对哪-状态进存 操作呢？这取决丁搜索策略，不同搜索策略的操作顺序足 不和同的。2.2.1状态空间表示法peg 1peg 2圖一狀態(2.2.1)加丁状态空间农示的问题求解算法Stepl：确定问题状态的计算机描述形式，将所 有町能的状

9、态表示出来，并确定其中的初始状态 和H标状态。Step2：确定促使状态发牛转换的操作，并金计 算机中将其农示为相应的算符。Step3：以状态为顶点，状态之间所允许的操作 为仃向边，获得图形式的状态空间。Step4：应用图搜索方法，在状态空间中搜索从 初始状态到目标状态的仗优路径或可行路径。t例：三阶Hanoi Tower （梵塔）问题（工;二）=（小盤子所任的柱子中盤子所任的柱子人盤子所任的柱子）.peg 3:三阶Hanoi Tower （梵塔）问题它在一個步可能改變的狀態如下:(2,2, 1)將柱1盤子移到柱3將柱2盤了移到柱1將柱2盤了移到柱3(2, 2, 3)(1,2, 1).丄丿(3,

10、2, 1)屮列:三阶Hanoi Tower （梵塔）问题起始走一 1 ower of Hanoi状態關係表1 r(1.1. jj2. 1, 1)3 1 I)2 (1.1-2)(：.L2J41. L3J(lL3)C. 1.3)0,1.3)4(IQ)C.iUJ(2 2)(2. 2, 2)(322) U3. 2)6仃23)C. 2,3)9(14)24)a3,0LXI)$(1.3,2)G，32)3. 3. 2)U2. 3)9(l33)d33)333)10 2 1. 11. L 1J. h 02. i. 2)12(2 1.3)(1.1.3)(3.1-3)d33U(2二 I)0.2.1)(3. I)(X2

11、016。31)fl. 3, n(3. 3 hfi-in17(23打(132)(332(XI2)1S(23,1)(l 3) 3,3(il3)19Q 1.1)(I-to(：.Ll(3.21)200.1.2(Ub2j(3.22i2J(J 1, J)D(32打2：OX 1)CL XI)(2工nQlI)25G 2 I)(1-2 2)(2. 2. 2(5.12)240 2.(1.2 (2. X MZ；）25Q3 I)Cl-3 0(2M lZ2)26(13- 2(L 3.2)(Z 3,2)3n27旺噪(1-3 3)(233、終結2.2.2与或图表示法2.2.2与或图表示法（树）O也称为问题归约方法：把初始问

12、题通过一系列交换 报终变为一个子问题集合，而这些于问题的解町以 直接得到，从而解答了初始问题。.分解：把一个Q杂间题分解为若个较为简单的子问题, 毎个子问题乂町继续分解为若I：个更为简单的子问题。 車父此过程，直到不盂要再分解或者不能再分解为上。 然后对毎个子问题分别进行求解，最后把各子问题的解 复介起來就衍到了原I* -J题的解.问题的分解可以川图表示出來，称为与树。例如，把问 题P分解为三个子问题P1、P2和P3,町以农示为下图：等价变换：利川同构或同态的等价变换，把它 变换成若个较容易求解的新问题。若新问题 中有一个可求解，则就得到了原问题的解。问题的等价变换过程也可用一个图表示出来，

13、称为“或树。-与或树的结合称为与或图12.2.2与或图表示法嚟原问禅:不能再分解或变换,而且直接町解的子问 题称为栄原问题。端节点片终11:节点=在与/,或树中，没右了节点的节 点称力端节点；木j泉同舷所对脸Mj节点称男终匚节点O 显然，终止节点一定是端节点，但端节点不一定是终 止节点。可解节点：在与/或树今，满足下列条件之一的节点: -1）它是一个终|：节点。-2?它足一个“或”节点，n其了节点至少冇一个是町解节 S足一个“与” Vf点，J1其了打点全部足可解丫点。 不对解节点：上面三个条件全不满足的节点。 解树：市节:点所构成的，、并且由这些叮解节点可 推出初始节点（它対应上原始冋题）为叮

14、解节点的孑树 称为解树。在祸树中定包含初始节点。丄例:三阶Hanoi Tower （梵塔）问题弓设有A、B、C三个盘片以及三根林子,三个盘片按从小到人的顺序穿在1号柱匕耍 求把它们全部移到3号柱上，而且每次只能 移动一个盘片，任何时刻都不能把大的盘 片压衣小的盘片上血，如图所示。AjrzzL419：三阶旳110）Tower （梵塔）问题1）为了把三个盘片全部移到3号柱上，必须先把盘片C移 到3号柱上。2）为了移盘片C,必须先把盘片A及B移到2号柱上。3）、丄 1把盘片C移到3号盘上后，就町把A、B从2号柱移到3 号柱上，以完成问题的求解。把原问题分解为三个了问题：-i）把盘片A及B移到2号柱的

15、双盘片问题。-2）把盘片C移到3号柱的m-盘片问题。-3）把盘片A及B移到3廿柱的双盘片问题。其中，子问题子问题3）又分別可分解为三个了问题列：三阶Hanoi Tower （梵塔）问题f 义问题状态表示：设三元组（i,j,k）表示状态，其屮 i表示盘片C所在的柱号,j表示盘丿tB所在的柱号；k 表示盘片A所在的柱号。初始问题可表示为：（1、1. 1）1=（3, 3. 3）-与/或树表示如图所示。（把图中7个终止节点（木原 间题）按从左至右排列，彳d到了初始问题的解）（hljn（122）（3.2,2） =（333）（13）=O入 3）|（323D2】）gi）n（33J）（122m（UJ）=（14

16、3）Q3）q（3,3,3）|dXh=333（12.2.2与或图表示法玛r与或图表示的问题求解算法Stepl：确定单个问题描述形式，可采用状态空 间表示法。Step2：从原始问题开始，逐步进行分解和变换, 穴到木原问题，然后将全部分解和变换过程表示 为Q或图。steps：从端顶点开始，逐步向上I叫溯，标注各 顶点为可解或不可解顶点，直到标注原始顶点为 可解顶点或不可解顶点为止Step4：当原始顶点被确定为可解顶点时，输出 相丿卫解图为问题的解。丄2.3搜索技术索技术足人工科能的里木技术之住人工智能 各应用领域中被广泛地使用。.早期的人匚智能程序打搜索技术联系就更为紧密，儿乎所 竹的T期的人工智能

17、秤序都是以搜索为基础的。例如， A.Newell（艾伦纽厄尔）和HASimon（西蒙）等人编写的 LT（Logic Theorist）程丿九J.Slagle写的符号积分程序SAINT, ANewell和HASimon写的GPS（Geneal Problem Solver）l4 序，H-Gelernter（格伦特尔）写的 Gwometry theorem - proving machine程序，R.Fikes（菲克斯）RiN.Nilsson（尼尔逊） 写的STRIPS（Stanford Research Institute Problem Solver） 程序以及A.Samuel（塞缪尔）写的C

18、hechers程序等，都使用 J各种搜索技术。-现在，搜索技术渗透在各种人工智能系统屮，町以说没仃哪 一种人1智能的应川不用搜索方法,在专家系统、门然语言 理解、口动程序设计、模式识别、机器人学、信息检索和 瞎弈都广泛使用搜技术。2.3搜索技术搜索问题是AI核心理论问题之一 一般一个问题可以用好儿种搜索技术解决，选 择一种好的搜索技术对解决问题的效率很有关 系，甚至关系到求解问题有没育解。搜索方法好的标准， 般认为有两个= (1)搜索空间小；-(2)解最佳。2.3搜索技术-搜索从问题性质上来看/町分为一般搜索 和博奕搜索，从处理方法上來看，町分为盲 U搜索和启发式搜索。还可以分得更细。当所给定

19、的问题用状态空间表示时，则求解过 程町归结为对状态空间的搜索。当问题冇解时，使用不同的搜索策略，找到解 的搜索空间范用是有区别的。一般來说，对人 空间问题#搜索策略是要解决组合爆炸的问题M 2.3搜索策略Y 通常搜索策略的要任务是确定如何选取规则的 方式。冇两种基本方式： 一种足不不虑给定问题所真冇的特定知识，系统根据事 先确泄好的某种固定排序，依次调用规则或随机调用规 则,这实际上足盲H搜索的方法，一般统称为无信息引 孑的搜索策略。.另一种足考虑问题领域町应用的知识#动态地确定规则 的排序，优先调用较合适的规则使用，这就是通常称为 启发式捜索第略或冇信息引导的搜索策略。I 叫溯法(Backt

20、racking) 爬山法(Hill Climbing) 宽度 优先法(Breadth-fi rst) 深度优先法(Depth-first) 限定范国搜索法(Beam Search) 最佳优先法(Best-fi rst)Al领域的搜索方法AI领域的搜索方法 (1)求任一解路的搜索策略 (2)求最住解路的搜索策略大英帖物馆法(British Museum) 分枝界限法(Branch and Bound) 动态规划法(Dynamic Programming) 最佳图搜索法(A*) (3)求与或关系解图的搜索法 一般与或图搜索法(A0*)-极小极人法(Minimax)剪枝法(Alpha-beta Pruning)川发式剪枝法(Heuristic Pruning)搜索策略分类-般劭（即一人走JP育目