盲目搜索启发式搜索与图有关的术语状态空间图——由节点(不一定是有限的节点)及连接节点的分枝的集合构成。有限节点图——节点数目有限的图称为有限节点图。有向图——一对节点用分枝线连接起来,从一个节点指向另一个节点。这种图叫做有向图。始节点叫父节点或双亲节点,终节点叫子节点。扩展——求解父节点的所有子节点,叫做扩展。路径——在一系列节点n1,n2,,nm中,从n1开始,ni总有分枝连接ni+1,称从n1到nm之间的分枝集合是路径。路径中不包含两个及以上相同的分枝,如果n1和nm是同一个节点,则称这种路径为闭路。不构成闭路的称为树。在用状态空间图来表示问题时,对问题的求解就是求出从初始节点到目标节点的路径。——一种计算机在状态图中寻找路径的方法。(记录扩展过的节点)OPEN表的引入节点号父节点号OPEN表(记录待扩展的节点)举例:八数码魔方例子中OPEN表变化过程节点号父节点号S0空AS0BS0CS0DS0EAFACLOSED表变化过程编号节点号父节点号0S0空1AS02BS0图搜索的一般过程(1)建立一个只含有起始节点S的搜索图G,把S放到一个叫做OPEN表的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表,其初始为空表。(3)LOOP:若OPEN表是空表,则失败退出。(4)选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。
盲目搜索启发式搜索-PPT课件 来自淘豆网m.daumloan.com转载请标明出处.
