《AI-第5章 搜索与优化策略（1）.pptx》由会员分享，可在线阅读，更多相关《AI-第5章 搜索与优化策略（1）.pptx（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能导论5.1 概述5.2 状态空间搜索5.3 与或树搜索5.4 智能优化搜索第五章第五章 搜索与优化策略搜索与优化策略5.1 5.1 概述概述根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为。45.1.1 5.1.1 什么是搜索什么是搜索搜索的分类是按照预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。5u问题求解过程可以看作一个搜索过程。状态空间表示法是用来表示问题及其搜索过程的一种方法。它是人工智能中。状态
2、用以描述问题求解过程中不同时刻的状况，是一个数据结构，一般用一组变量的有序组合表示：SK=(Sk0,Sk1,)当每一个分量的值确定时，就得到了一个具体的状态。引起状态中某些分量发生变化，从而使问题从一个状态变为另一个状态的操作称为算符。在产生式系统中，一条产生式规则就是一个算符。由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：其中S是问题所有；F是；G是。状态空间的图示形式称为状态空间图。65.1.2 5.1.2 状态空间表示法状态空间表示法状态空间示例二阶梵塔问题7状态空间85.1.3 与或树表示法u分解把一个复杂问题分解为若干个较为简单的子问题，每个子问
3、题又可继续分解。重复此过程，直到不需要或者不能再分解为止。如此形成“与”树。u等价变换利用同构或同态的等价变换，把原问题变换为若干个较为容易求解的新问题。如此形成“或”树。9与或树10与或树的基本概念不能再分解或变换，而且直接可解的子问题。在与/或树中，没有子节点的节点统称为端节点；本原问题所对应的节点称为终止节点。在与/或树中，满足下列条件之一者，称为可解节点：它是一个终止节点；它是一个“或”节点，且其子节点中至少有一个是可解节点；它是一个“与”节点，且其子节点全部是可解节点。关于可解节点的三个条件全部不满足的节点1112三阶梵塔问题的与或树135.2 5.2 状态空间搜索状态空间搜索5.2
4、 状态空间搜索15盲目搜索的特点：搜索按规定的路线进行，不使用与问题有关的启发性信息；适用于其状态空间图是树状结构的一类问题。启发式搜索要使用与问题有关的启发性信息，并以这些启发性信息指导搜索过程，可以高效地求解结构复杂的问题。搜索的原则165.2.1 状态空间的一般搜索过程uOPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。uCLOSE表用于存放将要扩展或者已经扩展的节点。17状态节点父节点编号 状态节点 父节点搜索的一般过程1.对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；2.对于那些先前已经在G中出现
5、过的M成员，确定是否需要修改它指向父节点的指针；3.对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；18一些说明195.2.2 广度优先搜索20广度优先搜索过程尾21重排九宫的广度优先搜索22广度优先搜索的特点235.2.3 深度优先搜索24深度优先搜索过程首25重排九宫的深度优先搜索26深度优先搜索的特点275.2.4 有界深度优先搜索u对深度优先搜索引入搜索深度的界限（设为dm），当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。1.把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。2.如果OPEN表为空，则问题无解
6、，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n的深度d(节点n)=dm，则转第2步。6.若节点n不可扩展，则转第2步。7.扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。2829有界深度优先搜索的一些改进方法30重排九宫的有界深度优先搜索315.2.5 启发式搜索32启发性信息与估价函数33估价函数示例34BBBWWWE局部择优搜索1.把初始节点S0放入OPEN表，令g(S0)=0。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个
7、节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展，则转第2步。6.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并按估价值从小到大的顺序放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。35代价树的深度优先搜索1.把初始节点S0放入OPEN表，令g(S0)=0。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展，则转第2步。6.扩展节点n，将其子节点按代
8、价从小到大的顺序放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。36全局择优搜索37基本思想：每当要选择一个节点进行考察时，局部择优搜索只是从刚生成的子节点中进行选择，选择的范围比较狭窄。全局择优搜索每次总是从OPEN表的全体节点中选择一个估价值最小的节点。搜索过程：1.把初始节点S0放入OPEN表，计算f(S0)。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展，则转第2步。6.扩展节点n，用估价函数f(x)计算每个子节点的估
9、价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小至大的顺序进行排序，然后转第2步。广度优先搜索、代价树的广度优先搜索以及全局择优搜索都是以当前所有节点作为考察范围的。但是前二者可以看作全局择优搜索的特例。重排九宫问题的全局择优搜索树38代价树的广度优先搜索39代价树广度优先搜索过程40代价树广度优先搜索示例415.2.6 A*算法4243A*算法的性质A*算法的搜索效率在很大程度上取决于h(x)，在满足h(x)h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它携带的启发性信息越多，搜索时扩展的节点数越少，搜索的效率越高。44h(x)的单调性45搜索的完备性46搜索效率47有效分枝因数485.3 5.3 与或树搜索与或树搜索5.3 与或树搜索50待续待续