问题求解基本原理问题求解基本原理问题实例基于状态空间的问题求解方法基于问题空间的问题求解方法状态空间法有关概念状态空间法有关概念问题空间法有关概念问题空间法的有关概念（2）问题空间法有关概念（2）小结–问题求解方法比较问题求解基本原理搜索技术预备状态空间搜索有关概念盲目搜索策略启发式搜索策略搜索策略预备搜索策略预备搜索策略预备状态空间搜索有关概念状态空间搜索有关概念状态空间搜索有关概念路径：对于一个节点序列（n0,n1,…,nl,…,nk），如若每一节点ni-1都有一个后继节点ni（i=1,2,…,k），则称该节点序列为一条从节点n0到节点nk、长度为k的路径；路径还可表示为与节点序列对应的规则序列。基于状态空间的盲目搜索算法:宽度优先搜索策略深度优先搜索策略盲目搜索算法的符号及数据结构宽度优先搜索算法宽度优先搜索算法open:=[S];closed:=[];d=深度限制值whileopen≠[]do{n:=first(open);remove(first(open));add(n,closed)；ifn=goalthenexit(success);ifdepth(n)>dthencontinue;expand(n)->{mi};delete((mi)(mi∈{mk}∨(mi∈{ml}));Insert(mj,open)};exit(fail);深度优先搜索算法盲目搜索算法应用实例-盲目搜索算法应用实例-宽度优先策略求解8数码问题：深度优先策略求解8数码问题：1、利用宽度优先法或深度优先法，程序实现High-waymap问题求解，只考虑节点的连接和变换,不考虑边的权值;求出有向图的一条解径,给出求解过程（即，给出Open，Closed表中的内容）。给定两个油桶,一个可装4公斤油,一个可装3公斤油,油桶上无任何度量标记。问：怎样才能使4公斤油桶里恰好只装2公斤油？设状态定义：(x,y)，其中，x：4公斤油桶中实际装油公斤数；y：3公斤油桶中实际装油公斤数。问题表示：(0,0)-〉(2,y)要求定义合法的装油规则，利用盲目搜索策略画出状态图。问题求解基本原理启发式图搜索策略启发式图搜索算法启发式图搜索算法-A算法启发式图搜索算法-A算法A算法搜索算法应用实例-8数码问题搜索算法应用实例-8数码问题搜索算法应用实例-8数码问题搜索算法应用实例-8数码问题启发式最佳图搜索算法-A*算法信息度定理：有两个A*算法A1和A2,若A2比A1有较多的启发式信息（即对所有非目标节点均有：h1（n）≤h2（n）≤h*（n）），则在具有一条从s到t的隐含状态图上，搜索结束时，由A2扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。A*算法应用实例-8数码问题A*算法应用实例-8数码问题A*算法应用实例-8数码问题A*算法应用实例-8数码问题A*算法应用实例-8数码问题8数码问题搜索策略比较：小结作业: