人工智能第3章搜索原理课件

第第3章章 搜索原理搜索原理知识点知识点重难点重难点学习要求学习要求知识点知识点盲目搜索盲目搜索启发式搜索启发式搜索博弈树搜索博弈树搜索遗传算法遗传算法模拟退火算法模拟退火算法重难点重难点宽度优先宽度优先深度优先深度优先等代价搜索等代价搜索有序搜索有序搜索A*算法算法博弈树搜索博弈树搜索学习要求学习要求重点掌握宽度优先和深度优先搜索算法重点掌握宽度优先和深度优先搜索算法掌握等代价搜索算法掌握等代价搜索算法掌握启发式搜索相关知识掌握启发式搜索相关知识理解博弈树搜索相关技术理解博弈树搜索相关技术掌握遗传算法基本原理掌握遗传算法基本原理理解模拟退火算法基本原理理解模拟退火算法基本原理第第3章章 搜索原理搜索原理3.1 盲目搜索盲目搜索3.2 启发式搜索启发式搜索3.3 博弈树搜索博弈树搜索3.4 遗传算法遗传算法3.5 模拟退火算法模拟退火算法3.1 盲目搜索盲目搜索 知识是解决问题的基础，解决问题的方法一知识是解决问题的基础，解决问题的方法一知识是解决问题的基础，解决问题的方法一知识是解决问题的基础，解决问题的方法一种就是算法，但对很多问题没有有效的算法种就是算法，但对很多问题没有有效的算法种就是算法，但对很多问题没有有效的算法种就是算法，但对很多问题没有有效的算法（或无现成算法），这时就可利用最一般方法（或无现成算法），这时就可利用最一般方法（或无现成算法），这时就可利用最一般方法（或无现成算法），这时就可利用最一般方法即搜索来解决。即搜索来解决。即搜索来解决。即搜索来解决。1 1、搜索的概念、搜索的概念、搜索的概念、搜索的概念 根据问题的实际情况，按照一定的策略或规根据问题的实际情况，按照一定的策略或规根据问题的实际情况，按照一定的策略或规根据问题的实际情况，按照一定的策略或规则，从知识库重寻找可利用的知识，从而构造则，从知识库重寻找可利用的知识，从而构造则，从知识库重寻找可利用的知识，从而构造则，从知识库重寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程，就出一条使问题获得解决的推理路线的过程，就出一条使问题获得解决的推理路线的过程，就出一条使问题获得解决的推理路线的过程，就称为称为称为称为搜索搜索搜索搜索。盲目搜索（续）盲目搜索（续）搜索包含两层含义：一是要找到从初始事实搜索包含两层含义：一是要找到从初始事实搜索包含两层含义：一是要找到从初始事实搜索包含两层含义：一是要找到从初始事实到问题最终答案的一条推理路线，另一是找到的到问题最终答案的一条推理路线，另一是找到的到问题最终答案的一条推理路线，另一是找到的到问题最终答案的一条推理路线，另一是找到的这条路线是时间和空间复杂度最小的求解路线。这条路线是时间和空间复杂度最小的求解路线。这条路线是时间和空间复杂度最小的求解路线。这条路线是时间和空间复杂度最小的求解路线。2 2、搜索的种类、搜索的种类、搜索的种类、搜索的种类 分为分为分为分为盲目搜索盲目搜索盲目搜索盲目搜索和和和和启发式搜索启发式搜索启发式搜索启发式搜索。盲目搜索盲目搜索盲目搜索盲目搜索又称无信息搜索，即在搜索过程中，又称无信息搜索，即在搜索过程中，又称无信息搜索，即在搜索过程中，又称无信息搜索，即在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有只按预先规定的搜索控制策略进行搜索，而没有只按预先规定的搜索控制策略进行搜索，而没有只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。即问题本身任何中间信息来改变这些控制策略。即问题本身任何中间信息来改变这些控制策略。即问题本身任何中间信息来改变这些控制策略。即问题本身的特性对搜索控制策略没有任何影响，这就使搜的特性对搜索控制策略没有任何影响，这就使搜的特性对搜索控制策略没有任何影响，这就使搜的特性对搜索控制策略没有任何影响，这就使搜索带有盲目性，效率不高。只用于解决比较简单索带有盲目性，效率不高。只用于解决比较简单索带有盲目性，效率不高。只用于解决比较简单索带有盲目性，效率不高。只用于解决比较简单的问题。的问题。的问题。的问题。盲目搜索（续）盲目搜索（续）启发式搜索启发式搜索又称有信息搜索，指搜索求又称有信息搜索，指搜索求解过程中，根据问题本身的特性或搜索过解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断改变或调整搜程中产生的一些信息来不断改变或调整搜索的方向，使搜索朝着最有希望的方向前索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。求进，加速问题的求解，并找到最优解。求解的效率更高，更易于求解复杂的问题。解的效率更高，更易于求解复杂的问题。盲目搜索（续）盲目搜索（续）3 3、研究和选用搜索算法的原则、研究和选用搜索算法的原则、研究和选用搜索算法的原则、研究和选用搜索算法的原则（1 1）有限搜索还是无限搜索？）有限搜索还是无限搜索？）有限搜索还是无限搜索？）有限搜索还是无限搜索？（2 2）搜索空间是静态还是动态生成？）搜索空间是静态还是动态生成？）搜索空间是静态还是动态生成？）搜索空间是静态还是动态生成？（3 3）已知目标还是未知目标？）已知目标还是未知目标？）已知目标还是未知目标？）已知目标还是未知目标？（4 4）只要目标还是也要路径？）只要目标还是也要路径？）只要目标还是也要路径？）只要目标还是也要路径？（5 5）状态空间搜索还是问题空间搜索？）状态空间搜索还是问题空间搜索？）状态空间搜索还是问题空间搜索？）状态空间搜索还是问题空间搜索？（6 6）有约束还是无约束？）有约束还是无约束？）有约束还是无约束？）有约束还是无约束？（7 7）数据驱动还是目标驱动？）数据驱动还是目标驱动？）数据驱动还是目标驱动？）数据驱动还是目标驱动？（8 8）单向搜索还是双向搜索？）单向搜索还是双向搜索？）单向搜索还是双向搜索？）单向搜索还是双向搜索？（9 9）盲目搜索还是启发式搜索？）盲目搜索还是启发式搜索？）盲目搜索还是启发式搜索？）盲目搜索还是启发式搜索？（1010）有对手搜索还是无对手搜索？）有对手搜索还是无对手搜索？）有对手搜索还是无对手搜索？）有对手搜索还是无对手搜索？3.1.1 图搜索策略图搜索策略 搜索法求解问题的基本思想搜索法求解问题的基本思想搜索法求解问题的基本思想搜索法求解问题的基本思想:首先将问题的初始状态首先将问题的初始状态首先将问题的初始状态首先将问题的初始状态(即状态空间图中的即状态空间图中的即状态空间图中的即状态空间图中的初始节点初始节点初始节点初始节点)当做当前状态，选择一适当的算符当做当前状态，选择一适当的算符当做当前状态，选择一适当的算符当做当前状态，选择一适当的算符作用于当前状态，生成一组后继状态（或称后作用于当前状态，生成一组后继状态（或称后作用于当前状态，生成一组后继状态（或称后作用于当前状态，生成一组后继状态（或称后继节点），然后检查这组后继状态中有没有目继节点），然后检查这组后继状态中有没有目继节点），然后检查这组后继状态中有没有目继节点），然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状标状态。如果有，则说明搜索成功，从初始状标状态。如果有，则说明搜索成功，从初始状标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若态到目标状态的一系列算符即是问题的解；若态到目标状态的一系列算符即是问题的解；若态到目标状态的一系列算符即是问题的解；若没有，则按某种控制策略从已生成的状态中没有，则按某种控制策略从已生成的状态中没有，则按某种控制策略从已生成的状态中没有，则按某种控制策略从已生成的状态中 再再再再选一个状态作为当前状态，重复上述过程，直选一个状态作为当前状态，重复上述过程，直选一个状态作为当前状态，重复上述过程，直选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算到目标状态出现或不再有可供操作的状态及算到目标状态出现或不再有可供操作的状态及算到目标状态出现或不再有可供操作的状态及算符为止。符为止。符为止。符为止。图搜索策略（续）图搜索策略（续）1、概念、概念已扩展节点：已扩展节点：对于状态图中的某个节点，对于状态图中的某个节点，若求出了它的后继节点，称已扩展节点。若求出了它的后继节点，称已扩展节点。未扩展节点：未扩展节点：对于状态图中的某个节点，对于状态图中的某个节点，尚未求出它的后继节点，称未扩展节点。尚未求出它的后继节点，称未扩展节点。扩展：扩展：就是用合适的算符对某个节点进行就是用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程实操作，生成一组后继节点，扩展过程实际上就是求后继节点的过程。际上就是求后继节点的过程。图搜索策略（续）图搜索策略（续）2、状态空间图的一般搜索算法、状态空间图的一般搜索算法 用两个表分别存放已扩展节点和未扩展用两个表分别存放已扩展节点和未扩展节点，节点，OPEN表存放未扩展节点，表存放未扩展节点，CLOSED表存放已扩展节点。两个表的结表存放已扩展节点。两个表的结构如下：构如下：OPEN表：表：CLOSED表：表：节点节点 父节点父节点编号编号 节点节点 父节点父节点图搜索策略（续）图搜索策略（续）状态空间图的一般搜索算法：状态空间图的一般搜索算法：状态空间图的一般搜索算法：状态空间图的一般搜索算法：（1 1）建立一个只含有起始节点）建立一个只含有起始节点）建立一个只含有起始节点）建立一个只含有起始节点S S的搜索图的搜索图的搜索图的搜索图G G，把把把把S S放到放到放到放到OPENOPEN表中。表中。表中。表中。（2 2）建立）建立）建立）建立CLOSEDCLOSED表，且置为空表。表，且置为空表。表，且置为空表。表，且置为空表。（3 3）若）若）若）若OPENOPEN表是空表，则问题无解，失败退出。表是空表，则问题无解，失败退出。表是空表，则问题无解，失败退出。表是空表，则问题无解，失败退出。（4 4）选择）选择）选择）选择OPENOPEN表中的第一个节点，把它从表中的第一个节点，把它从表中的第一个节点，把它从表中的第一个节点，把它从OPENOPEN表移出，并放入表移出，并放入表移出，并放入表移出，并放入CLOSEDCLOSED表中，将此节点表中，将此节点表中，将此节点表中，将此节点记为节点记为节点记为节点记为节点n n，它是它是它是它是CLOSEDCLOSED表中节点的编号。表中节点的编号。表中节点的编号。表中节点的编号。（5 5）若）若）若）若n n为一目标节点，则有解并成功退出。问为一目标节点，则有解并成功退出。问为一目标节点，则有解并成功退出。问为一目标节点，则有解并成功退出。问题的解即可从图题的解即可从图题的解即可从图题的解即可从图G G中沿着指针从中沿着指针从中沿着指针从中沿着指针从n n到到到到S S这条路径而这条路径而这条路径而这条路径而得到。得到。得到。得到。图搜索策略（续）图搜索策略（续）（6 6）扩展节点）扩展节点）扩展节点）扩展节点n n，同时生成不是同时生成不是同时生成不是同时生成不是n n的祖先的那些的祖先的那些的祖先的那些的祖先的那些后继节点的集合后继节点的集合后继节点的集合后继节点的集合MM。把把把把MM中的这些成员作为中的这些成员作为中的这些成员作为中的这些成员作为n n的后继节点加入图的后继节点加入图的后继节点加入图的后继节点加入图G G中。中。中。中。（7 7）对那些未曾在）对那些未曾在）对那些未曾在）对那些未曾在G G中出现过的（既未曾在中出现过的（既未曾在中出现过的（既未曾在中出现过的（既未曾在OPENOPEN表上或表上或表上或表上或CLOSEDCLOSED表上出现过的）表上出现过的）表上出现过的）表上出现过的）MM成员成员成员成员设置一个通向设置一个通向设置一个通向设置一个通向n n的指针。把的指针。把的指针。把的指针。把MM的这些成员加进的这些成员加进的这些成员加进的这些成员加进OPENOPEN表。对已经在表。对已经在表。对已经在表。对已经在OPENOPEN表或表或表或表或CLOSEDCLOSED表上表上表上表上的每一个的每一个的每一个的每一个MM成员，确定是否需要更改通到成员，确定是否需要更改通到成员，确定是否需要更改通到成员，确定是否需要更改通到n n的的的的指针方向。对已在指针方向。对已在指针方向。对已在指针方向。对已在CLOSEDCLOSED表上的每个表上的每个表上的每个表上的每个MM成员，成员，成员，成员，确定是否需要更改图确定是否需要更改图确定是否需要更改图确定是否需要更改图G G中通向它的每个后继节中通向它的每个后继节中通向它的每个后继节中通向它的每个后继节点的指针方向。点的指针方向。点的指针方向。点的指针方向。图搜索策略（续）图搜索策略（续）（8）按某一任意方式或按某个探试值，重）按某一任意方式或按某个探试值，重排排OPEN表。表。（9）转第（）转第（3）步。）步。举例说明：举例说明：P68，例例3.1图搜索策略（续）图搜索策略（续）3、搜索图与搜索树、搜索图与搜索树 图搜索过程生成一个明确的图图搜索过程生成一个明确的图图搜索过程生成一个明确的图图搜索过程生成一个明确的图G G（称为搜索图）和一称为搜索图）和一称为搜索图）和一称为搜索图）和一个个个个G G的子集的子集的子集的子集T T（称为搜索树），树称为搜索树），树称为搜索树），树称为搜索树），树T T上的每个节点也在上的每个节点也在上的每个节点也在上的每个节点也在图图图图G G中。中。中。中。例：二阶例：二阶例：二阶例：二阶HanoiHanoi塔问题。状态空间图如下。塔问题。状态空间图如下。塔问题。状态空间图如下。塔问题。状态空间图如下。（1，1）（2，1）（3，1）（2，3）（3，2）（3，3）（1，3）（1，2）（2，2）A(2,1)A(1,2)初始状态初始状态目标状态目标状态SS1S2S3S4S5S6S7S8图搜索策略（续）图搜索策略（续）搜索图搜索图G为：为：搜索树搜索树T为：为：SS1S2S3S4S5S6S7S8S8SS1S2S3S4S5S6S7图搜索策略（续）图搜索策略（续）4、图搜索方法的几点分析、图搜索方法的几点分析（1 1）对对对对OPENOPEN表进行排序（盲目或启发式搜索）。表进行排序（盲目或启发式搜索）。表进行排序（盲目或启发式搜索）。表进行排序（盲目或启发式搜索）。（2 2）被选作扩展的节点为目标节点时，成功，回）被选作扩展的节点为目标节点时，成功，回）被选作扩展的节点为目标节点时，成功，回）被选作扩展的节点为目标节点时，成功，回溯，可找到路径。否则，失败终止情况下没有解溯，可找到路径。否则，失败终止情况下没有解溯，可找到路径。否则，失败终止情况下没有解溯，可找到路径。否则，失败终止情况下没有解路径。路径。路径。路径。在利用状态空间搜索方法求解问题时，并不是将整个在利用状态空间搜索方法求解问题时，并不是将整个在利用状态空间搜索方法求解问题时，并不是将整个在利用状态空间搜索方法求解问题时，并不是将整个问题的状态空间图全部输入计算机，而是只存入问题有问题的状态空间图全部输入计算机，而是只存入问题有问题的状态空间图全部输入计算机，而是只存入问题有问题的状态空间图全部输入计算机，而是只存入问题有关的部分状态空间图，这部分是在搜索过程中生成的，关的部分状态空间图，这部分是在搜索过程中生成的，关的部分状态空间图，这部分是在搜索过程中生成的，关的部分状态空间图，这部分是在搜索过程中生成的，并且每前进一步，都要检查是否到达目标节点，这样就并且每前进一步，都要检查是否到达目标节点，这样就并且每前进一步，都要检查是否到达目标节点，这样就并且每前进一步，都要检查是否到达目标节点，这样就可尽量减少生成与问题求解无关的状态，从而提高了解可尽量减少生成与问题求解无关的状态，从而提高了解可尽量减少生成与问题求解无关的状态，从而提高了解可尽量减少生成与问题求解无关的状态，从而提高了解题效率，节省了存储空间。题效率，节省了存储空间。题效率，节省了存储空间。题效率，节省了存储空间。3.1.2 宽度优先搜索宽度优先搜索定义定义 如果搜索是以接近起始节点的程度依次扩展如果搜索是以接近起始节点的程度依次扩展如果搜索是以接近起始节点的程度依次扩展如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。节点的，那么这种搜索就叫做宽度优先搜索。节点的，那么这种搜索就叫做宽度优先搜索。节点的，那么这种搜索就叫做宽度优先搜索。宽度优先搜索又称广度优先搜索，是一种盲目宽度优先搜索又称广度优先搜索，是一种盲目宽度优先搜索又称广度优先搜索，是一种盲目宽度优先搜索又称广度优先搜索，是一种盲目搜索策略。搜索策略。搜索策略。搜索策略。其基本思想是：从初始节点开始，逐层对其基本思想是：从初始节点开始，逐层对其基本思想是：从初始节点开始，逐层对其基本思想是：从初始节点开始，逐层对节点进行依次扩展，并考虑它是否为目标节点，节点进行依次扩展，并考虑它是否为目标节点，节点进行依次扩展，并考虑它是否为目标节点，节点进行依次扩展，并考虑它是否为目标节点，在对下层节点进行扩展（或搜索）前，必须完在对下层节点进行扩展（或搜索）前，必须完在对下层节点进行扩展（或搜索）前，必须完在对下层节点进行扩展（或搜索）前，必须完成对当前层的所有节点的扩展（或搜索）。成对当前层的所有节点的扩展（或搜索）。成对当前层的所有节点的扩展（或搜索）。成对当前层的所有节点的扩展（或搜索）。宽度优先搜索（续）宽度优先搜索（续）宽度优先搜索算法（宽度优先搜索算法（P71）宽度优先搜索方法分析宽度优先搜索方法分析（1 1）将）将）将）将OPENOPEN表作为表作为表作为表作为“先进先出先进先出先进先出先进先出”的队列进行操的队列进行操的队列进行操的队列进行操作；作；作；作；（2 2）宽度优先搜索方法能够保证在搜索树中找到）宽度优先搜索方法能够保证在搜索树中找到）宽度优先搜索方法能够保证在搜索树中找到）宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短路径（即宽度优先搜索一条通向目标节点的最短路径（即宽度优先搜索一条通向目标节点的最短路径（即宽度优先搜索一条通向目标节点的最短路径（即宽度优先搜索策略是完备的）；策略是完备的）；策略是完备的）；策略是完备的）；（3 3）搜索树提供了所有存在的路径；）搜索树提供了所有存在的路径；）搜索树提供了所有存在的路径；）搜索树提供了所有存在的路径；（4 4）盲目性较大，当目标节点较远时，将产生大）盲目性较大，当目标节点较远时，将产生大）盲目性较大，当目标节点较远时，将产生大）盲目性较大，当目标节点较远时，将产生大量无用节点。量无用节点。量无用节点。量无用节点。例例例例3.23.2，P72P72，图图图图3.53.53.1.3 深度优先搜索深度优先搜索定义定义 深度优先搜索也是一种盲目搜索策略，其深度优先搜索也是一种盲目搜索策略，其深度优先搜索也是一种盲目搜索策略，其深度优先搜索也是一种盲目搜索策略，其基本思想是：首先扩展最新产生的（即最深）基本思想是：首先扩展最新产生的（即最深）基本思想是：首先扩展最新产生的（即最深）基本思想是：首先扩展最新产生的（即最深）节点，即从初始节点节点，即从初始节点节点，即从初始节点节点，即从初始节点S S开始，在其后继节点中开始，在其后继节点中开始，在其后继节点中开始，在其后继节点中选择一个节点，对其进行考察，若它不是目标选择一个节点，对其进行考察，若它不是目标选择一个节点，对其进行考察，若它不是目标选择一个节点，对其进行考察，若它不是目标节点，则对该节点进行扩展，并再从它的后继节点，则对该节点进行扩展，并再从它的后继节点，则对该节点进行扩展，并再从它的后继节点，则对该节点进行扩展，并再从它的后继节点中选择一个节点进行考察。依次类推，一节点中选择一个节点进行考察。依次类推，一节点中选择一个节点进行考察。依次类推，一节点中选择一个节点进行考察。依次类推，一直搜索下去，当到达某个既非目标节点又无法直搜索下去，当到达某个既非目标节点又无法直搜索下去，当到达某个既非目标节点又无法直搜索下去，当到达某个既非目标节点又无法继续扩展的节点时，才选择其兄弟节点进行考继续扩展的节点时，才选择其兄弟节点进行考继续扩展的节点时，才选择其兄弟节点进行考继续扩展的节点时，才选择其兄弟节点进行考察。察。察。察。深度优先搜索（续）深度优先搜索（续）有界深度优先搜索有界深度优先搜索 为了避免考虑太长的路径为了避免考虑太长的路径(防止搜索防止搜索过程沿着无益的路径扩展下去过程沿着无益的路径扩展下去)，往往给，往往给出一个节点扩展的最大深度，即深度界出一个节点扩展的最大深度，即深度界限。任何节点如果达到了深度界限，都限。任何节点如果达到了深度界限，都将被作为没有后继节点处理。将被作为没有后继节点处理。深度优先搜索（续）深度优先搜索（续）有界深度优先搜索算法（有界深度优先搜索算法（P73）深度优先搜索策略分析深度优先搜索策略分析（1 1）将将将将OPENOPEN表作为表作为表作为表作为“先进后出先进后出先进后出先进后出”的栈进行操作；的栈进行操作；的栈进行操作；的栈进行操作；（2 2）深度优先搜索所求得的解答路径不一定是最）深度优先搜索所求得的解答路径不一定是最）深度优先搜索所求得的解答路径不一定是最）深度优先搜索所求得的解答路径不一定是最短路径；短路径；短路径；短路径；（3 3）深度界限得选择很重要，过大，可能会影响）深度界限得选择很重要，过大，可能会影响）深度界限得选择很重要，过大，可能会影响）深度界限得选择很重要，过大，可能会影响搜索效率，过小，有可能求不到解。有界深度搜索效率，过小，有可能求不到解。有界深度搜索效率，过小，有可能求不到解。有界深度搜索效率，过小，有可能求不到解。有界深度优先搜索策略是不完备的。优先搜索策略是不完备的。优先搜索策略是不完备的。优先搜索策略是不完备的。例例例例3.33.3，P74P74，图图图图3.83.83.1.4 等代价搜索等代价搜索定义定义 有些问题并不要求有应用算符序列有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。为最少的解，而是要求具有某些特性的解。宽度优先搜索可被推广用来解决这种寻找宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有从起始状态至目标状态的具有最小代价最小代价的的路径问题，这种推广了的宽度优先搜索算路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。法叫做等代价搜索算法。等代价搜索（续）等代价搜索（续）记号记号S S：起始节点。起始节点。起始节点。起始节点。c(i,j)c(i,j):节点节点节点节点i i到它的后继节点到它的后继节点到它的后继节点到它的后继节点j j的连接弧线代价。的连接弧线代价。的连接弧线代价。的连接弧线代价。g(i)g(i):起始节点起始节点起始节点起始节点S S到任一节点到任一节点到任一节点到任一节点i i的路径代价，在搜索的路径代价，在搜索的路径代价，在搜索的路径代价，在搜索树上它也是从起始节点树上它也是从起始节点树上它也是从起始节点树上它也是从起始节点S S到节点到节点到节点到节点i i的最少代价路的最少代价路的最少代价路的最少代价路径上的代价。径上的代价。径上的代价。径上的代价。等代价搜索（续）等代价搜索（续）等代价搜索算法等代价搜索算法 与宽度优先搜索算法区别，以与宽度优先搜索算法区别，以与宽度优先搜索算法区别，以与宽度优先搜索算法区别，以g(i)g(i)的递增的递增的递增的递增顺序扩展其节点，即根据节点的代价大小对顺序扩展其节点，即根据节点的代价大小对顺序扩展其节点，即根据节点的代价大小对顺序扩展其节点，即根据节点的代价大小对OPENOPEN表中的所有节点进行从小到大的排序。表中的所有节点进行从小到大的排序。表中的所有节点进行从小到大的排序。表中的所有节点进行从小到大的排序。（1 1）把起始节点）把起始节点）把起始节点）把起始节点S S放到放到放到放到OPENOPEN表中。如果此起始表中。如果此起始表中。如果此起始表中。如果此起始节点为一目标节点，则求得一个解；否则令节点为一目标节点，则求得一个解；否则令节点为一目标节点，则求得一个解；否则令节点为一目标节点，则求得一个解；否则令g(S)=0g(S)=0；（2 2）如果如果如果如果OPENOPEN表是个空表，则没有解而失败表是个空表，则没有解而失败表是个空表，则没有解而失败表是个空表，则没有解而失败退出；退出；退出；退出；等代价搜索（续）等代价搜索（续）（3 3）从）从）从）从OPENOPEN表中选择一个节点表中选择一个节点表中选择一个节点表中选择一个节点i i，使其使其使其使其g(i)g(i)为最小。为最小。为最小。为最小。如果有几个节点都合格，那么就要选择一个目标节点如果有几个节点都合格，那么就要选择一个目标节点如果有几个节点都合格，那么就要选择一个目标节点如果有几个节点都合格，那么就要选择一个目标节点作为节点作为节点作为节点作为节点i i（如果有目标节点）；否则，就从中选一如果有目标节点）；否则，就从中选一如果有目标节点）；否则，就从中选一如果有目标节点）；否则，就从中选一个作为节点个作为节点个作为节点个作为节点i i。把节点把节点把节点把节点i i从从从从OPENOPEN表移至表移至表移至表移至CLOSEDCLOSED表中；表中；表中；表中；（4 4）如果节点）如果节点）如果节点）如果节点i i为目标节点为目标节点为目标节点为目标节点，则求得一个解；则求得一个解；则求得一个解；则求得一个解；（5 5）扩展节点）扩展节点）扩展节点）扩展节点i i。如果没有后继节点，则转向步骤如果没有后继节点，则转向步骤如果没有后继节点，则转向步骤如果没有后继节点，则转向步骤（2 2）（6 6）对于节点）对于节点）对于节点）对于节点i i的每个后继节点的每个后继节点的每个后继节点的每个后继节点j j，计算计算计算计算g(j)=g(i)+c(i,j)g(j)=g(i)+c(i,j)，并把所有后继节点并把所有后继节点并把所有后继节点并把所有后继节点j j放进放进放进放进OPENOPEN表。表。表。表。提供回到节点提供回到节点提供回到节点提供回到节点i i的指针。的指针。的指针。的指针。（7 7）转向步骤（）转向步骤（）转向步骤（）转向步骤（2 2）。）。）。）。等代价搜索（续）等代价搜索（续）举例分析举例分析例：推销员旅行问题。例：推销员旅行问题。例：推销员旅行问题。例：推销员旅行问题。假设假设假设假设A A，B B，C C，D D，E E是是是是5 5个城市，推销员从个城市，推销员从个城市，推销员从个城市，推销员从城市城市城市城市A A出发，到达城市出发，到达城市出发，到达城市出发，到达城市E E，走怎样的路线费用最走怎样的路线费用最走怎样的路线费用最走怎样的路线费用最省？省？省？省？5 5个城市间的交通图及每两个城市间的旅个城市间的交通图及每两个城市间的旅个城市间的交通图及每两个城市间的旅个城市间的交通图及每两个城市间的旅行费用如图所示。行费用如图所示。行费用如图所示。行费用如图所示。ABCDE675348作业作业1、分别用宽度优先搜索、有界深度优先搜、分别用宽度优先搜索、有界深度优先搜索（深度界限索（深度界限5）求解下图所示八数码难）求解下图所示八数码难题。初始状态题。初始状态S0，目标状态目标状态Sg，要求寻要求寻找从初始状态到目标状态的路径，并画出找从初始状态到目标状态的路径，并画出对应搜索树。对应搜索树。2 32 31 8 41 8 47 6 57 6 51 2 31 2 38 48 47 6 57 6 5S0Sg作业（续）作业（续）2 2、推销员旅行问题。设有、推销员旅行问题。设有、推销员旅行问题。设有、推销员旅行问题。设有5 5个相互直达的城市个相互直达的城市个相互直达的城市个相互直达的城市A A、B B、C C、D D、E E，如下图所示，各城市间的交通如下图所示，各城市间的交通如下图所示，各城市间的交通如下图所示，各城市间的交通费用已在图中标出。推销员从城市费用已在图中标出。推销员从城市费用已在图中标出。推销员从城市费用已在图中标出。推销员从城市A A出发，去出发，去出发，去出发，去每个城市各旅行一次，最后到达城市每个城市各旅行一次，最后到达城市每个城市各旅行一次，最后到达城市每个城市各旅行一次，最后到达城市E E，请找请找请找请找出一条费用最省的旅行路线。出一条费用最省的旅行路线。出一条费用最省的旅行路线。出一条费用最省的旅行路线。80ABCDE90858065170110140160100第第3章章 搜索原理搜索原理3.1 盲目搜索盲目搜索3.2 启发式搜索启发式搜索3.3 博弈树搜索博弈树搜索3.4 遗传算法遗传算法3.5 模拟退火算法模拟退火算法3.1 启发式搜索启发式搜索 启发信息启发信息是进行搜索技术所需要的一是进行搜索技术所需要的一些有关具体问题领域的特性的信息。些有关具体问题领域的特性的信息。利用启发信息的搜索方法称为启发式利用启发信息的搜索方法称为启发式搜索或有信息搜索。搜索或有信息搜索。1、启发信息分类、启发信息分类 按用途可分为按用途可分为3种。种。（1）用于决定要扩展的下一个节点，以免）用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目像在宽度优先或深度优先搜索中那样盲目地扩展。地扩展。启发式搜索（续）启发式搜索（续）（2）在扩展一个节点的过程中，用于决定）在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。盲目地同时生成所有可能的节点。（3）用于决定某些应该从搜索树中抛弃或）用于决定某些应该从搜索树中抛弃或修剪的节点。修剪的节点。2、估价函数、估价函数 用来用来估算希望程度估算希望程度的量度，叫做估价的量度，叫做估价函数。函数。启发式搜索（续）启发式搜索（续）一个节点的一个节点的“希望希望”有几种不同的有几种不同的定义方法。在状态空间问题中，一种定定义方法。在状态空间问题中，一种定义是估算义是估算目标节点目标节点到到此节点的距离此节点的距离；另；另一种定义是一种定义是整条路径（包括被估价过的整条路径（包括被估价过的节点）的长度或难度节点）的长度或难度。用符号用符号f来标记估价函数，用来标记估价函数，用f(n)表示节点表示节点n的估价函数值。的估价函数值。启发式搜索（续）启发式搜索（续）3、有序搜索、有序搜索 用估价函数用估价函数f来排列来排列OPEN表上的节点，表上的节点，选择选择OPEN表上具有表上具有最小最小f值值的节点作为的节点作为下一个要扩展的节点。这种搜索方法叫做下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索。它总是选择最有序搜索或最佳优先搜索。它总是选择最有希望的节点作为下一个要扩展的节点。有希望的节点作为下一个要扩展的节点。有序搜索又可分为两种：有序搜索又可分为两种：局部最佳优先局部最佳优先搜索搜索和和全局最佳优先搜索全局最佳优先搜索。启发式搜索（续）启发式搜索（续）有序搜索算法有序搜索算法（见（见P76-77）宽度优先搜索、等代价搜索和深度优宽度优先搜索、等代价搜索和深度优先搜索均是有序搜索的特例。先搜索均是有序搜索的特例。宽度优先搜索，宽度优先搜索，f(i)是节点是节点i的深度。的深度。等代价搜索，等代价搜索，f(i)是从起始节点至节点是从起始节点至节点i这段这段路径的代价。路径的代价。深度优先搜索，深度优先搜索，f(i)是节点是节点i距目标节点的深距目标节点的深度度.启发式搜索（续）启发式搜索（续）有序搜索的有效性直接取决于有序搜索的有效性直接取决于f的选的选择，如果选择的择，如果选择的f不合适，有序搜索就可不合适，有序搜索就可能失去一个最好的解甚至全部的解。能失去一个最好的解甚至全部的解。正确地选择估价函数对确定搜索结正确地选择估价函数对确定搜索结果具有决定性地作用。使用不能识别某些果具有决定性地作用。使用不能识别某些节点真实希望的估价函数会形成非最小代节点真实希望的估价函数会形成非最小代价路径；而使用一个过多地估计了全部节价路径；而使用一个过多地估计了全部节点希望地估价函数又会扩展过多的节点。点希望地估价函数又会扩展过多的节点。启发式搜索（续）启发式搜索（续）应用举例应用举例：（P78）采用简单的估价函数采用简单的估价函数f(n)=d(n)+w(n),其中，其中，d(n)是搜索树中节点是搜索树中节点n的深度；的深度；w(n)用来计算节点用来计算节点n与目标状态节点与目标状态节点Sg相比较，错位的数码个数。相比较，错位的数码个数。启发式搜索（续）启发式搜索（续）4、A算法算法定义：在图搜索过程中，如果定义：在图搜索过程中，如果OPEN表节表节点顺序是依据点顺序是依据f(x)=g(x)+h(x)进行的，进行的，称该过程为称该过程为A算法算法。在这里，把估价函数在这里，把估价函数在这里，把估价函数在这里，把估价函数f(x)f(x)定义为从定义为从定义为从定义为从初始初始初始初始节节节节点点点点经过节点经过节点经过节点经过节点x x到达到达到达到达目标目标目标目标节点的节点的节点的节点的最小代价路径最小代价路径最小代价路径最小代价路径的的的的代价代价代价代价估计值估计值估计值估计值。其中，。其中，。其中，。其中，g(x)g(x)为初始节点为初始节点为初始节点为初始节点S S0 0到节点到节点到节点到节点x x的估计的最小路径代价；的估计的最小路径代价；的估计的最小路径代价；的估计的最小路径代价；h(x)h(x)为从为从为从为从节点节点节点节点x x到目到目到目到目标节点标节点标节点标节点S Sg g的估计的最小路径代价。的估计的最小路径代价。的估计的最小路径代价。的估计的最小路径代价。启发式搜索（续）启发式搜索（续）搜索信息主要由搜索信息主要由h(x)来体现，故来体现，故h(x)称为称为启发函数启发函数。应用实例一，应用课本应用实例一，应用课本P78所列估价函数所列估价函数f(n)=d(n)+w(n)求解八数码问题。求解八数码问题。13 13 7 2 47 2 46 8 56 8 51 2 31 2 38 48 47 6 57 6 5S0Sg启发式搜索（续）启发式搜索（续）应用实例二，应用实例二，应用估价函数应用估价函数应用估价函数应用估价函数f(n)=d(n)+p(n)f(n)=d(n)+p(n)求解八数码问题。其中，求解八数码问题。其中，求解八数码问题。其中，求解八数码问题。其中，d(n)d(n)是搜索树中节是搜索树中节是搜索树中节是搜索树中节点点点点n n的深度；的深度；的深度；的深度；p(n)p(n)的值是节点的值是节点的值是节点的值是节点n n与目标状态节与目标状态节与目标状态节与目标状态节点点点点S Sg g相比较，每个错位的数码在假设不受阻拦相比较，每个错位的数码在假设不受阻拦相比较，每个错位的数码在假设不受阻拦相比较，每个错位的数码在假设不受阻拦的情况下，移动到目标状态相应位置所需走步的情况下，移动到目标状态相应位置所需走步的情况下，移动到目标状态相应位置所需走步的情况下，移动到目标状态相应位置所需走步的总和。的总和。的总和。的总和。13 13 7 2 47 2 46 8 56 8 51 2 31 2 38 48 47 6 57 6 5S0Sg启发式搜索（续）启发式搜索（续）5、A*算法算法定义：如果对于所有的定义：如果对于所有的x，h(x)h*(x)成成立。采用立。采用h*(x)的下界的下界h(x)为启发函数为启发函数的的A算法，称为算法，称为A*算法算法。说明：说明：搜索算法的可采纳性搜索算法的可采纳性 在搜索图存在从初始节点到目标节在搜索图存在从初始节点到目标节点解答路径的情况下，若一个搜索方法总点解答路径的情况下，若一个搜索方法总能找到能找到最短（代价最小）的解答路径最短（代价最小）的解答路径，则，则称该算法具有称该算法具有可采纳性可采纳性。启发式搜索（续）启发式搜索（续）为了考察启发式搜索算法为了考察启发式搜索算法A的可采纳的可采纳性，首先引入估价函数性，首先引入估价函数f*：f*(x)=g*(x)+h*(x)f*(x)、g*(x)、h*(x)分别指示当经分别指示当经由节点由节点x的最短（代价最小）解答路径找的最短（代价最小）解答路径找到时实际的路径代价（长度）、该路径前到时实际的路径代价（长度）、该路径前段（自初始节点到节点段（自初始节点到节点x）代价和后段代价和后段（自节点（自节点x到目标节点）代价。到目标节点）代价。启发式搜索（续）启发式搜索（续）一般来讲，一般来讲，g(x)的值容易从迄今已的值容易从迄今已生成的搜索树中计算出来，不必专门定义生成的搜索树中计算出来，不必专门定义计算公式。这时计算公式。这时g(x)g*(x)。然而然而h(x)的设计依赖于启发式知识的应用，的设计依赖于启发式知识的应用，所以如何挖掘贴切的启发式知识是设计估所以如何挖掘贴切的启发式知识是设计估价函数乃至价函数乃至A算法的关键。可以证明，若算法的关键。可以证明，若确保对于搜索图中的节点确保对于搜索图中的节点x，总是有总是有h(x)h*(x)，则则A算法具有可采纳性，算法具有可采纳性，既总能搜索到最短（代价最小）的解答路既总能搜索到最短（代价最小）的解答路径。所以径。所以A*算法是可采纳的。算法是可采纳的。作业作业分别利用估价函数分别利用估价函数f(n)=d(n)+w(n)和和f(n)=d(n)+p(n)，采用最佳优先搜索采用最佳优先搜索方法求解下列八数码问题。方法求解下列八数码问题。初始状态初始状态S0，目标状态目标状态Sg，要求寻找从初始状态到要求寻找从初始状态到目标状态的路径，并画出对应搜索树。目标状态的路径，并画出对应搜索树。28 28 1 6 31 6 37 5 47 5 41 2 31 2 38 48 47 6 57 6 5S0Sg第第3章章 搜索原理搜索原理3.1 盲目搜索盲目搜索3.2 启发式搜索启发式搜索3.3 博弈树搜索博弈树搜索3.4 遗传算法遗传算法3.5 模拟退火算法模拟退火算法3.3 博弈树搜索博弈树搜索1、概述、概述 讨论最简单的讨论最简单的“二人零和、全信息、二人零和、全信息、非偶然非偶然”博弈，特征有：博弈，特征有：（1）对垒双方轮流采取行动，结果有）对垒双方轮流采取行动，结果有3种：种：甲胜、乙胜、和局；甲胜、乙胜、和局；（2）在对垒过程中，任何一方都了解当前）在对垒过程中，任何一方都了解当前的格局及过去的历史；的格局及过去的历史；（3）双方都是很理智的决定自己的行动。）双方都是很理智的决定自己的行动。博弈树搜索（续）博弈树搜索（续）描述博弈过程的描述博弈过程的描述博弈过程的描述博弈过程的与或树与或树与或树与或树称为称为称为称为博弈树博弈树博弈树博弈树，有如，有如，有如，有如下特点：下特点：下特点：下特点：（1 1）博弈的初始格局是初始节点；）博弈的初始格局是初始节点；）博弈的初始格局是初始节点；）博弈的初始格局是初始节点；（2 2）在博弈树中，）在博弈树中，）在博弈树中，）在博弈树中，“或或或或”节点和节点和节点和节点和“与与与与”节点是节点是节点是节点是逐层交替出现的。自己一方扩展的节点之间是逐层交替出现的。自己一方扩展的节点之间是逐层交替出现的。自己一方扩展的节点之间是逐层交替出现的。自己一方扩展的节点之间是“或或或或”关系，对方扩展的节点之间是关系，对方扩展的节点之间是关系，对方扩展的节点之间是关系，对方扩展的节点之间是“与与与与”关关关关系。双方轮流地扩展节点。系。双方轮流地扩展节点。系。双方轮流地扩展节点。系。双方轮流地扩展节点。（3 3）所有自己一方获胜的终局都是本原问题，）所有自己一方获胜的终局都是本原问题，）所有自己一方获胜的终局都是本原问题，）所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终相应的节点是可解节点；所有使对方获胜的终相应的节点是可解节点；所有使对方获胜的终相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。局都认为是不可解节点。局都认为是不可解节点。局都认为是不可解节点。博弈树搜索（续）博弈树搜索（续）2、极大极小分析法、极大极小分析法（1）设博弈的双方一方为）设博弈的双方一方为MAX，另一方另一方为为MIN，然后为其中的一方（例如然后为其中的一方（例如MAX）寻找一个最优行动方案；寻找一个最优行动方案；（2）计算可能的得分；）计算可能的得分；（3）定义一个估价函数，用来估算当前博）定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分弈树端节点的得分。此时估算出来的得分称为静态估值；称为静态估值；博弈树搜索（续）博弈树搜索（续）（4）推算出父节点的得分。对）推算出父节点的得分。对“或或”节点，节点，选其子节点中一个最大的得分作为父节选其子节点中一个最大的得分作为父节点的得分；对点的得分；对“与与”节点，选其子节点节点，选其子节点中一个最小的得分作为父节点的得分。中一个最小的得分作为父节点的得分。这样计算出的父节点的得分称为倒推值；这样计算出的父节点的得分称为倒推值；（5）若一个行动方案能获得较大的倒推值，）若一个行动方案能获得较大的倒推值，则它就是当前最好得行动方案。则它就是当前最好得行动方案。博弈树搜索（续）博弈树搜索（续）可行的办法是只生成一定深度的博弈可行的办法是只生成一定深度的博弈树，然后进行极大极小分析，找出当前最树，然后进行极大极小分析，找出当前最好的行动方案。此后，再在已选定的分支好的行动方案。此后，再在已选定的分支上扩展一定深度，再选最好的行动方案，上扩展一定深度，再选最好的行动方案，如此进行下去，直到取得胜败的结果为止。如此进行下去，直到取得胜败的结果为止。至于每生成博弈树深度，当然是越大越好，至于每生成博弈树深度，当然是越大越好，具体视情况而定。具体视情况而定。博弈树搜索（续）博弈树搜索（续）实例：实例：“一一”字棋游戏极大极小分析法字棋游戏极大极小分析法 九个空格，谁先使自己的棋子构成九个空格，谁先使自己的棋子构成“三子成一线三子成一线”（同一行或同一列或对角（同一行或同一列或对角线全是某人的棋子），谁就取得了胜利。线全是某人的棋子），谁就取得了胜利。用叉号代表用叉号代表MAX，用圆圈代表用圆圈代表MIN。如下图为如下图为MIN取胜的棋局。取胜的棋局。博弈树搜索（续）博弈树搜索（续）为了不致于生成太大的博弈树，假设每次扩为了不致于生成太大的博弈树，假设每次扩为了不致于生成太大的博弈树，假设每次扩为了不致于生成太大的博弈树，假设每次扩展两层。估价函数定义如下：展两层。估价函数定义如下：展两层。估价函数定义如下：展两层。估价函数定义如下：设棋局为设棋局为设棋局为设棋局为P P，估价函数为估价函数为估价函数为估价函数为e(P)e(P)；（1 1）若若若若P P对任何一方来说都不是获胜位置，则对任何一方来说都不是获胜位置，则对任何一方来说都不是获胜位置，则对任何一方来说都不是获胜位置，则e(P)=e(e(P)=e(那些仍为那些仍为那些仍为那些仍为MINMIN空着的完全的行、列、空着的完全的行、列、空着的完全的行、列、空着的完全的行、列、对角线的总数对角线的总数对角线的总数对角线的总数)-)-e(e(那些仍为那些仍为那些仍为那些仍为MAXMAX空着的完全行、空着的完全行、空着的完全行、空着的完全行、列、对角线的总数列、对角线的总数列、对角线的总数列、对角线的总数)；（2 2）若）若）若）若P P是是是是MAXMAX必胜的棋局，则必胜的棋局，则必胜的棋局，则必胜的棋局，则e(P)=+e(P)=+；（3 3）若若若若P P是是是是MINMIN必胜的棋局，则必胜的棋局，则必胜的棋局，则必胜的棋局，则e(P)=-e(P)=-。博弈树搜索（续）博弈树搜索（续）比如比如P如右图所示，则：如右图所示，则：e(P)=6-4=2 要注意利用棋盘位置的对称性，在生成要注意利用棋盘位置的对称性，在生成后继节点位置时，下列结局都是相同的后继节点位置时，下列结局都是相同的棋局。棋局。博弈树搜索（续）博弈树搜索（续）下面是经过两层搜索生成的博弈树，静态估下面是经过两层搜索生成的博弈树，静态估下面是经过两层搜索生成的博弈树，静态估下面是经过两层搜索生成的博弈树，静态估值记在端节点下面，倒推值记在圆圈内。值记在端节点下面，倒推值记在圆圈内。值记在端节点下面，倒推值记在圆圈内。值记在端节点下面，倒推值记在圆圈内。1-1-211010-1-10-10-212MAXMAX应当选取最大的倒推值走步（正好是应当选取最大的倒推值走步（正好是应当选取最大的倒推值走步（正好是应当选取最大的倒推值走步（正好是MAXMAX的的的的最好的优先走步）。如下图所示：最好的优先走步）。如下图所示：最好的优先走步）。如下图所示：最好的优先走步）。如下图所示：现在假设现在假设现在假设现在假设MAXMAX走了这步，而走了这步，而走了这步，而走了这步，而MINMIN走步是直接在走步是直接在走步是直接在走步是直接在“X X”上方的空格里放上一个上方的空格里放上一个上方的空格里放上一个上方的空格里放上一个“OO”（对对对对MINMIN来说来说来说来说是一步坏棋）。下一步，是一步坏棋）。下一步，是一步坏棋）。下一步，是一步坏棋）。下一步，MAXMAX又在新的格局下又在新的格局下又在新的格局下又在新的格局下搜索两层，产生新的搜索树，一直这样进行下去，搜索两层，产生新的搜索树，一直这样进行下去，搜索两层，产生新的搜索树，一直这样进行下去，搜索两层，产生新的搜索树，一直这样进行下去，直到结果出现（直到结果出现（直到结果出现（直到结果出现（MAXMAX胜、胜、胜、胜、MINMIN胜、和局）。胜、和局）。胜、和局）。胜、和局）。博弈树搜索（续）博弈树搜索（续）博弈树搜索（续）博弈树搜索（续）3、-剪枝技术剪枝技术 -剪枝技术的基本思想是：在生成博剪枝技术的基本思想是：在生成博弈树的同时计算评估各节点的倒推值，并弈树的同时计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。了机器开销，提高了搜索效率。博弈树搜索（续）博弈树搜索（续）-剪枝方法如下：剪枝方法如下：（1）对于一个与节点）对于一个与节点MIN，若能估计出其若能估计出其倒推值的上界倒推值的上界，并且这个并且这个值不大于值不大于MIN的父节点（一定是或节点）的估计倒的父节点（一定是或节点）的估计倒推值的下界推值的下界，即即，则就不必再扩展则就不必再扩展该该MIN节点的其余子节点了（因为这些节节点的其余子节点了（因为这些节点的估值对点的估值对MIN父节点的倒推值已无任何父节点的倒推值已无任何影响了）。这一过程称为影响了）。这一过程称为剪枝。剪枝。博弈树搜索（续）博弈树搜索（续）（2）对于一个或节点）对于一个或节点MAX，若能估计出若能估计出其倒推值的下界其倒推值的下界，并且这个并且这个值不小于值不小于MAX的父节点（一定是与节点）的估计的父节点（一定是与节点）的估计倒推值的上界倒推值的上界，即即，则不必再扩展则不必再扩展该该MAX节点的其余子节点了（因为这些节点的其余子节点了（因为这些节点的估值对节点的估值对MAX父节点的倒推值已无父节点的倒推值已无任何影响了）。这一过程称为任何影响了）。这一过程称为剪枝。剪枝。第第3章章 搜索原理搜索原理3.1 盲目搜索盲目搜索3.2 启发式搜索启发式搜索3.3 博弈树搜索博弈树搜索3.4 遗传算法遗传算法3.5 模拟退火算法模拟退火算法3.4 遗传算法遗传算法 遗传算法是仿真生物遗传学和自然选择机遗传算法是仿真生物遗传学和自然选择机遗传算法是仿真生物遗传学和自然选择机遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，是理，通过人工方式所构