重排九宫的深度优先搜索第23页，共54页，星期日，2025年，2月5日深度优先搜索的特点在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。本质：以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。第24页，共54页，星期日，2025年，2月5日6.2.4有界深度优先搜索基本思想：对深度优先搜索引入搜索深度的界限（设为dm），当搜索深度达到了深度界限，而仍未出现目标节点时，就换一个分支进行搜索。搜索过程：把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。如果OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n的深度d(n)=dm，则转第2步（此时节点n位于CLOSE表，但并未进行扩展）。若节点n不可扩展，则转第2步。扩展节点n，将其子节点放入OPEN表的首部，为每一个子节点都配置指向父节点的指针，将每一个子节点的深度设置为d(n)+1，然后转第2步。第25页，共54页，星期日，2025年，2月5日如果问题有解，且其路径长度≤dm，则上述搜索过程一定能求得解。但是，若解的路径长度dm,则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。第26页，共54页，星期日，2025年，2月5日有界深度优先搜索的一些改进方法先任意设定一个较小的数作为dm，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限dm仍未发现目标节点，并且CLOSE表中仍有待扩展节点时，就将这些节点送回OPEN表，同时增大深度界限dm，继续向下搜索。如此不断地增大dm，只要问题有解，就一定可以找到它。但此时找到的解不一定是最优解。为了找到最优解，可增设一个表R，每找到目标节点Sg后，就把它放入到R的前面，并令dm等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以后求得的解一定是最优解。第27页，共54页，星期日，2025年，2月5日重排九宫的有界深度优先搜索设深度界限dm＝4第28页，共54页，星期日，2025年，2月5日6.2.5代价树的广度优先搜索边上标有代价(或费用)的树称为代价树。用g(x)表示从初始节点S0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)基本思想： 每次从OPEN表中选择节点往CLOSE表传送时，总是选择其中代价最小的节点。也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面。如果问题有解，代价树的广度优先搜索一定可以求得解，并且求出的是最优解。该算法应用的条件:该算法是针对代价树的算法。为了采用该算法对图进行搜索，必须先将图转换为代价树。转换方法见例6.7。第29页，共54页，星期日，2025年，2月5日代价树广度优先搜索过程把初始节点S0放入OPEN表，令g(S0)=0。如果OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n不可扩展，则转第2步。扩展节点n，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放入OPEN表中。按各节点的代价对OPEN表中的全部节点进行排序(按从小到大的顺序)，然后转第2步。第30页，共54页，星期日，2025年，2月5日代价树示例(例6.7)第31页，共54页，星期日，2025年，2月5日6.2.6代价树的深度优先搜索搜索过程：把初始节点S0放入OPEN表，令g(S0)=0。如果OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n不可扩展，则转第2步。扩展节点n，将其子节点按代价从小到大的顺序放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。代价树的深度有限搜索是不完备的。第32页，共54页，星期日，2025年，2月5日总结1、上述各种搜索方法的本质是，以初始节点为根节点，按照