《人工智能搜索策略-优质ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能搜索策略-优质ppt课件.ppt（94页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、搜 索 策 略 搜索问题，人工智能的一个基本问题l在二十世纪五十年代人工智能概念的提出至今，人在二十世纪五十年代人工智能概念的提出至今，人工智能界已对搜索技术开展了大量研究，取得了丰工智能界已对搜索技术开展了大量研究，取得了丰硕的成果。硕的成果。 l搜索是人工智能的一个基本问题，是推理不可分割搜索是人工智能的一个基本问题，是推理不可分割的一部分。一个问题的求解过程其实就是搜索过程，的一部分。一个问题的求解过程其实就是搜索过程，所以所以搜索实际上就是求解问题的一种方法搜索实际上就是求解问题的一种方法。lNilsson把搜索列为把搜索列为人工智能研究中的四个核心问人工智能研究中的四个核心问题题之一
2、。之一。l本部分将讨论本部分将讨论目标状态和最优路径的确定目标状态和最优路径的确定，以及，以及如如何从初始状态经过变换得到目标状态何从初始状态经过变换得到目标状态等，将在各节等，将在各节分别讨论一些分别讨论一些通用的搜索策略通用的搜索策略，以及，以及状态空间搜索状态空间搜索和和树搜索策略树搜索策略。最后简要介绍智能搜索算法的效率。最后简要介绍智能搜索算法的效率和约束满足问题。和约束满足问题。 现实世界中的大多数问题都是非结构化问题，现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前
3、进。只能利用已有的知识一步一步地摸索着前进。 在这一过程中，所要解决的问题是如何寻找可在这一过程中，所要解决的问题是如何寻找可利用的知识，即利用的知识，即如何确定推理路线如何确定推理路线，才能使在付出，才能使在付出尽量少的代价下把问题圆满解决。尽量少的代价下把问题圆满解决。 如果存在多条路线可实现对问题的求解，那就如果存在多条路线可实现对问题的求解，那就又存在着这样的问题，即又存在着这样的问题，即如何从这多条求解路线中，如何从这多条求解路线中，选出一条使它的求解代价最小，以提高求解程序的选出一条使它的求解代价最小，以提高求解程序的运行效率运行效率。 根据问题的实际情况，按照一定的策略或规则，根
4、据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条解从知识库中寻找可利用的知识，从而构造出一条解决问题的推理路线的过程，就称为决问题的推理路线的过程，就称为搜索搜索。1.搜索包含两层含义搜索包含两层含义l找到从初始事实到问题最终答案的一条推理路线找到从初始事实到问题最终答案的一条推理路线;l找到的这条路线是时间和空找到的这条路线是时间和空 间复杂度最小的求解路间复杂度最小的求解路线。线。v举一个具体的例子举一个具体的例子 实现一个能够中国象棋下棋的程序。实现一个能够中国象棋下棋的程序。3.1.1 什么是搜索什么是搜索 (Whats search)2.搜索的种类搜
5、索的种类(The type of search) 搜索分为盲目搜索和启发式搜索两种搜索分为盲目搜索和启发式搜索两种l盲目搜索又称无信息搜索盲目搜索又称无信息搜索，也就是说，在搜索过程，也就是说，在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。这就使得这有任何中间信息来改变这些控制策略。这就使得这样的搜索带有盲目性，效率不高。盲目搜索只用于样的搜索带有盲目性，效率不高。盲目搜索只用于解决比较简单的问题。解决比较简单的问题。l启发式搜索又称有信息搜索启发式搜索又称有信息搜索，它是指在搜索求解过，它是指在搜索求解过程
6、中，根据问题本身的特性或搜索过程中产生的一程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到着最有希望的方向前进，加速问题的求解，并找到最优解。最优解。 3.1.1 什么是搜索什么是搜索 (Whats search)v问题求解系统可在问题求解系统可在两种基本情况下运用启发式策略两种基本情况下运用启发式策略：1.一个问题由于在一个问题由于在问题陈述和数据获取方面固有的模糊性问题陈述和数据获取方面固有的模糊性，可，可能会使它能会使它没有一个确定的解没有一个确定的解，即它是一
7、个模糊系统。，即它是一个模糊系统。2.虽然一个问题可能有确定解，但是虽然一个问题可能有确定解，但是求解过程中的搜索代价将求解过程中的搜索代价将令人难以接受令人难以接受，在很多问题中，其状态空间特别大，搜索中，在很多问题中，其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。在这种生成扩展的状态数会随着搜索的深度呈指数级增长。在这种情况下，情况下，穷尽式搜索策略穷尽式搜索策略如宽度优先和深度优先搜索，在一如宽度优先和深度优先搜索，在一个给定的较实际的时空内很可能得不到最终的解，而个给定的较实际的时空内很可能得不到最终的解，而启发式启发式策略则通过引导搜索向最有希望的方向进行来降
8、低搜索复杂策略则通过引导搜索向最有希望的方向进行来降低搜索复杂度度。通过仔细考虑，删除某些状态及其后裔，启发式策略可。通过仔细考虑，删除某些状态及其后裔，启发式策略可以消除组合爆炸，并得到令人能接受的解。以消除组合爆炸，并得到令人能接受的解。3.1.1 什么是搜索什么是搜索 (Whats search)3.1.1 什么是搜索什么是搜索 (Whats search)v启发式策略的缺点：启发式策略的缺点：l 极易出错。在解决问题过程中极易出错。在解决问题过程中启发仅仅是下一步启发仅仅是下一步将要采取措施的一个猜想将要采取措施的一个猜想，它常常根据经验和直觉，它常常根据经验和直觉来判断。来判断。l
9、由于启发式搜索由于启发式搜索只利用特定问题的有限的信息只利用特定问题的有限的信息，如当前如当前open表中状态的描述及其之间的关系，表中状态的描述及其之间的关系，要想要想准确地预测下一步在状态空间中采取的具体的搜索准确地预测下一步在状态空间中采取的具体的搜索行为是很难办到的行为是很难办到的。一个启发式搜索可能得到一个一个启发式搜索可能得到一个次最佳解，也可能一无所获次最佳解，也可能一无所获，这是启发式搜索固有，这是启发式搜索固有的局限性，而这种局限性不可能由所谓更好的启发的局限性，而这种局限性不可能由所谓更好的启发式策略或更有效的搜索算法来彻底消除。式策略或更有效的搜索算法来彻底消除。3.1.
10、2 适合于搜索的知识表示方法适合于搜索的知识表示方法 状态空间表示法：状态空间表示法： 算符、状态、状态空间算符、状态、状态空间与或树表示法：与或树表示法： 分解、等价变化；本原问题、分解、等价变化；本原问题、端节点与终止端节点与终止节点、可解节点、不可解节点、解树节点、可解节点、不可解节点、解树状态空间搜索策略分类：状态空间搜索策略分类：l盲目搜索盲目搜索 按事先规定好的路线进行搜索，不使用按事先规定好的路线进行搜索，不使用与问题有关的启发性信息；适用于其状态空间图是与问题有关的启发性信息；适用于其状态空间图是树状结构的一类问题。它包括树状结构的一类问题。它包括广度优先搜索广度优先搜索、深度
11、深度优先搜索、有界深度优先搜索优先搜索、有界深度优先搜索、代价树的广度优先代价树的广度优先搜索搜索以及以及代价树的深度优先搜索代价树的深度优先搜索。l启发式搜索启发式搜索搜索过程中使用与问题有关的启发搜索过程中使用与问题有关的启发性信息，并以启发性信息指导搜索过程；可以高效性信息，并以启发性信息指导搜索过程；可以高效地求解结构复杂的问题。它包括地求解结构复杂的问题。它包括局部择优搜索局部择优搜索、全全局择优搜索局择优搜索和和A*算法算法。3.2 状态空间的搜索策略状态空间的搜索策略3.2.1 状态空间的一般搜索过程状态空间的一般搜索过程1.状态空间图状态空间图 状态空间图是一个有向图，当把一个
12、待求解状态空间图是一个有向图，当把一个待求解的问题表示为状态空间以后，就可以通过对状的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。如果从状态空间的搜索，实现对问题的求解。如果从状态空间图的角度来看，则对问题的求解就相当态空间图的角度来看，则对问题的求解就相当于于 在有向图上寻找一条从某一节点在有向图上寻找一条从某一节点(初始状态初始状态节点节点)到另一节点到另一节点(目标状态节点目标状态节点)的路径的路径。3.2.1 状态空间的一般搜索过程状态空间的一般搜索过程2.状态空间搜索法求解问题的基本思想状态空间搜索法求解问题的基本思想 首先首先将问题的初始状态将问题的初始状
13、态(即状态空间图中的初始节即状态空间图中的初始节点点)当作当前状态，选择适当的算符作用于当前状态，当作当前状态，选择适当的算符作用于当前状态，生成一组后继状态生成一组后继状态(或称后继节点或称后继节点)， 然后然后检查这组后继状态中有没有目标状态。检查这组后继状态中有没有目标状态。如果有如果有，则说明搜索成功，从初始状态到目标状，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；态的一系列算符即是问题的解；若没有若没有，则按照某种控制策略从已生成的状态中，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，再选一个状态作为当前状态，重复上述过程，直到目标状态出
14、现或不再有可供操作的状态及直到目标状态出现或不再有可供操作的状态及算符时为止。算符时为止。3.状态空间的搜索过程需要的两个数据结构状态空间的搜索过程需要的两个数据结构 OPEN表：表：用于存放刚生成的节点，这些节点也是待扩展的，用于存放刚生成的节点，这些节点也是待扩展的，所以所以OPEN表也称为未扩展节点表；表也称为未扩展节点表； CLOSED表：表：CLOSED表则是用来存放将要扩展或已经扩展表则是用来存放将要扩展或已经扩展的节点，所以它被称为已扩展节点表。的节点，所以它被称为已扩展节点表。4.状态空间的一般搜索过程描述如下状态空间的一般搜索过程描述如下:1)把初始节点把初始节点S0放入放入
15、OPEN表，并建立目前只包含表，并建立目前只包含S0的图，记的图，记为为G；2)检查检查OPEN表是否为空，若为空则问题无解，退出。表是否为空，若为空则问题无解，退出。3)把把 OPEN 表的第一个节点取出并放入表的第一个节点取出并放入 CLOSED 表，并记该表，并记该节点为节点节点为节点 n；4)检查节点检查节点 n 是否是目标节点，如果是目标节点，则说明得到是否是目标节点，如果是目标节点，则说明得到了问题的解，过程成功退出，并返回从节点了问题的解，过程成功退出，并返回从节点 n 逆向回溯到逆向回溯到S0得出的路径；得出的路径；3.2.1状态空间的一般搜索过程状态空间的一般搜索过程5)扩展
16、节点扩展节点n，生成一组子节点。把其中生成一组子节点。把其中不是节点不是节点n先辈的那先辈的那些子节点记做集合些子节点记做集合M，并把这些子节点作为节点并把这些子节点作为节点n的子节的子节点加入点加入G中。中。6) 针对针对M中子节点的不同情况，分别进行如下处理：中子节点的不同情况，分别进行如下处理：对于那些未曾在对于那些未曾在G 图中出现过的图中出现过的 M 成员设置一个指向父成员设置一个指向父节点（即节点节点（即节点n）的指针，并把它们加入的指针，并把它们加入 OPEN 表表对于那些先前已在对于那些先前已在G图中出现过的图中出现过的M成员，确定是否需要成员，确定是否需要修改它指向父节点的指
17、针。修改它指向父节点的指针。对于那些先前已在对于那些先前已在G中出现并且已经扩展了的中出现并且已经扩展了的M成员，确成员，确定是否需要修改其后继节点指向父节点的指针。定是否需要修改其后继节点指向父节点的指针。7)按某种搜索策略对按某种搜索策略对OPEN表中的节点进行排序。表中的节点进行排序。8)转第转第2）步。）步。3.2.1状态空间的一般搜索过程状态空间的一般搜索过程S0S1S2S3S4S5S6S7S8S9S10S11S12S13S14S9扩展之后生成的子节点扩展之后生成的子节点有有S1,S6,S12,S13。但是，。但是，S1是是S9的祖先节点，所以的祖先节点，所以S9的子集的子集M=S6
18、,S12,S13其中，其中，S13满足第满足第1种情况；种情况；S12满第满第2种情况；种情况；S6满足第满足第3种情况。种情况。下面对上述过程作一些说明：下面对上述过程作一些说明：1) 上述过程是状态空间的一般搜索过程，具有通用性，在此之上述过程是状态空间的一般搜索过程，具有通用性，在此之后讨论的各种搜索策略都可看作是它的一个特例。各种搜索后讨论的各种搜索策略都可看作是它的一个特例。各种搜索策略的主要区别是策略的主要区别是对对 OPEN 表中节点排序的准则不同表中节点排序的准则不同。 例如例如广度优先搜索把先生成的子节点排在前面，而深度优先搜索广度优先搜索把先生成的子节点排在前面，而深度优先
19、搜索则把后生成的子节点排在前面。则把后生成的子节点排在前面。2) 一个节点经一个算符操作后一般只生成一个子节点一个节点经一个算符操作后一般只生成一个子节点，但适，但适用用于一个节点的算符可能有多个于一个节点的算符可能有多个，此时就会生成一组子节点。，此时就会生成一组子节点。在这些子节点中可能有些是当前扩展节点在这些子节点中可能有些是当前扩展节点 ( 即节点即节点n)的父节点，的父节点，祖父节点等，此时不能把这些先辈节点作为当前扩展节点的祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。余下的子节点记作集合子节点。余下的子节点记作集合M，并加入图，并加入图 G 中。这就是中。这就是第第
20、 5) 步要说明的意思。步要说明的意思。3) 一个新生成的节点，它可能是第一次被生成的节点，也可能一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的后继节点被生成过，当前又作为另是先前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节点被再次生成。此时，它究竟应作为哪个一个节点的后继节点被再次生成。此时，它究竟应作为哪个节点的后继节点呢？节点的后继节点呢？一般由原始节点到该节点路径上所付出一般由原始节点到该节点路径上所付出的代价来决定，哪条路径付出的代价小，相应的节点就作为的代价来决定，哪条路径付出的代价小，相应的节点就作为它的父节点它的父节点。 4) 通过
21、搜索所得到的图称为搜索图，由搜索图中的所有通过搜索所得到的图称为搜索图，由搜索图中的所有节点及反向指针节点及反向指针(在第在第6)步形成的指向父节点的指针步形成的指向父节点的指针) )所所构成的集合是一棵树，称为搜索树。构成的集合是一棵树，称为搜索树。5) 在搜索过程中，一旦某个被考察的节点是目标节点在搜索过程中，一旦某个被考察的节点是目标节点 (第第5)步步)就得到了一个解。该解是由从初始节点到该目就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成的，而路径由第标节点路径上的算符构成的，而路径由第7) 步形成的步形成的反向指针指定。反向指针指定。6) 如果在搜索中一直找不到目标节
22、点，而且如果在搜索中一直找不到目标节点，而且 OPEN 表表中不再有可供扩展的节点，则搜索失败，在第中不再有可供扩展的节点，则搜索失败，在第3) 步退步退出。出。7) 由于盲目搜索仅适用于其状态空间是树状结构的问题，由于盲目搜索仅适用于其状态空间是树状结构的问题，因此对盲目搜索而言，不会出现一般搜索过程第因此对盲目搜索而言，不会出现一般搜索过程第6) 步步中，两点的问题，每个节点经扩展后生成的子节点中，两点的问题，每个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指针方向。都是第一次出现的节点，不必检查并修改指针方向。 5.搜索过程举例：搜索过程举例：1S064523实心黑点实心
23、黑点代表已扩展了节点，它代表已扩展了节点，它们位于们位于CLOSED表上；表上；空心圆圈空心圆圈代表未扩展的节点，它们位于代表未扩展的节点，它们位于OPEN表上；表上；有向边旁边的箭头有向边旁边的箭头是指向父节点的指针，它们是在是指向父节点的指针，它们是在第第 6) 步形成的。步形成的。假设现在要扩展节点假设现在要扩展节点 1，并且，并且只生成单一的后继节点只生成单一的后继节点 2 。但。但是目前节点是目前节点 2 已有父节点已有父节点 3，即节点即节点 2 在先前扩节点在先前扩节点 3 时时已被生成了，现在又作为节点已被生成了，现在又作为节点 1 的后继节点被再次生成。的后继节点被再次生成。
24、1S0645231S064523广度优先搜索又称为宽度优先搜索。广度优先搜索又称为宽度优先搜索。v基本思想是：从初始节点基本思想是：从初始节点S0开始，逐层地开始，逐层地对节点进行扩展并考察它是否为目标节点，对节点进行扩展并考察它是否为目标节点，在第在第n层的节点没有全部扩展并考察之前，层的节点没有全部扩展并考察之前， 不对第不对第n+1层的节点进行扩展。层的节点进行扩展。OPEN表中表中的节点总是按进入的先后顺序排列，先进的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。入的节点排在前面，后进入的排在后面。3.2.2 状态空间的盲目搜索状态空间的盲目搜索v广度优先搜索过
25、程广度优先搜索过程:1) 把起始节点放到把起始节点放到OPEN表中表中(如果该起始节点为一目标节点，如果该起始节点为一目标节点，则求得一个解答则求得一个解答)；2) 如果如果OPEN是个空表，则没有解，失败退出；否则继续；是个空表，则没有解，失败退出；否则继续；3) 把第一个节点把第一个节点(节点节点n)从从OPEN表移出，并把它放入表移出，并把它放入CLOSED扩展节点表中；扩展节点表中；4) 扩展节点扩展节点n。如果没有后继节点，则转向上述第。如果没有后继节点，则转向上述第 2) 步；步；5) 把把n的所有后继节点放到的所有后继节点放到OPEN表的表的末端末端，并提供从这些后继，并提供从这
26、些后继节点回到节点回到n的指针；的指针；6) 如果如果n的任一个后继节点是个目标节点，则找到一个解答，成的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第功退出；否则转向第2)步。步。 v广度优先搜索示意图：广度优先搜索示意图：v广度优先搜索举例：广度优先搜索举例：v重排九宫问题。在重排九宫问题。在33的的方格棋盘上放置分别标有方格棋盘上放置分别标有数字数字1,2,3,4,5,6,7,8的的八张牌，初始状态为八张牌，初始状态为S0，目标状态为目标状态为Sg，如图所示。如图所示。v可用的算符有四种可用的算符有四种。初始状态初始状态目标状态目标状态解路径：解路径：S0-3-8-16
27、-261234567891011121314151617181920212223 242526v缺点：盲目性大，当目标节点距离初始节点缺点：盲目性大，当目标节点距离初始节点较远时将会产生许多无用节点；搜索效率低。较远时将会产生许多无用节点；搜索效率低。v优点：是完备的。优点：是完备的。v深度优先搜索深度优先搜索 在深度优先搜索中，我们首先扩展最新产生的在深度优先搜索中，我们首先扩展最新产生的(即最深的即最深的)节点。深度相等的节点可以任意排列。节点。深度相等的节点可以任意排列。 对于许多问题，其状态空间搜索树的深度可能对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受
28、的解答序为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路列的已知深度上限还要深。为了避免考虑太长的路径径(防止搜索过程沿着无益的路径扩展下去防止搜索过程沿着无益的路径扩展下去)，往往，往往给出一个节点扩展的最大深度给出一个节点扩展的最大深度深度界限。任何深度界限。任何节点如果达到了深度界限，那么都将把它们作为没节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。有后继节点处理。示意图示意图v例：按深度优先搜索生例：按深度优先搜索生成的八数码难题搜索树成的八数码难题搜索树v其算法的基本思想与广其算法的基本思想与广度优先搜索类似，唯一度优先搜索类似，
29、唯一不同就在第不同就在第5)步中：步中： 把把n的所有后继节点放的所有后继节点放到到OPEN表的表的首部首部，并，并提供从这些后继节点回提供从这些后继节点回到到n的指针。的指针。S0123456缺点：有可能陷入无穷缺点：有可能陷入无穷分支。算法是不完备的。分支。算法是不完备的。v基本思想：对深度优先搜索引入搜索深度的基本思想：对深度优先搜索引入搜索深度的界限（设为界限（设为dm）当搜索深度达到了深度界限，）当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行而尚未出现目标节点时，就换一个分支进行搜索。搜索。v有界深度优先搜索有界深度优先搜索算法如下：算法如下：1)把起始节点把起始节
30、点S0放到未扩展节点放到未扩展节点OPEN表中，置表中，置S0的的深度为深度为d(S0)=0；2)如果如果OPEN为一空表，则失败退出；为一空表，则失败退出；3)OPEN表的第一个节点表的第一个节点(节点节点n)从从OPEN表移到表移到CLOSED表；表；4)考查结点考查结点n是否为目标节点。若是，则求得了问题是否为目标节点。若是，则求得了问题的解，退出；的解，退出；5)如果节点如果节点n的深度的深度d(节点节点n)等于最大深度等于最大深度(dm)，则，则转转2)；6)若节点若节点n不可扩展，则转第不可扩展，则转第2)步；步；7)扩展节点扩展节点n,将其子节点放入将其子节点放入OPEN表的表的
31、首部首部，并为，并为其配置指向父节点的指针。然后转第其配置指向父节点的指针。然后转第2)步。步。S012345628 3147 6 52 8 3147 652 831 47 6 52 8 3147652 8 3147652 8 3147652831 47 6 5283147 6 52 831 47 6 5283147 6 5283147 6 5283147 6 5283147 65283147 6 5283147 6 52831476 5283147 6 5v设深度界限设深度界限 dm4，用有界深度优先搜索方法求解图，用有界深度优先搜索方法求解图v由于解的路径长度事先难以预料，所以要恰由于解的
32、路径长度事先难以预料，所以要恰当地给出当地给出dm的值是比较困难的，且所求出的的值是比较困难的，且所求出的解也不一定是最优解。解也不一定是最优解。v改进方法：改进方法：先任意给定一个较小的数作为先任意给定一个较小的数作为dm ，然后进行上述的有界深度优先搜索，当搜索然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限达到了指定的深度界限dm仍未发现目标节点，仍未发现目标节点，并且并且CLOSED表中仍有待扩展节点时就将这表中仍有待扩展节点时就将这些节点送回些节点送回OPEN表，同时增大深度界限，表，同时增大深度界限，继续向下搜索。如此不断地增大继续向下搜索。如此不断地增大dm，只要问，只
33、要问题有解，就一定可以找到它。但此时找到的题有解，就一定可以找到它。但此时找到的解不一定是最优解。解不一定是最优解。v代价树代价树 边上标有代价边上标有代价(或费用或费用)的树称为代价树的树称为代价树。 g(x)表示从初始节点表示从初始节点S0到节点到节点x的代价；的代价；c(x1,x2)表表示从父结点示从父结点x1到子节点到子节点x2的代价。的代价。 g(x2)=g(x1)+ c(x1,x2)v代价树广度优先搜索代价树广度优先搜索的基本思想的基本思想: 每次从每次从 OPEN 表中选择节点往表中选择节点往 CLOSED 表传表传送时，总是选择其代价为送时，总是选择其代价为最小最小的节点。也就
34、是说，的节点。也就是说，OPEN 表中的节点在任一时刻都是按其代价表中的节点在任一时刻都是按其代价从小至从小至大大排序的，代价小的节点排在前面，代价大的节点排序的，代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。排在后面，而不管节点在代价树中处于什么位置上。搜索过程如下：搜索过程如下：(1) 把初始节点把初始节点 S0 放入放入OPEN 表，令表，令 g(S0)=0 。(2) 如果如果 OPEN 表为空，则问题无解，退出。表为空，则问题无解，退出。(3) 把把 OPEN 表的第一个节点表的第一个节点 ( 记为节点记为节点 i) 取出放取出放入入 CLOSED 表
35、。表。(4) 考察节点考察节点 i 是否为目标节点。若是，则求得了问是否为目标节点。若是，则求得了问题的解，退出。题的解，退出。(5) 若节点若节点 i 不可扩展，则转第不可扩展，则转第 (2) 步。步。(6) 扩展节点扩展节点 i，将其子节点放入，将其子节点放入 OPEN 表中，且为表中，且为其配置指向父节点的指针；计算各子节点的代价，并其配置指向父节点的指针；计算各子节点的代价，并按各节点的代价对按各节点的代价对 OPEN 表中的表中的全部节点进行排序全部节点进行排序 (按从小到大的顺序按从小到大的顺序)，然后转第，然后转第 (2) 步。步。 如果问题有解，该搜索过程一定可以求得它并且求出
36、的如果问题有解，该搜索过程一定可以求得它并且求出的是最优解。是最优解。举例：五城市间的交通路线图，举例：五城市间的交通路线图，A 城市是出发地，城市是出发地，E 城城市是目的地，两城市间的交通费用市是目的地，两城市间的交通费用 ( 代价代价 ) 如图中数字如图中数字所示。求从所示。求从 A 到到 E 的最小费用交通路线。的最小费用交通路线。5为了应用代价树的广度优为了应用代价树的广度优先搜索方法求解此问题，先搜索方法求解此问题，需先将交通图转换为需先将交通图转换为代价代价树树。 转换的方法是转换的方法是：从起：从起始节点始节点 A 开始，把与它直开始，把与它直接相邻的节点作为它的子接相邻的节点
37、作为它的子节点。对其它节点也做相节点。对其它节点也做相同的处理。但若一个节点同的处理。但若一个节点已作为某节点的直系先辈已作为某节点的直系先辈节点时，就不能再作为这节点时，就不能再作为这个节点的子节点。个节点的子节点。 另外，另外，目的节点不再扩展了。目的节点不再扩展了。g(x)表示从初始节点表示从初始节点S0到节点到节点x的代价；的代价；c(x1,x2)表示从表示从父结点父结点x1到子节点到子节点x2的代价。的代价。代价树深度优先搜索的过程：代价树深度优先搜索的过程：(1) 把初始节点把初始节点 S0 放入放入 OPEN 表中。表中。(2) 如果如果 OPEN 表为空，则问题无解，退出。表为
38、空，则问题无解，退出。(3) 把把 OPEN 表的第一个节点表的第一个节点 ( 记为节点记为节点 n) 取出放入取出放入 CLOSED 表。表。(4) 考察节点考察节点 n 是否为目标节点。若是，则求得了问题的解，退出。是否为目标节点。若是，则求得了问题的解，退出。(5) 若节点若节点n不可扩展，则转第不可扩展，则转第 (2) 步。步。(6) 扩展节点扩展节点n，将，将OPEN 表中所有节点按边代价从小到大的顺序表中所有节点按边代价从小到大的顺序排列排列，并为各子节点配置指向父节点的指针，然后转第，并为各子节点配置指向父节点的指针，然后转第 (2) 步。步。 g(x)表示从初始节点表示从初始节
39、点S0到节点到节点x的代价；的代价；c(x1,x2)表示从表示从父结点父结点x1到子节点到子节点x2的代价。的代价。代价树深度优先搜索的过程：代价树深度优先搜索的过程：(1) 把初始节点把初始节点 S0 放入放入 OPEN 表中。表中。(2) 如果如果 OPEN 表为空，则问题无解，退出。表为空，则问题无解，退出。(3) 把把 OPEN 表的第一个节点表的第一个节点 ( 记为节点记为节点 n) 取出放入取出放入 CLOSED 表。表。(4) 考察节点考察节点 n 是否为目标节点。若是，则求得了问题的解，退出。是否为目标节点。若是，则求得了问题的解，退出。(5) 若节点若节点n不可扩展，则转第不
40、可扩展，则转第 (2) 步。步。(6) 扩展节点扩展节点n，将其，将其子节点按边代价从小到大的顺序放到子节点按边代价从小到大的顺序放到 OPEN 表的首部表的首部，并为各子节点配置指向父节点的指针，然后转第，并为各子节点配置指向父节点的指针，然后转第 (2) 步。步。 v在代价树的广度优先搜索中，在代价树的广度优先搜索中，每次都是从每次都是从 OPEN表的全体节表的全体节点中选择一个代价最小的节点点中选择一个代价最小的节点送入送入 CLOSED 表进行考察；表进行考察；v代价树的深度优先搜索是代价树的深度优先搜索是从刚从刚扩展出的子节点中选一个代价扩展出的子节点中选一个代价最小的节点送入最小的
41、节点送入 CLOSED 表表进行考察进行考察。v一般情况下这两种方法得到的结果不一定相同。另外，由于代价一般情况下这两种方法得到的结果不一定相同。另外，由于代价树的深度优先搜索有可能进入无穷分支路径，因此它是树的深度优先搜索有可能进入无穷分支路径，因此它是不完备的。不完备的。 前面讨论的搜索方法都是非启发式搜索，前面讨论的搜索方法都是非启发式搜索，它们或者是它们或者是按事先规定的路线进行搜索按事先规定的路线进行搜索，或者，或者是是按已经付出的代价决定下一步要搜索的节点按已经付出的代价决定下一步要搜索的节点。 它们的一个共同特点是它们的一个共同特点是都没有利用问题本都没有利用问题本身的特性信息身
42、的特性信息，在决定要被扩展的节点时，在决定要被扩展的节点时，都都没有考虑该节点在解的路径上的可能性有多大没有考虑该节点在解的路径上的可能性有多大，它它是否有利于问题求解是否有利于问题求解以及以及求出的解是否为最求出的解是否为最优解优解等。等。 因此这些搜索方法都具有较大的盲目性，因此这些搜索方法都具有较大的盲目性，产生的无用节点较多，搜索空间较大，效率不产生的无用节点较多，搜索空间较大，效率不高。高。 3.2.3状态空间的启发式搜索状态空间的启发式搜索 启发式搜索要用到启发式搜索要用到问题自身的某些特性信息问题自身的某些特性信息，以，以指导搜索朝着最有希望的方向前进。由于这种搜索指导搜索朝着最
43、有希望的方向前进。由于这种搜索针对性较强，因而原则上只需要搜索问题的部分状针对性较强，因而原则上只需要搜索问题的部分状态空间，效率较高。态空间，效率较高。 v启发性信息：启发性信息：可用于指导搜索过程，且与具体问题求解有关可用于指导搜索过程，且与具体问题求解有关的控制性信息的控制性信息1.陈述性启发信息陈述性启发信息：一般被用于更准确、更精练地描述状态，：一般被用于更准确、更精练地描述状态，使问题的状态空间缩小，如待求问题的特定状况等属于此类使问题的状态空间缩小，如待求问题的特定状况等属于此类信息。信息。2.过程性启发信息过程性启发信息：一般被用于构造操作算子，使操作算子少：一般被用于构造操作
44、算子，使操作算子少而精，如一些规律性知识属于此类信息。而精，如一些规律性知识属于此类信息。3.控制性启发信息控制性启发信息：它是关于表示控制策略方面的知识，包括：它是关于表示控制策略方面的知识，包括协调整个问题求解过程中所使用的各种处理方法、搜索策略、协调整个问题求解过程中所使用的各种处理方法、搜索策略、控制结构等有关的知识。控制结构等有关的知识。v估价函数估价函数 用于估价节点重要性或用于估价节点重要性或“有希望有希望”程度的函程度的函数称为估价函数。其一般形式为：数称为估价函数。其一般形式为：f(x)=g(x)+h(x)&g(x) 为从初始节点为从初始节点 S0 到节点到节点 x 已经实际
45、付出的代已经实际付出的代价；价；&h(x) 是从节点是从节点 x 到目标节点到目标节点 S 的最优路径的估计代的最优路径的估计代价，价，它体现了问题的启发性信息，其形式要根据问它体现了问题的启发性信息，其形式要根据问题的特性确定。它可以是节点题的特性确定。它可以是节点 x 到目标节点的距离到目标节点的距离或差异，可以是或差异，可以是x格局的得分，也可以是节点格局的得分，也可以是节点 x 处处于最优路径上的概率等等。于最优路径上的概率等等。h (x) 称为启发函数。称为启发函数。3.2.3状态空间的启发式搜索状态空间的启发式搜索& 估价函数估价函数 f(z) 表示从初始节点经过节点表示从初始节点
46、经过节点 Z 到达目标到达目标节点的最优路径的代价估计值，它的作用是节点的最优路径的代价估计值，它的作用是估价估价 OPEN 表中各节点的重要程度，决定它们在表中各节点的重要程度，决定它们在 OPEN 表中的次序表中的次序。& g(z) 指出了搜索的指出了搜索的横向趋势横向趋势，它有利于搜索的完备，它有利于搜索的完备性，但性，但影响搜索的效率影响搜索的效率。如果我们只关心到达目标。如果我们只关心到达目标节点的路径，并且希望有较高的搜索效率，则节点的路径，并且希望有较高的搜索效率，则 g(z) 可以忽略，但此时会影响搜索的完备性。可以忽略，但此时会影响搜索的完备性。 &在确定在确定 f(z) 时
47、，要权衡各种利弊得失，使时，要权衡各种利弊得失，使 g(z) 与与 h (z) 各占适当的比重。各占适当的比重。5.2.3状态空间的启发式搜索状态空间的启发式搜索v举例：对举例：对 8 数码问题，评估函数可以表数码问题，评估函数可以表示为：示为：f(z) =d(z)+ (z) d(z)表示节点表示节点 Z 在搜索树中的深度，在搜索树中的深度， (z)表示节点表示节点 Z 不在目标状态中相应位不在目标状态中相应位置的数码个数，置的数码个数，(z)就包含了问题的启就包含了问题的启发式信息。一般来说，某节点发式信息。一般来说，某节点(z) 越大，越大，即即“不在目标位不在目标位”的数码个数越多，说的
48、数码个数越多，说明它离目标节点越远。明它离目标节点越远。v 对初始节点对初始节点 S0，由于，由于 d(S0)=0， (S0) =3，因此，因此f(S0)=3。3.2.3状态空间的启发式搜索状态空间的启发式搜索目标状态目标状态初始状态初始状态几种启发式算法几种启发式算法1. 局部择优搜索局部择优搜索是对深度优先搜索方法的是对深度优先搜索方法的一种改进。一种改进。&基本思想：基本思想：&当一个节点被扩展以后，按当一个节点被扩展以后，按f(x)对每一个子对每一个子节点节点计算估价值，并计算估价值，并选择最小者选择最小者作为下一个作为下一个要考查的节点，要考查的节点，&由于它由于它每次都只是在子节点
49、的范围内选择每次都只是在子节点的范围内选择下下一个要考查的节点，范围比较窄，所以称为一个要考查的节点，范围比较窄，所以称为局部择优搜索。局部择优搜索。&搜索过程：搜索过程：(1)把初始节点把初始节点s0放入放入OPEN表，计算表，计算f(s0)；(2)如果如果OPEN表为空，则问题无解，退出；表为空，则问题无解，退出；(3)把把OPEN表的第一个节点（记为表的第一个节点（记为n）取出放入）取出放入CLOSED表；表；(4)考查节点考查节点n是否为目标节点。若是，则求得了问题是否为目标节点。若是，则求得了问题的解，退出；的解，退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步
50、；(6)扩展节点扩展节点n，用估价函数用估价函数f(x)计算每个子节点的估计算每个子节点的估价值，并按估价值从大到小的顺序依次放到价值，并按估价值从大到小的顺序依次放到OPEN表的首部表的首部，为每个子节点配置指向父节点的指针。，为每个子节点配置指向父节点的指针。然后转第然后转第(2)步。步。几种启发式算法几种启发式算法vf(z) =d(z)+ (z)ld(z)表示节点表示节点 Z 在搜索树在搜索树中的深度，中的深度，l(z)表示节点表示节点 Z 不在目不在目标状态中相应位置的数码标状态中相应位置的数码个数个数目标状态目标状态初始状态初始状态几种启发式算法几种启发式算法v深度优先搜索、代价树的