1、23.1 图搜索策略图搜索策略1 1、图搜索策略的定义、图搜索策略的定义图搜索策略可看作一种在图中寻找路径图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一搜索的一般策略，能够给出图搜索过程的一般步骤。般步骤。32 2、图搜索算法中的几个重要名词术语、图搜索算法中的几个重要
2、名词术语（1 1）OPENOPEN表与表与CLOSECLOSE表表（2 2）搜索图与搜索树）搜索图与搜索树状态节点父节点状态节点父节点编号OPENOPEN表表CLOSECLOSE表表453 3、图搜索、图搜索(GRAPHSEARCH)(GRAPHSEARCH)的一般过程的一般过程(1)(1)建立一个只含有起始节点建立一个只含有起始节点S S的搜索图的搜索图G G，把把S S放到一个叫做放到一个叫做OPENOPEN的未扩展节点表中。的未扩展节点表中。(2)(2)建立一个叫做建立一个叫做CLOSEDCLOSED的已扩展节点表，的已扩展节点表，其初始为空表。其初始为空表。(3)LOOP(3)LOOP
3、：若：若OPENOPEN表是空表，则失败退出。表是空表，则失败退出。(4)(4)选择选择OPENOPEN表上的第一个节点，把它从表上的第一个节点，把它从OPENOPEN表移出并放进表移出并放进CLOSEDCLOSED表中。称此节点为节表中。称此节点为节点点n n。(5)(5)若若n n为一目标节点，则有解并成功退出，为一目标节点，则有解并成功退出，此解是追踪图此解是追踪图G G中沿着指针从中沿着指针从n n到到S S这条路径而得这条路径而得到的到的(指针将在第指针将在第7 7步中设置步中设置)。6 (6)(6)扩展节点扩展节点n n，同时生成不是，同时生成不是n n的祖先的那的祖先的那些后继节
4、点的集合些后继节点的集合M M。把。把M M的这些成员作为的这些成员作为n n的后的后继节点添入图继节点添入图G G中。中。(7)(7)对那些未曾在对那些未曾在G G中出现过的中出现过的(既未曾在既未曾在OPENOPEN表上或表上或CLOSEDCLOSED表上出现过的表上出现过的)M)M成员设置一成员设置一个通向个通向n n的指针。把的指针。把M M的这些成员加进的这些成员加进OPENOPEN表。表。对已经在对已经在OPENOPEN或或CLOSEDCLOSED表上的每一个表上的每一个M M成员，确成员，确定是否需要更改通到定是否需要更改通到n n的指针方向。对已在的指针方向。对已在CLOSED
5、CLOSED表上的每个表上的每个M M成员，确定是否需要更改图成员，确定是否需要更改图G G中通向它的每个后裔节点的指针方向。中通向它的每个后裔节点的指针方向。(8)(8)按某一任意方式或按某个探试值，重按某一任意方式或按某个探试值，重排排OPENOPEN表。表。(9)GO LOOP(9)GO LOOP。74、图搜索方法分析：、图搜索方法分析：图搜索过程的第图搜索过程的第8 8步对步对OPENOPEN表上的节点进行排表上的节点进行排序，以便能够从中选出一个序，以便能够从中选出一个“最好最好”的节点作的节点作为第为第4 4步扩展用。这种排序可以是任意的即盲目步扩展用。这种排序可以是任意的即盲目的
6、的(属于盲目搜索属于盲目搜索)，也可以用以后要讨论的各，也可以用以后要讨论的各种启发思想或其它准则为依据种启发思想或其它准则为依据(属于启发式搜属于启发式搜索索)。每当被选作扩展的节点为目标节点时，这。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是始节点到目标节点的这条成功路径，其办法是从目标节点按指针向从目标节点按指针向S S返回追溯。当搜索树不再返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以
7、某些节点最终可能没有后继节点，所以OPENOPEN表表可能最后变成空表可能最后变成空表)。在失败终止的情况下，从。在失败终止的情况下，从起始节点出发，一定达不到目标节点。起始节点出发，一定达不到目标节点。83.2盲目搜索盲目搜索教学内容：介绍三种盲目搜索方法，即宽度教学内容：介绍三种盲目搜索方法，即宽度优先搜索、深度优先搜索和等代价搜索。优先搜索、深度优先搜索和等代价搜索。教学重点：盲目搜索的特点，宽度优先搜索。教学重点：盲目搜索的特点，宽度优先搜索。教学难点：等代价搜索中代价的概念。教学难点：等代价搜索中代价的概念。教学方法：以实例强化内容的学习，通过提教学方法：以实例强化内容的学习，通过提
8、问引导学生对三种方法的特点进行比较。问引导学生对三种方法的特点进行比较。教学要求：掌握盲目搜索的特点，比较三种教学要求：掌握盲目搜索的特点，比较三种盲目搜索方法的优缺点。盲目搜索方法的优缺点。93.2.13.2.1宽度优先搜索宽度优先搜索1 1、定义、定义如果搜索是以接近起始节点的程度依次如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先扩展节点的，那么这种搜索就叫做宽度优先搜索搜索(breadth-first search)(breadth-first search)。102 2、特点、特点这种搜索是逐层进行的；在对下一层的这种搜索是逐层进行的；在对下一层的任一节点进行
9、搜索之前，必须搜索完本层的任一节点进行搜索之前，必须搜索完本层的所有节点。所有节点。113 3、宽度优先搜索算法、宽度优先搜索算法(1)(1)把起始节点放到把起始节点放到OPENOPEN表中表中(如果该起始节如果该起始节点为一目标节点，则求得一个解答点为一目标节点，则求得一个解答)。(2)(2)如果如果OPENOPEN是个空表，则没有解，失败退出；是个空表，则没有解，失败退出；否则继续。否则继续。(3)(3)把第一个节点把第一个节点(节点节点n)n)从从OPENOPEN表移出，并表移出，并把它放入把它放入CLOSEDCLOSED的扩展节点表中。的扩展节点表中。(4)(4)扩展节点扩展节点n n
10、。如果没有后继节点，则转向。如果没有后继节点，则转向上述第上述第(2)(2)步。步。(5)(5)把把n n的所有后继节点放到的所有后继节点放到OPENOPEN表的末端，表的末端，并提供从这些后继节点回到并提供从这些后继节点回到n n的指针。的指针。(6)(6)如果如果n n的任一个后继节点是个目标节点，的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第则找到一个解答，成功退出；否则转向第(2)(2)步。步。124 4、宽度优先搜索方法分析：、宽度优先搜索方法分析：宽度优先搜索是图搜索一般过程的特殊情宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第况，将图搜索一般过
11、程中的第8 8步具体化为本算步具体化为本算法中的第法中的第6 6步，这实际是将步，这实际是将OPENOPEN表作为表作为“先进先先进先出出”的队列进行操作。的队列进行操作。宽度优先搜索方法能够保证在搜索树中找宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径提供了所有存在的路径(如果没有路径存在，那如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止于无限图来说，则永远不会终止)。135 5、例：把宽度优先搜索应用于八数码难题时、例：
12、把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：局变为如下目标棋局的问题：15 3.2.2深度优先搜索深度优先搜索1、定义、定义在此搜索中，首先扩展最新产生的在此搜索中，首先扩展最新产生的(即即最深的最深的)节点。深度相等的节点可以任意排节点。深度相等的节点可以任意排列。列。这种盲目这种盲目(无信息无信息)搜索叫做深度优先搜搜索叫做深度优先搜索索(depth-first search)(depth-first search)。162 2、特点、特点首先，扩展最深的节点的结果使得搜索首先，扩展最深的节点的结果使
13、得搜索沿着状态空间某条单一的路径从起始节点向沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。的状态时，它才考虑另一条替代的路径。183 3、深度界限、深度界限为了避免考虑太长的路径为了避免考虑太长的路径(防止搜索过防止搜索过程沿着无益的路径扩展下去程沿着无益的路径扩展下去)，往往给出一，往往给出一个节点扩展的最大深度界限。任何节点如果个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有达到了深度界限，那么都将把它们作为没有后继节点处理。后继节点处理。204 4、含有深度
14、界限的深度优先搜索算法、含有深度界限的深度优先搜索算法请同学们课后自学，并回答课后思考题。请同学们课后自学，并回答课后思考题。思考题思考题：有界深度优先搜索方法能够保证在：有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径搜索树中找到一条通向目标节点的最短途径吗？吗？213.2.33.2.3等代价搜索等代价搜索1 1、定义、定义宽度优先搜索可被推广用来解决寻找从宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。等代价搜索算法。
15、222 2、等代价搜索中的几个记号、等代价搜索中的几个记号起始节点记为起始节点记为S S；从节点从节点i i到它的后继节点到它的后继节点j j的连接弧线代的连接弧线代价记为价记为c(ic(i，j)j)；从起始节点从起始节点S S到任一节点到任一节点i i的路径代价记的路径代价记为为g(i)g(i)。23243 3、等代价搜索算法、等代价搜索算法（请同学们课后认真阅读本算法，指出（请同学们课后认真阅读本算法，指出与宽度优先、深度优先算法有何特别之处。）与宽度优先、深度优先算法有何特别之处。）254 4、等代价搜索方法分析、等代价搜索方法分析如果所有的连接弧线具有相等的代价，如果所有的连接弧线具有
16、相等的代价，那么等代价算法就简化为宽度优先搜索算法。那么等代价算法就简化为宽度优先搜索算法。思考思考：试比较各种盲目搜索搜索方法的效率，试比较各种盲目搜索搜索方法的效率，找出影响算法效率的原因。找出影响算法效率的原因。263.3 启发式搜索启发式搜索 教学内容：启发式搜索策略概述和有序搜索。启发教学内容：启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足，提高搜索效率。式搜索弥补盲目搜索的不足，提高搜索效率。教学重点：启发式搜索策略、启发信息和有序搜索。教学重点：启发式搜索策略、启发信息和有序搜索。教学难点：估价函数的设计、教学难点：估价函数的设计、A A*算法原理。算法原理。教学方法
17、：通过实例加深对原理的理解，鼓励同学教学方法：通过实例加深对原理的理解，鼓励同学扩大阅读范围。扩大阅读范围。教学要求：掌握启发式搜索策略和估价函数的设计教学要求：掌握启发式搜索策略和估价函数的设计方法，了解方法，了解A A*算法原理。算法原理。273.3.13.3.1启发式搜索策略和估价函数启发式搜索策略和估价函数1 1、为什么需要启发式搜索、为什么需要启发式搜索盲目搜索效率低，耗费过多的计算空间盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。与时间，这是组合爆炸的一种表现形式。282 2、定义、定义进行搜索技术一般需要某些有关具体问进行搜索技术一般需要某些有关具体问题领
18、域的特性的信息，把此种信息叫做启发题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式信息。利用启发信息的搜索方法叫做启发式搜索方法。搜索方法。293 3、启发式搜索策略、启发式搜索策略有关具体问题领域的信息常常可以用来有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活简化搜索。一个比较灵活(但代价也较大但代价也较大)的的利用启发信息的方法是应用某些准则来重新利用启发信息的方法是应用某些准则来重新排列每一步排列每一步OPENOPEN表中所有节点的顺序。然后，表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边搜索就可能沿着某个被认为是最有希望的边缘区段
19、向外扩展。应用这种排序过程，需要缘区段向外扩展。应用这种排序过程，需要某些估算节点某些估算节点“希望希望”的量度，这种量度叫的量度，这种量度叫做估价函数做估价函数(evalution function)(evalution function)。304 4、估价函数、估价函数为获得某些节点为获得某些节点“希望希望”的启发信息，提的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上个节点最有可能在通向目标的最佳路径上 。f(n)f(n)表示节点表示节点n n的估价函数值的估价函数值建立估价函数的一般方法：试图确定一个建立
20、估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。节点前进一步的希望程度有关。313.3.2 3.3.2 有序搜索有序搜索1 1、定义、定义用估价函数用估价函数f f来排列来排列GRAPHSEARCHGRAPHSEARCH第第8 8步中步中OPENOPEN表上的节点。应
21、用某个算法表上的节点。应用某个算法(例如等代价算例如等代价算法法)选择选择OPENOPEN表上具有最小表上具有最小f f值的节点作为下一值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)(ordered search)或最佳优先搜索或最佳优先搜索(best-(best-first search)first search)，而其算法就叫做有序搜索算法，而其算法就叫做有序搜索算法或最佳优先算法。或最佳优先算法。尼尔逊尼尔逊(Nilsson)(Nilsson)曾提出一个有序搜索的基曾提出一个有序搜索的基本算法。估价函数本算
22、法。估价函数f f是这样确定的：一个节点的是这样确定的：一个节点的希望程序越大，其希望程序越大，其f f值就越小。被选为扩展的节值就越小。被选为扩展的节点，是估价函数最小的节点。点，是估价函数最小的节点。322 2、实质、实质选择选择OPENOPEN表上具有最小表上具有最小f f值的节点作为值的节点作为下一个要扩展的节点，即总是选择最有希望下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。的节点作为下一个要扩展的节点。333 3、有序状态空间搜索算法、有序状态空间搜索算法(1)(1)把起始节点把起始节点S S放到放到OPENOPEN表中，计算表中，计算f(S)f(S)并把并把
23、其值与节点其值与节点S S联系起来。联系起来。(2)(2)如果如果OPENOPEN是个空表，则失败退出，无解。是个空表，则失败退出，无解。(3)(3)从从OPENOPEN表中选择一个表中选择一个f f值最小的节点值最小的节点i i。结。结果有几个节点合格，当其中有一个为目标节点果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一时，则选择此目标节点，否则就选择其中任一个节点作为节点个节点作为节点i i。(4)(4)把节点把节点i i从从OPENOPEN表中移出，并把它放入表中移出，并把它放入CLOSEDCLOSED的扩展节点表中。的扩展节点表中。(5)(5)如果如果
24、i i是个目标节点，则成功退出，求得一是个目标节点，则成功退出，求得一个解。个解。34(6)(6)扩展节点扩展节点i i，生成其全部后继节点。对于，生成其全部后继节点。对于i i的每一的每一个后继节点个后继节点j j：(a)(a)计算计算f(j)f(j)。(b)(b)如果如果j j既不在既不在OPENOPEN表中，又不在表中，又不在CLOSEDCLOSED表中，则表中，则用估价函数用估价函数f f把它添入把它添入OPENOPEN表。从表。从j j加一指向其父辈加一指向其父辈节点节点i i的指针，以便一旦找到目标节点时记住一个的指针，以便一旦找到目标节点时记住一个解答路径。解答路径。(c)(c)
25、如果如果j j已在已在OPENOPEN表上或表上或CLOSEDCLOSED表上，则比较刚刚表上，则比较刚刚对对j j计算过的计算过的f f值和前面计算过的该节点在表中的值和前面计算过的该节点在表中的f f值。如果新的值。如果新的f f值较小，则值较小，则(i)(i)以此新值取代旧值。以此新值取代旧值。(ii)(ii)从从j j指向指向i i，而不是指向它的父辈节点。，而不是指向它的父辈节点。(iii)(iii)如果节点如果节点j j在在CLOSEDCLOSED表中，则把它移回表中，则把它移回OPENOPEN表。表。(7)(7)转向转向(2)(2)，即，即GO TO(2)GO TO(2)。354
26、 4、有序搜索方法分析、有序搜索方法分析宽度优先搜索、等代价搜索和深度优先搜索统宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索，选统是有序搜索技术的特例。对于宽度优先搜索，选择择f(i)f(i)作为节点作为节点i i的深度。对于等代价搜索，的深度。对于等代价搜索，f(i)f(i)是从起始节点至节点是从起始节点至节点i i这段路径的代价。这段路径的代价。有序搜索的有效性直接取决于有序搜索的有效性直接取决于f f的选择，如果的选择，如果选择的选择的f f不合适，有序搜索就可能失去一个最好的不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望
27、量度，解甚至全部的解。如果没有适用的准确的希望量度，那么那么f f的选择将涉及两个方面的内容：一方面是一的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。一个最优的解或任意解。365 5、例：八数码难题、例：八数码难题采用了简单的估价函数采用了简单的估价函数f(n)=d(n)+W(n)f(n)=d(n)+W(n)其中：其中：d(n)d(n)是搜索树中节点是搜索树中节点n n的深度；的深度；W(n)W(n)用用来计算对应于节点来计算对应于节点n n的数据库中错放的棋子个数。的数据库中错放的棋子个数。
28、因此，起始节点棋局因此，起始节点棋局2 8 32 8 31 1 4 47 6 57 6 5的的f f值等于值等于0+4=40+4=4。373.3.3 A3.3.3 A*算法算法A A*算法是一种有序搜索算法，其特点在于对算法是一种有序搜索算法，其特点在于对估价函数的定义上。估价函数的定义上。1 1、几个记号、几个记号令令k(nk(ni i，n nj j)表示任意两个节点表示任意两个节点n ni i和和n nj j之间之间最小代价路径的实际代价最小代价路径的实际代价(对于两节点间没有通对于两节点间没有通路的节点，函数路的节点，函数k k没有定义没有定义)。于是，从节点。于是，从节点n n到到某个
29、具体的目标节点某个具体的目标节点t ti i，某一条最小代价路径，某一条最小代价路径的代价可由的代价可由k(n,tk(n,ti i)给出。令给出。令h h*(n)(n)表示整个目表示整个目标节点集合标节点集合t ti i上所有上所有k(n,tk(n,ti i)中最小的一个，中最小的一个，因此，因此，h h*(n)(n)就是从就是从n n到目标节点最小代价路径到目标节点最小代价路径的代价，而且从的代价，而且从n n到目标节点能够获得到目标节点能够获得h h*(n)(n)的的任一路径就是一条从任一路径就是一条从n n到某个目标节点的最佳路到某个目标节点的最佳路径径(对于任何不能到达目标节点的节点对
30、于任何不能到达目标节点的节点n n，函数，函数h h*没有定义没有定义)。382 2、估价函数的定义、估价函数的定义定义定义g g*为为:g:g*(n)=k(S,n)(n)=k(S,n)定义函数定义函数f f*，使得在任一节点，使得在任一节点n n上其函数值上其函数值f f*(n)(n)就是从节点就是从节点S S到节点到节点n n的一条最佳路径的一条最佳路径的实际代价加上从节点的实际代价加上从节点n n到某目标节点的一到某目标节点的一条最佳路径的代价之和，即条最佳路径的代价之和，即 f f*(n)=g(n)=g*(n)+h(n)+h*(n)(n)39 希望估价函数希望估价函数f f是是f f*
31、的一个估计，此估计可由下的一个估计，此估计可由下式给出：式给出：f(n)=g(n)+h(n)f(n)=g(n)+h(n)其中：其中：g g是是g g*的估计；的估计；h h是是h h*的估计。对于的估计。对于g(n)g(n)来说，一个明显的选择就是搜索树中从来说，一个明显的选择就是搜索树中从S S到到n n这段路径的代价，这一代价可以由从这段路径的代价，这一代价可以由从n n到到S S寻找寻找指针时，把所遇到的各段弧线的代价加起来给指针时，把所遇到的各段弧线的代价加起来给出出(这条路径就是到目前为止用搜索算法找到的这条路径就是到目前为止用搜索算法找到的从从S S到到n n的最小代价路径的最小代
32、价路径)。这个定义包含了。这个定义包含了g(n)gg(n)g*(n)(n)。h h*(n)(n)的估计的估计h(n)h(n)依赖于有关问依赖于有关问题的领域的启发信息。这种信息可能与八数码题的领域的启发信息。这种信息可能与八数码难题中的函数难题中的函数W(n)W(n)所用的那种信息相似。把所用的那种信息相似。把h h叫叫做启发函数。做启发函数。403 3、A A*算法定义算法定义定义定义1 1 在在GRAPHSEARCHGRAPHSEARCH过程中，如果第过程中，如果第8 8步步的重排的重排OPENOPEN表是依据表是依据f(x)=g(x)+h(x)f(x)=g(x)+h(x)进行的，进行的，
33、则称该过程为则称该过程为A A算法。算法。定义定义2 2 在在A A算法中，如果对所有的算法中，如果对所有的x x存在存在h(x)hh(x)h*(x),(x),则称则称h(x)h(x)为为h h*(x)(x)的下界，它表示的下界，它表示某种偏于保守的估计。某种偏于保守的估计。定义定义3 3 采用采用h h*(x)(x)的下界的下界h(x)h(x)为启发函数的为启发函数的A A算法，称为算法，称为A A*算法。当算法。当h=0h=0时，时，A A*算法就变为算法就变为有序搜索算法。有序搜索算法。414 4、A A*算法算法A A*算法描述参考教材。算法描述参考教材。提问提问：由由g g*(n)(
34、n)和和g(n)g(n)的定义知的定义知g g*(n)g(n)(n)g(n)A A对对 B B错错思考：思考：试比较宽度优先搜索、有界深度优先试比较宽度优先搜索、有界深度优先搜索及有序搜索的搜索效率，并以实例数据搜索及有序搜索的搜索效率，并以实例数据加以说明加以说明423.4 消解原理消解原理教学内容：消解原理是针对谓词逻辑知识表示教学内容：消解原理是针对谓词逻辑知识表示的问题求解方法。本节内容主要包括子句集的的问题求解方法。本节内容主要包括子句集的求取、消解推理的规则和消解反演问题求解方求取、消解推理的规则和消解反演问题求解方法。法。教学重点：子句集的求取、消解推理的规则和教学重点：子句集的
35、求取、消解推理的规则和消解反演问题求解方法。消解反演问题求解方法。教学难点：消解反演的思想。教学难点：消解反演的思想。教学方法：实例讲解，注重课堂练习。教学方法：实例讲解，注重课堂练习。教学要求：重点掌握子句集的求解步骤和消解教学要求：重点掌握子句集的求解步骤和消解反演过程，掌握消解推理的规则。反演过程，掌握消解推理的规则。43消解原理的基础知识：消解原理的基础知识：（1 1）谓词公式、某些推理规则以及置换合）谓词公式、某些推理规则以及置换合一等概念。一等概念。（2 2）子句：由文字的析取组成的公式）子句：由文字的析取组成的公式(一一个原子公式和原子公式的否定都叫做文字个原子公式和原子公式的否
36、定都叫做文字)。（3 3）消解：当消解可使用时，消解过程被）消解：当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。应用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理例如，如果存在某个公理E E1 1EE2 2和另一公理和另一公理E E2 2EE3 3，那么，那么E E1 1EE3 3在逻辑上成立。这就是消解，在逻辑上成立。这就是消解，而称而称E E1 1EE3 3为为E E1 1EE2 2和和E E2 2EE3 3的消解式的消解式(resolvent)(resolvent)。443.4.13.4.1子句集的求取子句集的求取1 1、步骤、步骤(1)(1)消去蕴涵符号
37、消去蕴涵符号只应用只应用和符号，以和符号，以ABAB替换替换ABAB。提问：提问：现有公式现有公式(A(AB)B)B CB C，在消去蕴涵，在消去蕴涵符号后得到公式：符号后得到公式：A A(AB)B C B(AB)B C B(AB)B(AB)B CCC C(AB)B C DAB)B C D(AB)B (AB)B CC45(2)(2)减少否定符号的辖域减少否定符号的辖域每个否定符号最多只用到一个谓词符每个否定符号最多只用到一个谓词符号上，号上，并反复应用狄并反复应用狄摩根定律。例如：摩根定律。例如：以以AAB B代替代替(AB)(AB)以以AAB B代替代替(AB)(AB)以以A A代替代替(A
38、)A)以以()A A代替代替(x)A x)A以以(x)x)A A代替代替(x)A x)A46提问提问：设有公式设有公式(x)(x)(y)y)(y)P(x,y)y)P(x,y)(x)Q(x,y)x)Q(x,y)，在经过对变量标准化后得到公式为：，在经过对变量标准化后得到公式为：A A(x)(x)(y)y)(y)P(x,y)(y)P(x,y)(y)Q(y,y)y)Q(y,y)B B(x)(x)(y)y)(x)P(x,x)(x)P(x,x)(x)Q(x,y)x)Q(x,y)C C(x)(x)(y)y)(z)P(x,z)(z)P(x,z)(q)Q(q,y)q)Q(q,y)D D(x)(x)(y)y)(
39、z)P(x,z)(z)P(x,z)(q)Q(q,z)q)Q(q,z)E E(x)(x)(y)y)(z)P(q,z)(z)P(q,z)(q)Q(q,z)q)Q(q,z)47(3)(3)对变量标准化对变量标准化在任一量词辖域内，受该量词约束的变在任一量词辖域内，受该量词约束的变量为一哑元量为一哑元(虚构变量虚构变量)，它可以在该辖域内，它可以在该辖域内处处统一地被另一个没有出现过的任意变量处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。合适公式中所代替，而不改变公式的真值。合适公式中变量的标准化意味着对哑元改名以保证每个变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元
40、。量词有其自己唯一的哑元。48(4)(4)消去存在量词消去存在量词用用SkolemSkolem函数代替存在的函数代替存在的x,x,就可以消去全就可以消去全部存在量词，并写成：部存在量词，并写成：(y)P y)Pg(y),yg(y),y从一个公式消去一个存在量词的一般规则从一个公式消去一个存在量词的一般规则是以一个是以一个SkolemSkolem函数代替每个出现的存在量词函数代替每个出现的存在量词的量化变量，而这个的量化变量，而这个SkolemSkolem函数的变量就是由函数的变量就是由那些全称量词所约束的全称量词量化变量，这那些全称量词所约束的全称量词量化变量，这些全称量词的辖域包括要被消去的
41、存在量词的些全称量词的辖域包括要被消去的存在量词的辖域在内。辖域在内。SkolemSkolem函数所使用的函数符号必须函数所使用的函数符号必须是新的，即不允许是公式中已经出现过的函数是新的，即不允许是公式中已经出现过的函数符号。例如：符号。例如：(y)(y)(x)P(x,y)x)P(x,y)被被(y)P(g(y),y)y)P(g(y),y)代替，其中代替，其中g(y)g(y)为一为一SkolemSkolem函数。函数。49如果要消去的存在量词不在任何一个全如果要消去的存在量词不在任何一个全称量词的辖域内，则用不含变量的称量词的辖域内，则用不含变量的SkolemSkolem函函数即常量。例如，数
42、即常量。例如，(x)P(x)x)P(x)化为化为P(A)P(A)，其，其中常量符号中常量符号A A用来表示人们知道的存在实体。用来表示人们知道的存在实体。A A必须是个新的常量符号，它未曾在公式中必须是个新的常量符号，它未曾在公式中其它地方使用过。其它地方使用过。50(5)(5)化为前束形化为前束形把所有全称量词移到公式的左边，并使每把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。分。所得公式称为前束形。(6)(6)把母式化为合取范式把母式化为合取范式任何母式都可写成由一些谓词公式和任何母式都可写成由一
43、些谓词公式和(或或)谓词公式的否定的析取的有限集组成的合取。谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。这种母式叫做合取范式。(7)(7)消去全称量词消去全称量词消去明显出现的全称量词。消去明显出现的全称量词。51提问：对于公式提问：对于公式(z)(z)(y)(y)(x)P(x,y,z)(x)P(x,y,z)(q)(q)()()(e)Q(q,w,e,z)e)Q(q,w,e,z)，在经过消去存在量词后，在经过消去存在量词后，正确的公式为：正确的公式为：A A(y)P(B,y,A)(y)P(B,y,A)(w)Q(C,w,D,A)w)Q(C,w,D,A)B B(y)P(B,y,A)
44、(y)P(B,y,A)(w)Q(C,w,g(w),A),w)Q(C,w,g(w),A),g(w)g(w)为一为一SkolemSkolem函数函数C C(y)P(g y)P(g1 1(y),y,A)(y),y,A)(w)Q(g w)Q(g(y),w,g(y),w,g(w),A)(w),A)式中，式中，(g(g1 1(y)(y)，g g(y)(y)和和g g(w)(w)为为SkolemSkolem函数函数D D(y)P(g y)P(g1 1(y),y,A)(y),y,A)(w)Q(g w)Q(g(y),w,g(y),w,g(y,w),A)(y,w),A)式中，式中，(g(g1 1(y)(y)，g
45、g(y)(y)和和g g(y,w)(y,w)为为SkolemSkolem函数函数52(8)(8)消去连词符号消去连词符号用用A A，B B代替代替(AB)(AB)，以消去明显的，以消去明显的符号符号。反复代替的结果，最后得到一个有。反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子只由文字的析取构成的合适公式叫做一个子句。句。(9)(9)更换变量名称更换变量名称可以更换变量符号的名称，使一个变量可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。符号不出现在一个以上的子句中。532 2、例
46、、例将下列谓词演算公式化为一个子句集将下列谓词演算公式化为一个子句集(x)x)P(x)P(x)(y)y)P(y)P(f(x,y)P(y)P(f(x,y)(y)y)Q(x,y)P(y)Q(x,y)P(y)543 3、说明、说明并不是所有问题的谓词公式化为子句集并不是所有问题的谓词公式化为子句集都需要上述都需要上述9 9个步骤。对于某些问题，可能个步骤。对于某些问题，可能不需要其中的一些步骤。不需要其中的一些步骤。553.4.2 3.4.2 消解推理规则消解推理规则1 1、消解式、消解式令令L L1 1为任一原子公式，为任一原子公式，L L2 2为另一原子公为另一原子公式；式；L L1 1和和L
47、L2 2具有相同的谓词符号，但一般具具有相同的谓词符号，但一般具有不同的变量。已知两子句有不同的变量。已知两子句L L1 1和和L L2 2,如果如果L L1 1和和L L2 2具有最一般合一者具有最一般合一者，那，那么通过消解可以从这两个父辈子句推导出一么通过消解可以从这两个父辈子句推导出一个新子句个新子句()()。这个新子句叫做消解。这个新子句叫做消解式。它是由取这两个子句的析取，然后消去式。它是由取这两个子句的析取，然后消去互补对而得到的。互补对而得到的。562 2、消解式求法、消解式求法(1)(1)假言推理假言推理父辈子句父辈子句 P P PQ(PQ(即即PQ)PQ)/消解式消解式Q
48、Q57(2)(2)合并合并 (3)(3)重言式重言式(4)(4)空子句空子句(矛盾矛盾)P PP P /NILNIL(5)(5)链式链式(三段论三段论)即取各子句的析取，然后消去互补对。即取各子句的析取，然后消去互补对。说明：说明：对合并、重言式、链式对合并、重言式、链式(三段论三段论)请同学们自请同学们自行阅读。行阅读。583.4.3 含有变量的消解式含有变量的消解式1、消解式求法、消解式求法为了对含有变量的子句使用消解规则，为了对含有变量的子句使用消解规则，必须找到一个置换，作用于父辈子句使其含必须找到一个置换，作用于父辈子句使其含有互补文字。有互补文字。592、例子、例子 P(x)Q(x
49、)Qf(y)置换置换=f(y)/xf(y)/xP Pf(y)f(y)603.4.4 3.4.4 消解反演求解过程消解反演求解过程1 1、基本思想、基本思想把要解决的问题作为一个要证明的命题，把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加其目标公式被否定并化成子句形，然后添加到命题公式集中去，把消解反演系统应用于到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句联合集，并推导出一个空子句(NIL)(NIL)，产生，产生一个矛盾，这说明目标公式的否定式不成立，一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解即有目标公式成立，定
50、理得证，问题得到解决，与数学中反证法的思想十分相似。决，与数学中反证法的思想十分相似。612 2、消解反演、消解反演反演求解的步骤反演求解的步骤给出一个公式集给出一个公式集S S和目标公式和目标公式L L，通过反证，通过反证或反演来求证目标公式或反演来求证目标公式L L，其证明步骤如下：，其证明步骤如下：(1)(1)否定否定L L，得，得L L；(2)(2)把把L L添加到添加到S S中去；中去；(3)(3)把新产生的集合把新产生的集合L L，S S化成子句集；化成子句集；(4)(4)应用消解原理，力图推导出一个表示矛应用消解原理，力图推导出一个表示矛盾的空子句盾的空子句NILNIL。62反演
