第五章人工智能搜索策略.

人工智能ArtificialIntelligence主讲：杨利英西安电子科技大学计算机学院E_mail：[e-mail]第五章搜索策略5.1基本概念5.2状态空间的搜索策略5.3与/或树的搜索策略5.4搜索的完备性与效率5.1基本概念采用某种策略，在知识库中寻找可利用的知识，从而构造一条代价较小的推理路线，使问题得到解决的过程称为搜索。5.1.1什么是搜索5.1.1什么是搜索搜索分为盲目搜索和启发式搜索。盲目搜索是按照预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。5.1.2状态空间表示法状态空间用“状态”和“算符”来表示问题。状态状态用以描述问题在求解过程中不同时刻的状态，一般用向量表示算符使问题从一个状态转变为另一个状态的操作称为算符。状态空间由所有可能出现的状态及一切可用算符所构成的集合称为问题的状态空间。回顾状态空间示例：十五数码难题119151341275861321014119415131275861321014119151341275861321014119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014回顾5.1.3与/或树表示法对于一个复杂问题，直接求解往往比较困难。此时可通过下述方法进行简化：（1）分解（2）等价变换回顾5.1.3与/或树表示法（1）分解把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解。重复此过程，直到不需要再分解或者不能再分解为止。如此形成“与”树。（2）等价变换利用同构或同态的等价变换，把原问题变换为若干个较为容易求解的新问题。如此形成“或”树。PP1P2P3与树PP1P2P3或树回顾与/或树P31PP1P2P3与/或树P11P12P32P33分解与等价变换可以结合起来使用，这样形成的图称为“与/或树”回顾由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树(t表示终止节点)。解树中一定包含初始节点。（它对应于原始问题）解树解树PtttPttt回顾5.2状态空间的搜索策略状态空间搜索策略盲目搜索启发式搜索广度优先搜索深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的深度优先搜索局部择优搜索全局择优搜索A*算法5.2状态空间的搜索策略盲目搜索搜索按规定的路线进行，不使用与问题有关的启发性信息；适用于其状态空间图是树状结构的一类问题。启发式搜索使用与问题有关的启发性信息，并以这些启发性信息指导搜索过程，可以高效地求解结构复杂的问题。5.2.1状态空间的一般搜索过程一个复杂问题的状态空间一般都是十分庞大的。如64阶梵塔问题共有3的64次方个不同的状态。把问题的所有状态空间都进行存储有时候是不可能的。把问题的所有状态空间都进行存储也是不必要的。因为与解题有关的状态空间往往只是整个状态空间的一部分，只要能生产并存储这部分状态空间就可以求出问题的解。5.2.1状态空间的一般搜索过程如何产生问题需要的状态空间从而实现对问题的求解呢？答案就是搜索技术。搜索技术基本思想：把问题的初始状态作为当前状态，选择适用的算符对其操作，生产一组子状态，然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解，否则按某种搜索策略从已生成的状态中再选择一个作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符为止。5.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.针对M中子节点的不同情况，分别进行如下处理：①对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）②对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中）③对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中）7.按某种搜索策略对OPEN表中的节点进行排序；8.转第2步。搜索的一般过程对一般搜索过程的一些说明一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。对一般搜索过程的一些说明一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的子节点被生成过，当前又作为另一个节点的子节点被再次生成。此时，它究竟应选择哪个节点作为父节点？一般由原始节点到该节点的代价来决定，处于代价小的路途上的那个节点就作为该节点的父节点。对一般搜索过程的一些说明在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜索失败。对一般搜索过程的一些说明通过搜索得到的图称为搜索图，搜索图是状态空间图的一个子集。由搜索图中的所有节点及反向指针所构成的集合是一棵树，称为搜索树。根据搜索树可给出问题的解。5.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小插曲－关于九宫问题射雕英雄传瑛姑的问题：将一至九这九个数字排成三列，不论纵横斜角，每三字相加都是十五，如何排法？黄蓉的回答：九宫之义，法以灵龟，二四为肩，六八为足，左三右七，戴九履一，五居中央。幻方问题中国人首先发现了幻方洛水神龟献奇图关于三阶幻方的奥秘南宋杨辉研究幻方第一人幻方问题在我国古代称为“纵横图”，又叫“九宫算图”。南宋大数学家杨辉在1275年所著的《续古摘奇算法》两卷中，除了给出洛书中3阶幻方的构造方法外，还给出了4阶至10阶的幻方。杨辉对3阶幻方的解释29435761816594211714310615138121三阶幻方(15)四阶幻方(34)欧美的幻方热德国画家和文艺理论家丢勒在1514年创作的一幅铜版雕刻画《忧伤》中就有一个4阶幻方。名画《忧伤》现在珍藏于大英博物馆。富兰克林也投入了很大精力研究幻方。名画《忧伤》广度优先算法中需要注意的问题1、对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（如前面重排九宫例子中的空格左移、上移、右移、下移）。2、在对任一节点进行扩展的时候，如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入OPEN表）。因此，广度优先搜索的本质是：以初始节点为根节点，在状态空间图中按照广度优先的原则，生成一棵搜索树。广度优先搜索的特点优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。缺点：广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。5.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操作符：空格左移、上移、右移、下移深度优先搜索的特点在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。用深度优先求得的解，不一定是路径最短的解。本质：以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。5.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的值是比较困难的。即使能求出解，它也不一定是最优解。有界深度优先搜索的