5.状态空间搜索

人工智能—状态空间搜索状态空间搜索总体要求•各种搜索方法•A*算法•搜索树•盲目搜索方法–深度优先–广度优先•重点：启发式搜索•题型：给一个问题按照某种搜索方法策略给出解决方法第六章问题求解与搜索策略•6.1基本概念•6.2状态空间的搜索策略•6.3与/或树的搜索策略•6.4搜索的完备性与效率问题求解•问题求解是人工智能的核心问题之一•问题求解的目的–机器自动找出某问题的正确解决策略–更进一步，能够举一反三，具有解决同类问题的能力•是从人工智能初期的智力难题、棋类游戏等问题的研究中开始形成和发展起来的一大类技术，搜索技术是问题求解的主要手段之一–问题表示–解的搜索•示例——八数码难题在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。12384567初始状态81324567目标状态如何将棋盘从某一初始状态变成最后的目标状态？问题示例6怎样找到两点之间的最短路径呢？6.1.2状态空间表示法（1）很多问题的求解过程都可以看作是一个搜索过程。问题及其求解过程可以用状态空间表示法来表示。（2）状态空间用“状态”和“算符”来表示问题。–状态状态用以描述问题在求解过程中不同时刻的状态，一般用一个向量表示：SK=(Sk0,Sk1,…)–算符使问题从一个状态转变为另一个状态的操作称为算符。在产生式系统中，一条产生式规则就是一个算符。–状态空间由所有可能出现的状态及一切可用算符所构成的集合称为问题的状态空间。（3）采用状态空间求解问题，可以用下面的一个三元组表示：(S,F,G)其中S是问题初始状态的集合；F是算符的集合；G是目标状态的集合。•传教士野人问题（Missionaries&Cannibals，MC问题）有三个传教士M和三个野人C过河，只有一条能装下两个人的船，在河的一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险，你能不能提出一种安全的渡河方法呢？状态：问题在某一时刻所处的“位置”，“情况”等根据问题所关心的因素，一般用向量形式表示，每一位表示一个因素0：右岸1：左岸初始状态：(0,0,0)目标状态：(3,3,1)状态可有多种表示方法：(左岸传教士数,右岸传教士数,左岸野人数,右岸野人数,船的位置)或(左岸传教士数,左岸野人数,船的位置)•算子（算符，操作符）——使状态发生改变的操作•MC问题中的算子–将传教士或野人运到河对岸–Move-1m1c-lr：将一个传教士(m)一个野人(c)从左岸(l)运到右岸(r)–所有可能操作•Move-1m1c-lrMove-1m1c-rlMove-2c-lrMove-2c-rlMove-2m-lrMove-2m-rlMove-1c-lrMove-1c-rlMove-1m-lrMove-1m-rl传教士野人问题状态空间图MC6.2状态空间的搜索策略状态空间搜索策略盲目搜索启发式搜索广度优先搜索深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的深度优先搜索局部择优搜索全局择优搜索A*算法求解过程转化为在状态空间图中搜索一条从初始节点到目标节点的路径问题必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目标返回的路径OPEN表(记录还没有扩展的点)CLOSED表(记录已经扩展的点)每个状态的节点结构中必须有指向父节点的指针6.2.1状态空间的一般搜索过程•OPEN表和CLOSE表–OPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。–CLOSE表用于存放将要扩展的节点。对一个节点的扩展是指：用所有可适用的算符对该节点进行操作，生成一组子节点OPEN表CLOSE表状态节点父节点编号状态节点父节点搜索的一般过程1.把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；2.检查OPEN表是否为空，若为空则问题无解，退出；3.把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；4.考察节点n是否为目标节点。若是，则求得了问题的解，退出；5.扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；6.对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）7.按某种搜索策略对OPEN表中的节点进行排序；8.转第2步。一些说明•一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。•一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的子节点被生成过，当前又作为另一个节点的子节点被再次生成。此时，它究竟应选择哪个节点作为父节点？一般由原始节点到该节点的代价来决定，处于代价小的路途上的那个节点就作为该节点的父节点。•在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。•如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜索失败。•通过搜索得到的图称为搜索图，搜索图是状态空间图的一个子集。由搜索图中的所有节点及反向指针所构成的集合是一棵树，称为搜索树。根据搜索树可给出问题的解。盲目搜索•不同的搜索策略其搜索的效率是不同的•盲目搜索又称无信息搜索–宽度优先搜索–深度优先搜索–特点•搜索过程中不使用与问题有关的经验信息•采用固定策略对OPEN表排序•搜索效率低•不适合大空间的实际问题求解6.2.2广度优先搜索•基本思想：从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前，不对第n＋1层的节点进行扩展。•OPEN表中节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。广度优先搜索过程1.把初始节点S0放入OPEN表。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展，则转第2步。6.扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2步。重排九宫的广度优先搜索操作符：空格左移、上移、右移、下移2831476528314765832147652837146583214765283714658321476581324765283746152837146523184765231847651238476512384765283147652318476523418765281437652814376528314576283145762831647528316476283641752831647528316754S0Sg12345678910111213141516171811920212223242526在上述广度优先算法中需要注意两个问题：1、对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（空格左移、上移、右移、下移）。2、在对任一节点进行扩展的时候，如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入OPEN表）。因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的原则，生成一棵搜索树。广度优先搜索的特点•优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。•缺点：广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。6.2.3深度优先搜索•深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。深度优先搜索过程1.把初始节点S0放入OPEN表。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展，则转第2步。6.扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。重排九宫的深度优先搜索2831476528314765283167542318476528314765281637542816375428316475283164762831647528316754S01234...5深度优先搜索的特点•在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。•本质：以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。6.2.4有界深度优先搜索•基本思想：–对深度优先搜索引入搜索深度的界限（设为dm），当搜索深度达到了深度界限，而仍未出现目标节点时，就换一个分支进行搜索。•搜索过程：1.把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n的深度d(n)=dm，则转第2步（此时节点n位于CLOSE表，但并未进行扩展）。6.若节点n不可扩展，则转第2步。7.扩展节点n，将其子节点放入OPEN表的首部，为每一个子节点都配置指向父节点的指针，将每一个子节点的深度设置为d(n)+1，然后转第2步。•如果问题有解，且其路径长度≤dm，则上述搜索过程一定能求得解。但是，若解的路径长度dm,则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。•要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。有界深度优先搜索的一些改进方法1.先任意设定一个较小的数作为dm，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限dm仍未发现目标节点，并且CLOSE表中仍有待扩展节点时，就将这些节点送回OPEN表，同时增大深度界限dm，继续向下搜索。如此不断地增大dm，只要问题有解，就一定可以找到它。但此时找到的解不一定是最优解。2.为了找到最优解，可增设一个表R，每找到目标节点Sg后，就把它放入到R的前面，并令dm等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以后求得的解一定是最优解。重排九宫的有界深度优先搜索设深度界限dm＝4231847652341876522123847651237846523184765123847652341876523418576283147652318476528143765248137652831457628315746832641752836417528316754281637562814376528143765283145762831457628364175283167542831647628316475283147652831647528314765S0123Sg7891415162324252645610111213171819202127286.2.5代价树的广度优先搜索•边上标有代价(或费用)的树称为代价树。•用g(x)表示从初始节点S0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)•基本思想：每次从OPEN表中选择节点往CLOSE表传送时，总是选择其中代价最小的节点。也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面。•如果问题有解，代价树的