1、 启发式搜索一般优于盲目搜索，但启发式搜索一般优于盲目搜索，但不能过于追求更多的甚至更完整的启不能过于追求更多的甚至更完整的启发信息。应综合考虑各种因素，尽量发信息。应综合考虑各种因素，尽量使搜索系统的总开销较小。使搜索系统的总开销较小。4.1 状态空间的搜索策略状态空间的搜索策略4.2 与与/或树的搜索策略或树的搜索策略4.1 状态空间的搜索策略状态空间的搜索策略一般搜索过程的数据结构一般搜索过程的数据结构状态节点状态节点父节点父节点编号编号状态节点状态节点父节点父节点一般搜索过程算法流程一般搜索过程算法流程 建立只含有初始节点建立只含有初始节点S的的搜索图搜索图G，把，把S放到放到OPEN
2、表中；表中；建立建立CLOSED表，其初始值为空表；表，其初始值为空表；若若OPEN表是空表，则失败退出；表是空表，则失败退出；选择选择OPEN表中第一个节点，把它从表中第一个节点，把它从OPEN表移出并放进表移出并放进CLOSED表中，称此节点为节点表中，称此节点为节点n；若若n为目标节点，则有解并成功退出，解是追踪图为目标节点，则有解并成功退出，解是追踪图G中沿中沿指针指针从从n到到S这条路径得到（指针在第这条路径得到（指针在第步中设置）；步中设置）；扩展扩展n，生成不是，生成不是n的祖先的那些后继节点的集合的祖先的那些后继节点的集合M，把，把M的这些成员作为的这些成员作为n的后继节点添入
3、图的后继节点添入图G中；中；一般搜索过程算法流程一般搜索过程算法流程 对对M中子节点进行如下处理：中子节点进行如下处理：l对没在对没在G中出现过的（即没在中出现过的（即没在OPEN或或CLOSED表中出现表中出现过的）过的）M成员设置一个指向成员设置一个指向n的指针，把的指针，把M的这些成员加的这些成员加进进OPEN表；表；l已在已在OPEN或或CLOSED表中的每个表中的每个M成员，确定是否需要成员，确定是否需要更改指向更改指向n的指针方向；的指针方向；l已在已在CLOSED表中的每个表中的每个M成员，确定是否需要更改图成员，确定是否需要更改图G中它的每个后裔节点指向父节点的指针。中它的每个
4、后裔节点指向父节点的指针。按某种方式或按某个试探值，重排按某种方式或按某个试探值，重排OPEN表；表；转第转第步。步。3.1.3 一般搜索过程一般搜索过程一般搜索过程的几点说明一般搜索过程的几点说明1.搜索过程具有通用性搜索过程具有通用性此后讨论的各种搜索策略都可以看成是它的特例。此后讨论的各种搜索策略都可以看成是它的特例。各种搜索策略的各种搜索策略的主要区别在于：主要区别在于：步骤步骤对对OPEN表上的节点进行排序的准则表上的节点进行排序的准则，以便选出一个，以便选出一个“最好最好”的节点作为步骤的节点作为步骤扩展使用。扩展使用。l排序可以是任意的，即肓目的排序可以是任意的，即肓目的盲目搜索
5、。盲目搜索。l可以用启发信息为依据可以用启发信息为依据启发式搜索。启发式搜索。一般搜索过程的几点说明一般搜索过程的几点说明2.搜索图和搜索树搜索图和搜索树l图搜索的一般过程中生成的明确图，被称为搜索图图搜索的一般过程中生成的明确图，被称为搜索图G。l由图由图G中所有节点及反向指针（在第中所有节点及反向指针（在第步步形成的指向父节形成的指向父节点的指针）构成的集合点的指针）构成的集合T，是一棵树，称为搜索树。，是一棵树，称为搜索树。扩展某节点时图扩展某节点时图G已保存了从初始节点到该节点的搜索树。已保存了从初始节点到该节点的搜索树。G中每个节点（中每个节点（S除外）都有且仅有一个指向除外）都有且
6、仅有一个指向G中一个父节点中一个父节点的指针。的指针。OPEN表上的节点都是搜索图上未被扩展的端节点。表上的节点都是搜索图上未被扩展的端节点。CLOSED表上的节点，或者是已被扩展但没有生成后继节表上的节点，或者是已被扩展但没有生成后继节点的端节点，点的端节点，或者是搜索树的非端节点。或者是搜索树的非端节点。一般搜索过程的几点说明一般搜索过程的几点说明3.搜索过程终止条件搜索过程终止条件l在第在第步，当被选作扩展的节点是目标节点时，搜索过程步，当被选作扩展的节点是目标节点时，搜索过程成功结束，得到了一个解。成功结束，得到了一个解。从目标节点按指向父节点的指针（第从目标节点按指向父节点的指针（第
7、步形成）不断回溯，步形成）不断回溯，能重现从初始节点到目标节点的成功路径。能重现从初始节点到目标节点的成功路径。解是由从初始节点到该目标节点路径上的算符构成。解是由从初始节点到该目标节点路径上的算符构成。l当搜索树不再有末被扩展的端节点时，即当搜索树不再有末被扩展的端节点时，即OPEN表为空，表为空，搜索过程失败，从初始节点达不到目标节点。搜索过程失败，从初始节点达不到目标节点。一般搜索过程的几点说明一般搜索过程的几点说明4.步骤步骤的说明的说明 一个节点经一个算符操作通常指生成一个子节点。一个节点经一个算符操作通常指生成一个子节点。由于适用于一个节点的算符可能有多个，此时就会由于适用于一个节
8、点的算符可能有多个，此时就会生成一组子节点。生成一组子节点。判断子节点是否是当前扩展节点的父节点、祖父节判断子节点是否是当前扩展节点的父节点、祖父节点等，若是，则删除。点等，若是，则删除。余下的子节点记做集合余下的子节点记做集合M，加入图，加入图G中。中。扩展节点时，生成该节点的所有后继节点。扩展节点时，生成该节点的所有后继节点。一般搜索过程的几点说明一般搜索过程的几点说明5.步骤步骤的说明的说明l问题：问题：一个新生成的节点，若已作为其他节点的后继节点被一个新生成的节点，若已作为其他节点的后继节点被生成过，该新节点应作为哪个节点的后继节点？生成过，该新节点应作为哪个节点的后继节点？l解决方法
9、：解决方法：一般由初始节点到该节点路径上所付出的一般由初始节点到该节点路径上所付出的代价代价来决定，来决定，那条路经付出的代价小，相应的节点就作为父节点。那条路经付出的代价小，相应的节点就作为父节点。常见的几种盲目搜索策略常见的几种盲目搜索策略从初始节点开始，逐从初始节点开始，逐层对节点进行扩展，并考层对节点进行扩展，并考察它是否为目标节点。察它是否为目标节点。在第在第n层节点没有全部层节点没有全部扩展并考察之前，不对第扩展并考察之前，不对第n+1层的节点进行扩展。层的节点进行扩展。算法流程算法流程 把起始节点放到把起始节点放到OPEN表中，如果该起始节点为一目标表中，如果该起始节点为一目标节
10、点，则求得一个解答。节点，则求得一个解答。若若OPEN是空表，则没有解，失败退出；否则继续。是空表，则没有解，失败退出；否则继续。把第一个节点（节点把第一个节点（节点n）从）从OPEN表移出，并把它放入表移出，并把它放入CLOSED的扩展节点表中。的扩展节点表中。扩展扩展n。如果没有后继节点，则转向步骤。如果没有后继节点，则转向步骤。把把n的所有后继节点放到的所有后继节点放到OPEN表的末端，并提供从这些表的末端，并提供从这些后继节点回到后继节点回到n的指针。的指针。如果如果n的任一个后继节点是个目标节点，则找到一个解的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向步骤答，成功
11、退出；否则转向步骤；3.1.4 盲目搜索策略盲目搜索策略删除删除OPEN或或CLOSED表中出现过的子状态，避免表中出现过的子状态，避免循环搜索。循环搜索。只要问题有解，只要问题有解，总能找到最短解题路径总能找到最短解题路径。如果问题无解，对有限图，算法会失败退出；对无如果问题无解，对有限图，算法会失败退出；对无限图，则永远不会终止。限图，则永远不会终止。盲目性较大盲目性较大，当目标节点距初始节点较远，会产生许多，当目标节点距初始节点较远，会产生许多无用节点，无用节点，搜索效率低搜索效率低。因此，当图中分枝数太多，实。因此，当图中分枝数太多，实用意义不大。用意义不大。代价树的宽度优先搜索算法代
12、价树的宽度优先搜索算法启发式搜索算法启发式搜索算法代价树的宽度优先搜索算法的引入代价树的宽度优先搜索算法的引入例：城市交通问题。例：城市交通问题。设有设有5个城市个城市,它们之间的交它们之间的交通路线如图所示，图中的数字通路线如图所示，图中的数字表示两个城市之间的交通费用，表示两个城市之间的交通费用，即代价。即代价。求从求从A市出发到市出发到E市，费用最市，费用最小的交通路线。小的交通路线。结论：在搜索树中给每条边结论：在搜索树中给每条边都标上代价都标上代价。生成代价树的方法生成代价树的方法从初始节点从初始节点A开始，把与开始，把与A直接相邻的节点作为子节点。直接相邻的节点作为子节点。对其他节
13、点作相同处理。对其他节点作相同处理。若一个节点已是某节点的若一个节点已是某节点的直系先辈节点，就不能再作为直系先辈节点，就不能再作为该节点的子节点。该节点的子节点。除除A外，其它节点可能在外，其它节点可能在代价树中多次出现。为便于区代价树中多次出现。为便于区分，用下标分，用下标1,2,标出。标出。相关记号相关记号若节点若节点j是是i的子女，的子女，c(i,j)：从从i到到j的连接弧线代价。的连接弧线代价。g(i)：从起始节点从起始节点S到到i的路径代价，即从的路径代价，即从S到到i的最少代价的最少代价路径上的代价。路径上的代价。g(j)=g(i)+c(i,j)代价树的宽度优先搜索算法流程代价树
14、的宽度优先搜索算法流程 把起始节点把起始节点S放到未扩展节点表放到未扩展节点表OPEN中。如果中。如果S为一目为一目标节点，则求得一个解；否则令标节点，则求得一个解；否则令g(S)=0。如果如果OPEN是个空表，则没有解，失败退出。是个空表，则没有解，失败退出。把把OPEN表中第一个节点表中第一个节点n取出，放入取出，放入CLOSED表。表。如果如果n是目标节点，则求得问题的解，退出。是目标节点，则求得问题的解，退出。若若n不可扩展，则转第不可扩展，则转第(2)步。步。扩展扩展n，将其子节点放入，将其子节点放入OPEN表，并配置指向父节点的表，并配置指向父节点的指针；计算各子节点的代价，指针；
15、计算各子节点的代价，按代价对按代价对OPEN表中全部表中全部节点从小到大进行排序节点从小到大进行排序，然后转第，然后转第步。步。代价树的宽度优先搜索示例代价树的宽度优先搜索示例状态节点状态节点AC1B1B1D1D2E1D1E1D1E3C2状态节点状态节点AC1AB1C1AD2B1C1AE1D2B1C1A从初始节点开始，从初始节点开始，搜索一旦进入某个分支，就沿着该分支一直向下搜索。搜索一旦进入某个分支，就沿着该分支一直向下搜索。如果目标节点不在此分支上，且该分支又是一个无穷分如果目标节点不在此分支上，且该分支又是一个无穷分支，则不可能得到解。支，则不可能得到解。因此，深度优先搜索是不完备的。因
16、此，深度优先搜索是不完备的。为了防止搜索沿着一条路径无限地扩展下去，深度优先为了防止搜索沿着一条路径无限地扩展下去，深度优先搜索常设定搜索常设定深度限制值深度限制值，即有界深度优先搜索。，即有界深度优先搜索。节点深度定义节点深度定义l起始节点（即根节点）的深度为起始节点（即根节点）的深度为0。l其他节点的深度等于其父节点的深度加其他节点的深度等于其父节点的深度加1。深度界限深度界限l为避免考虑太长路径，防止搜索沿着无益路径扩展，往往为避免考虑太长路径，防止搜索沿着无益路径扩展，往往给出一个节点扩展的最大深度，称为深度界限。给出一个节点扩展的最大深度，称为深度界限。l若达到深度界限，对任何节点都
17、认为它们没有后继节点。若达到深度界限，对任何节点都认为它们没有后继节点。采用深度界限后，解答路径也不一定是最短路径。采用深度界限后，解答路径也不一定是最短路径。有界深度优先搜索算法流程有界深度优先搜索算法流程 把起始节点把起始节点S放到放到OPEN表中。如果此节点为目标节点，表中。如果此节点为目标节点，则得到一个解。则得到一个解。如果如果OPEN为空表，则失败退出。为空表，则失败退出。把第一个节点（节点把第一个节点（节点n）从）从OPEN表移到表移到CLOSED表。表。如果如果n的深度等于最大深度的深度等于最大深度dm，则转向步骤，则转向步骤。扩展扩展n，产生其全部后裔，并把它们放入，产生其全
18、部后裔，并把它们放入OPEN表的前头。表的前头。如果没有后裔，则转向步骤如果没有后裔，则转向步骤。如果后继节点中有任一个为目标节点，则求得一个解，如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向步骤成功退出；否则，转向步骤。有界深度优先搜索的几点说明有界深度优先搜索的几点说明如果问题有解，且路径长度如果问题有解，且路径长度 dm，则上述搜索过程一，则上述搜索过程一定能求得解。但若解的路径长度定能求得解。但若解的路径长度 dm，则得不到解。，则得不到解。为找到最优解，可增设表为找到最优解，可增设表R，每找到一个目标节点，每找到一个目标节点Sg后，就把它放到后，就把它放到R的前
19、面，并令的前面，并令dm等于该目标节点所对应等于该目标节点所对应的路径长度，然后继续搜索。的路径长度，然后继续搜索。代价树的深度优先搜索算法流程代价树的深度优先搜索算法流程 把起始节点把起始节点S放到未扩展节点表放到未扩展节点表OPEN中。如果中。如果S为一目为一目标节点，则求得一个解；否则令标节点，则求得一个解；否则令g(S)=0。如果如果OPEN是个空表，则没有解，失败退出。是个空表，则没有解，失败退出。把把OPEN表中第一个节点表中第一个节点n取出，放入取出，放入CLOSED表。表。如果如果n是目标节点，则求得问题的解，退出。是目标节点，则求得问题的解，退出。若若n不可扩展，则转第不可扩
20、展，则转第(2)步。步。扩展扩展n，将其子节点按边代价从小到大的顺序放入，将其子节点按边代价从小到大的顺序放入OPEN表，并配置指向父节点的指针，然后转第表，并配置指向父节点的指针，然后转第步。步。代价树的深度优先搜索示例代价树的深度优先搜索示例状态节点状态节点AC1B1D1B1E2B2B1状态节点状态节点AC1AD1C1AE2D1C1A盲目搜索存在的问题盲目搜索存在的问题扩展节点数目较多。扩展节点数目较多。效率低，耗费过多的计算时间和空间。效率低，耗费过多的计算时间和空间。解决方案：选择最有希望的节点扩展。解决方案：选择最有希望的节点扩展。的应用场合的应用场合启发式搜索可能得到一个次最佳启发
21、式搜索可能得到一个次最佳解，也可能无解，这是由其固有解，也可能无解，这是由其固有局限性决定的，不能通过局限性决定的，不能通过“更好更好”的启发式策略来克服。的启发式策略来克服。启发信息启发信息估价函数估价函数估价函数的选择估价函数的选择一个节点处在最佳路径上的概率。一个节点处在最佳路径上的概率。求出任意一个节点与目标节点集之间的距离度量或差异求出任意一个节点与目标节点集之间的距离度量或差异度量。度量。根据格局（如博弈问题）或状态的特点来计算。根据格局（如博弈问题）或状态的特点来计算。有序搜索算法（有序搜索算法（A算法）的基本思想算法）的基本思想 应用某个算法选择应用某个算法选择OPEN表上具有
22、最小表上具有最小f值的节点作值的节点作为下一个要扩展的节点，这种搜索方法叫做有序搜索为下一个要扩展的节点，这种搜索方法叫做有序搜索（最佳优先搜索）。（最佳优先搜索）。有序搜索总是选择最有希望的节点作为下一个要扩有序搜索总是选择最有希望的节点作为下一个要扩展的节点。展的节点。有序搜索算法流程有序搜索算法流程 把起始节点把起始节点S放到放到OPEN表中，计算表中，计算f(S)，并把值与，并把值与S联系联系起来。起来。如果如果OPEN表是个空表，则失败退出，无解。表是个空表，则失败退出，无解。从从OPEN表中选择一个表中选择一个f值最小的节点值最小的节点i。如果有多个节点。如果有多个节点满足这一要求
23、，且其中有一个为目标节点，则选择它作满足这一要求，且其中有一个为目标节点，则选择它作为为i；否则就选择其中任意一个节点作为；否则就选择其中任意一个节点作为i。把把i 从从OPEN表中移出，并放入表中移出，并放入CLOSED表中。表中。如果如果i是个目标节点，则成功退出，求得一个解。是个目标节点，则成功退出，求得一个解。有序搜索算法流程有序搜索算法流程 扩展扩展i，生成其全部后继节点。对，生成其全部后继节点。对i的每个后继节点的每个后继节点j：a)计算计算f(j)。b)如果如果j不在不在OPEN和和CLOSED表中，则用表中，则用f(j)把它添入把它添入OPEN表，并为表，并为j设置指向设置指向
24、i的指针。的指针。c)若若j已在已在OPEN或或CLOSED表上，则比较表上，则比较f(j)和前面计算过的和前面计算过的该节点在表中的该节点在表中的f(j)old值。若值。若f(j)较小，则：较小，则：I.以以f(j)取代取代f(j)old。II.修正修正j的父指针，使其指向的父指针，使其指向i。III.若若j在在CLOSED表中，把它移回表中，把它移回OPEN表。表。转向转向。有序搜索算法的几点说明有序搜索算法的几点说明宽度优先算法搜索是它的特例，此时宽度优先算法搜索是它的特例，此时f(i)为节点为节点i的深度。的深度。f(i)定义为从起始节点至定义为从起始节点至i的代价，则退化为代价树的宽
25、度的代价，则退化为代价树的宽度优先搜索。优先搜索。f的选择直接决定了有序搜索中被扩展节点的数目，即直的选择直接决定了有序搜索中被扩展节点的数目，即直接影响了搜索算法效率，对搜索结果具有决定性作用。接影响了搜索算法效率，对搜索结果具有决定性作用。f*(n)=g*(n)+h*(n)：l称为从节点称为从节点n到目标节点的最小代价。到目标节点的最小代价。lg*(n)=k(S,n)：从初始节点从初始节点S到节点到节点n的最小代价。的最小代价。k(ni,nj)：表示任意两个节点表示任意两个节点ni和和nj之间最小代价路径的实际代之间最小代价路径的实际代价（对于两节点间没有通路的节点，函数价（对于两节点间没
26、有通路的节点，函数k没有定义）。没有定义）。lh*(n)：表示整个目标节点集合表示整个目标节点集合ti上所有上所有k(n,ti)中最小的一中最小的一个个,即从节点即从节点n 到目标节点最优路径的实际代价。到目标节点最优路径的实际代价。定义：定义：在在A算法中，如果对所有的算法中，如果对所有的n存在存在h(n)h*(n)，则称，则称h(n)为为h*(n)的下界。的下界。A*算法：算法：在在A算法，采用算法，采用h*(n)的下界的下界h(n)为启发函数，即对任为启发函数，即对任意的节点意的节点n均有：均有：h(n)h*(n)，且，且g(n)是对是对g*(n)的估计，的估计，g(n)0，则算法成为，
27、则算法成为A*算法。算法。把把S放入放入OPEN表，记表，记f=h，令，令CLOSED为空表。为空表。重复下列过程，直至找到目标节点为止。若重复下列过程，直至找到目标节点为止。若OPEN表为表为空，则失败退出。空，则失败退出。选取选取OPEN表中未设置过的具有最小表中未设置过的具有最小f值的节点为最佳节值的节点为最佳节点点BESTNODE，并把它放入，并把它放入CLOSED表。表。若若BESTNODE为目标节点，则成功求解。为目标节点，则成功求解。若若BESTNODE不是目标节点，则扩展产生后继节点不是目标节点，则扩展产生后继节点SUCCESSOR。对每个对每个SUCCESSOR进行下列过程：
28、进行下列过程：3.1.5.3 a)建立从建立从SUCCESSOR返回返回BESTNODE的指针。的指针。b)计算计算g(SUC)=g(BES)+k(BES,SUC)。c)如果如果SUCCESSOR OPEN，则称此节点为，则称此节点为OLD，把它添至，把它添至BESTNODE的后继节点表中。的后继节点表中。d)比较新旧路径代价。若比较新旧路径代价。若g(SUC)g(OLD)，则重新确定，则重新确定OLD的的父亲节点为父亲节点为BESTNODE，记下较小代价，记下较小代价g(OLD)，并修正，并修正f(OLD)值。值。e)若至若至OLD节点的代价较低或一样，则停止扩展节点。节点的代价较低或一样，
29、则停止扩展节点。f)若若SUCCESSOR不在不在CLOSE表，则看其是否在表，则看其是否在CLOSED表中表中g)若若SUCCESSOR在在CLOSE表中，则转向表中，则转向(c)。h)若若SUCCESSOR不在不在OPEN表和表和CLOSED表中，则把它放入表中，则把它放入OPEN表中，并添入表中，并添入BESTNODE后裔表，然后转向后裔表，然后转向(7)。计算计算f值，转第值，转第(2)步。步。3.1.5.3 八数码难题八数码难题定义如下两种估价函数：定义如下两种估价函数：构成两个构成两个A*算法算法A1*和和A2*A1*：lh1(n)：“不在位不在位”的棋子数的棋子数lg1(n)：实际走的步数（节点深度）：实际走的步数（节点深度）A2*：lh2(n)：所有棋子偏离目标位置的距离总和：所有棋子偏离目标位置的距离总和lg2(n)：实际走的步数（节点深度）：实际走的步数（节点深度）有：有：h1(n)h2(n)3.1.5.3
