《搜索推理策略人工智能.ppt》由会员分享，可在线阅读，更多相关《搜索推理策略人工智能.ppt（239页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Artificial Intelligence(AI)人工智能人工智能主讲：何春梅Email：第第3章章:确定性推理确定性推理内容提要第三章：确定性推理第三章：确定性推理第三章：确定性推理第三章：确定性推理1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.归结演绎推理归结演绎推理5.5.基于规则的演绎推理基于规则的演绎推理内容提要第三章：确定性推理第三章：确定性推理第三章：确定性推理第三章：确定性推理1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.归结演绎推理归结演绎推理5.5.基于规则的演绎
2、推理基于规则的演绎推理推理的基本概念v推理的基本概念推理的基本概念1.1.什么是推理什么是推理2.2.推理方法及其分类推理方法及其分类3.3.推理的控制策略及其分类推理的控制策略及其分类推理的基本概念v什么是推理什么是推理所谓推理就是按某种策略由已知判断推出另一个判所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。断的思维过程。在人工智能中，推理是由程序实现的，称为推理机。在人工智能中，推理是由程序实现的，称为推理机。v推理的两个基本问题推理的两个基本问题推理的方法推理的方法推理的控制策略推理的控制策略推理的基本概念v推理方法及其分类推理方法及其分类1.1.按推理的逻辑基础分：按推理的
3、逻辑基础分：演绎，归纳，类比归纳推理演绎，归纳，类比归纳推理p演绎推理演绎推理:从已知的一般性知识出发，推出蕴含在已知从已知的一般性知识出发，推出蕴含在已知知识中的适合于某种个别情况的结论。是一种由一般到知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其个别的推理方法，其核心是三段论核心是三段论。假言三段论：假言三段论：AB，BC AC常用的三段论是由一个常用的三段论是由一个大前提大前提、一个小前提一个小前提和和一个结论一个结论这这三部分组成的。三部分组成的。大前提是已知的一般性知识或推理过程得到的判断；大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某
4、个具体实例的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。结论是由大前提推出的，并且适合于小前提的判断。其结其结论是蕴含在前提中的。论是蕴含在前提中的。推理的基本概念v推理方法及其分类推理方法及其分类1.1.按推理的逻辑基础分：按推理的逻辑基础分：演绎，归纳，类比归纳推理演绎，归纳，类比归纳推理归纳推理：归纳推理：按照所选事例的按照所选事例的广泛性广泛性可分为可分为完全归纳完全归纳推理推理和和不完全归纳推理不完全归纳推理。完全归纳推理：完全归纳推理：在进行归纳时需要考察相应事物在进行归纳时需要考察相应事物的的全部对象全部对象，并根据这些对象是
5、否都具有某种属，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。性，推出该类事物是否具有此属性。不完全归纳推理：不完全归纳推理：在进行归纳时只考察了相应事在进行归纳时只考察了相应事物的物的部分对象部分对象，就得出了关于该事物的结论。，就得出了关于该事物的结论。推理的基本概念v推理方法及其分类推理方法及其分类1.1.按推理的逻辑基础分：按推理的逻辑基础分：演绎，归纳，类比归纳推理演绎，归纳，类比归纳推理类比归纳推理：类比归纳推理：若在两个或两类事物有许多属性相若在两个或两类事物有许多属性相同或相似，则推出它们在其他属性上也相同或相似。同或相似，则推出它们在其他属性上也相同或相似。类
6、比归纳推理的基础是类比归纳推理的基础是相似原理相似原理，其可靠程度取，其可靠程度取决于两个或两类事物的相似程度以及这两个或两决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关类事物的相同属性与推出的那个属性之间的相关程度。程度。推理的基本概念v推理方法及其分类推理方法及其分类1.1.按推理的逻辑基础分：按推理的逻辑基础分：演绎，归纳，类比归纳推理演绎，归纳，类比归纳推理演绎推理与归纳推理的区别：演绎推理与归纳推理的区别：演绎推理是在已知领域内的一般性知识的前提下，通演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。过
7、演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提它所得出的结论实际上早已蕴含在一般性知识的前提中中，演绎推理只不过是将已有事实揭露出来，因此，演绎推理只不过是将已有事实揭露出来，因此它它不能增殖新知识不能增殖新知识。归纳推理所推出的结论是没有包含在前提内容中的归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，这种由个别事物或现象推出一般性知识的过程，是增是增殖新知识的过程殖新知识的过程。推理的基本概念v推理方法及其分类推理方法及其分类2.2.按推理过程所用知识的确定性分按推理过程所用知识的确定性分p 确定性推理确
8、定性推理p 不确定性推理不确定性推理3.3.按推理过程推出的结论是否单调增加分按推理过程推出的结论是否单调增加分p单调推理单调推理p非单调推理非单调推理4.4.按推理过程是否利用问题的启发性知识分按推理过程是否利用问题的启发性知识分p启发式推理启发式推理p非启发式推理非启发式推理推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类推理过程不仅依赖于所用的推理方法，同时也推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。依赖于推理的控制策略。推理的控制策略是指如何使用领域知识使推理推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略过程尽快达到目标的策略。推理的控制
9、策略可分为：推理的控制策略可分为：p搜索策略搜索策略p推理策略推理策略推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类搜索策略：搜索策略：在知识库中寻找可利用的知识，从而构造一在知识库中寻找可利用的知识，从而构造一条条代价较小代价较小的推理路线。主要解决推理线路、推理效果、的推理路线。主要解决推理线路、推理效果、推理效率等问题。推理效率等问题。按是否使用启发式信息可分为：按是否使用启发式信息可分为：p盲目搜索盲目搜索p启发式搜索启发式搜索按问题的表示方式可分为：按问题的表示方式可分为：p状态空间搜索状态空间搜索p与或树搜索与或树搜索推理的基本概念v推理的控制策略及其分类推理的控制策
10、略及其分类推理策略：推理策略：包括推理方向控制策略、求解策略、限制包括推理方向控制策略、求解策略、限制策略、冲突消解策略等策略、冲突消解策略等p推理方向控制策略：推理方向控制策略：用于确定推理的控制方向，可用于确定推理的控制方向，可分为分为正向推理正向推理逆向推理逆向推理混合推理混合推理双向推理双向推理推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类p推理方向控制策略：推理方向控制策略：正向推理：正向推理：从已知事实出发、正向使用推理规则，从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。亦称为数据驱动推理或前向链推理。正向推理从用户提供的正向推理从用户提供的初始已
11、知事实初始已知事实出发，在出发，在知识库知识库KB中找出当前可适用的知识，构成可适用的中找出当前可适用的知识，构成可适用的知识集知识集KS；然后按然后按某种冲突消解策略某种冲突消解策略从从KS中选出一条知识进行推理，中选出一条知识进行推理，并将推出的并将推出的新事实新事实加入到数据库加入到数据库DB中，作为下一步推理中，作为下一步推理的已知事实；的已知事实；在此之后，再在知识库中选取可适用的知识进行推理。在此之后，再在知识库中选取可适用的知识进行推理。如此重复进行这一过程，直到求得所要求的解。如此重复进行这一过程，直到求得所要求的解。推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类
12、p推理方向控制策略：推理方向控制策略：正向推理中，如何根据已知事实到知识库中选取可用知正向推理中，如何根据已知事实到知识库中选取可用知识？当知识库中有多条知识可用时应该先使用那一条知识？当知识库中有多条知识可用时应该先使用那一条知识？这些问题涉及到了识？这些问题涉及到了知识的匹配方法知识的匹配方法和和冲突消解策略。冲突消解策略。正向推理的优点：正向推理的优点：比较直观，允许用户主动提供有用的比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问事实信息，适合于诊断、设计、预测、监控等领域的问题求解。题求解。正向推理的缺点：正向推理的缺点：推理无明确目标，求解问题是可能
13、会推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。执行许多与解无关的操作，导致推理效率较低。推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类p推理方向控制策略：推理方向控制策略：逆向推理：逆向推理：从某个假设目标出发，逆向使用规则，从某个假设目标出发，逆向使用规则，亦称为亦称为目标驱动推理目标驱动推理或或逆向链推理逆向链推理。逆向推理首先选定一个假设目标，然后寻找支持该逆向推理首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假假设的证据，若所需的证据都能找到，则说明原假设是成立的；若找不到所需要的证据，则说明原假设是成立的；若
14、找不到所需要的证据，则说明原假设不成立，此时需要另作新的假设。设不成立，此时需要另作新的假设。推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类p推理方向控制策略：推理方向控制策略：逆向推理的主要优点：逆向推理的主要优点：不必寻找和使用那些与假设不必寻找和使用那些与假设目标无关的信息和知识，推理过程的目标明确，有目标无关的信息和知识，推理过程的目标明确，有利于向用户提供解释，在诊断性专家系统中较为有利于向用户提供解释，在诊断性专家系统中较为有效。效。逆向推理的主要缺点：逆向推理的主要缺点：当用户对解的情况认识不请当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若时，
15、由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效选择不好，可能需要多次提出假设，会影响系统效率。率。推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类p推理方向控制策略：推理方向控制策略：混合推理：混合推理：把正向推理和逆向推理结合起来所进行把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方的推理称为混合推理。是一种解决较复杂问题的方法。法。混合推理方法的三种类型：混合推理方法的三种类型：z1.先正向后逆向：先正向后逆向：这种方法先进行正向推理，从这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理已知事
16、实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。对这些结果进行证实或提高它们的可信度。推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类p推理方向控制策略：推理方向控制策略：混合推理方法的三种类型：混合推理方法的三种类型：z 2.先逆向后正向：先逆向后正向：这种方法先进行逆向推理，这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。向推理对这些中间假设进行证实。z 3.双向混合：双向混合：是指正向推理和逆向推理同时进是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结
17、合起来。行，使推理过程在中间的某一步结合起来。推理的基本概念v推理的控制策略及其分类推理的控制策略及其分类推理策略：推理策略：包括推理方向控制策略、求解策略、限制包括推理方向控制策略、求解策略、限制策略、冲突消解策略等策略、冲突消解策略等p求解策略：求解策略：是指仅求一个解，还是求所有解或最优是指仅求一个解，还是求所有解或最优解等。解等。p限制策略：限制策略：是指对推理的深度、宽度、时间、空间是指对推理的深度、宽度、时间、空间等进行的限制。等进行的限制。p冲突消解策略：冲突消解策略：是指当推理过程有多条知识可用时，是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推如何
18、从这多条可用知识中选出一条最佳知识用于推理的策略。理的策略。内容提要第三章：确定性推理第三章：确定性推理第三章：确定性推理第三章：确定性推理1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.归结演绎推理归结演绎推理5.5.基于规则的演绎推理基于规则的演绎推理搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的搜索策略状态空间的搜索策略与与/或树的搜索策略或树的搜索策略搜索的完备性与效率搜索的完备性与效率搜索的基本概念v搜索的基本概念搜索的基本概念搜索是人工智能中的一个基本问题，并与推理密切相搜索是人工智能中的一个基本问题，并与推理密
19、切相关，搜索策略的优劣，将直接影响到智能系统的性能关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。与推理效率。搜索的定义：搜索的定义：依靠经验，利用已有知识，根据问题的依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。最小的推理路线，使问题得以解决的过程称为搜索。搜索的适用情况：搜索的适用情况：不良结构或非结构化问题；难以获不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解得求解所需的全部信息；更没有现成的算法可供求解使用。使用。搜索的基
20、本概念v搜索的类型搜索的类型按是否使用启发式信息：按是否使用启发式信息：p盲目搜索：盲目搜索：按预定的控制策略进行搜索，在搜索过按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。程中获得的中间信息并不改变控制策略。p启发式搜索：启发式搜索：在搜索中加入了与问题有关的启发性在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。速问题的求解过程并找到最优解。按问题的表示方式：按问题的表示方式：p状态空间搜索：状态空间搜索：用状态空间法求解问题进行的搜索用状态空间法求解问题进行的搜索
21、p与或树搜索：与或树搜索：用问题归约法求解问题进行的搜索用问题归约法求解问题进行的搜索 状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法状态空间的搜索策略v状态空间搜索的基本思想状态空间搜索的基本思想先把问题的初始状态作为当前先把问题的初始状态作为当前扩展节点扩展节点对其进行对其进行扩展扩展，生
22、成一组子节点。生成一组子节点。然后检查问题的目标状态是否出现在这些子节点中。若然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。可供操作的节点为止。所谓对一个节点进行所谓对一个节点进行“扩展扩展”是指对该节点用某个可用是指对该节点用某个可用操作进行作用，生成该节点
23、的一组子节点操作进行作用，生成该节点的一组子节点。状态空间的搜索策略v状态空间搜索算法的数据结构和符号约定状态空间搜索算法的数据结构和符号约定OPEN表：表：未扩展节点表，用于存放刚生成节点未扩展节点表，用于存放刚生成节点CLOSED表：表：已扩展节点表，用于存放已经扩已扩展节点表，用于存放已经扩展或将要扩展节点的展或将要扩展节点的S：用表示问题的初始状态用表示问题的初始状态G：表示搜索过程所得到的搜索图表示搜索过程所得到的搜索图M：表示当前扩展节点新生成的且不为自己先辈表示当前扩展节点新生成的且不为自己先辈的子节点集的子节点集状态空间的搜索策略v图搜索的一般过程图搜索的一般过程(1)把初始节
24、点把初始节点S放入未扩展节点表放入未扩展节点表OPEN表，并建立目表，并建立目前仅包含前仅包含S的图的图G；(2)检查检查OPEN表是否为空，若为空，则问题无解，失表是否为空，若为空，则问题无解，失败退出；败退出；(3)把把OPEN表的表的第一个节点第一个节点取出放入已扩展节点表取出放入已扩展节点表CLOSED表，并记该节点为节点表，并记该节点为节点n；(4)考察节点考察节点n是否为目标节点。若是则得到了问题的解，是否为目标节点。若是则得到了问题的解，成功退出。此时的解为追踪图成功退出。此时的解为追踪图G中沿着指针中沿着指针（步骤（步骤6中中设置的指针）设置的指针）从从n到初始节点到初始节点S
25、的路径。的路径。状态空间的搜索策略v图搜索的一般过程图搜索的一般过程(5)扩展节点扩展节点n，生成一组子节点。把这些子节点中，生成一组子节点。把这些子节点中不是不是节点节点n先辈先辈 的那部分子节点记入集合的那部分子节点记入集合M，并把这些子节，并把这些子节点作为节点点作为节点n的子节点加入的子节点加入G中中(6)针对针对M中子节点的不同情况，分别作如下处理：中子节点的不同情况，分别作如下处理：p 对那些没有在对那些没有在G中出现过的中出现过的M成员设置一个指向其父节点成员设置一个指向其父节点（即节点（即节点n）的指针，并把它放入）的指针，并把它放入OPEN表。（表。（新生成的新生成的）p 对
26、那些原来已在对那些原来已在G中出现过，但还没有被扩展的中出现过，但还没有被扩展的M成员，确成员，确定是否需要修改它指向父节点的指针。（定是否需要修改它指向父节点的指针。（原生成但未扩展的原生成但未扩展的）p 对于那些先前已在对于那些先前已在G中出现过，并已经扩展了的中出现过，并已经扩展了的M成员，确成员，确定是否需要修改其后继节点指向父节点的指针。（定是否需要修改其后继节点指向父节点的指针。（原生成也扩原生成也扩展过的展过的）v图搜索的一般过程图搜索的一般过程(7)按某种策略对按某种策略对OPEN表中的节点表中的节点进行进行排序排序。(8)转第转第(2)步。步。状态空间的搜索策略状态空间的搜索
27、策略v图搜索的一般过程的几点说明：图搜索的一般过程的几点说明：上述过程是状态空间的一般图搜索算法，它具上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。策略都是上述过程的一个特例。各种搜索策略的主要区别在于对各种搜索策略的主要区别在于对OPEN表中节表中节点的排列顺序不同点的排列顺序不同。例如，广度优先搜索把先。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。后生成的子节点排在前面。状态空间的搜索策略v图搜索的一般过程的
28、几点说明：图搜索的一般过程的几点说明：在第在第(6)步针对步针对M中子节点的不同情况进行处理中子节点的不同情况进行处理时，如果发生当第时，如果发生当第种情况，那么，这个种情况，那么，这个M中的中的节点究竟应该作为哪一个节点的后继节点呢？节点究竟应该作为哪一个节点的后继节点呢？一般是由原始节点到该节点路径上所付出的代一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到的节点就作为它的父节点。所谓由原始节点到该节点路径上的代价是指这条路经上的所有有该节点路径上的代价是指这条路经上的所有有向边
29、的代价之和。向边的代价之和。状态空间的搜索策略v图搜索的一般过程的几点说明：图搜索的一般过程的几点说明：如果发生第如果发生第种情况，除了需要确定该子节点指种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该向父节点的指针。其依据也是由原始节点到该节点的路径上的代价。节点的路径上的代价。在搜索图中，除初始节点外，任意一个节点都含在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集由所有节点及
30、其指向父节点的指针所构成的集合是一棵树，称为合是一棵树，称为搜索树搜索树。状态空间的搜索策略v图搜索的一般过程的几点说明：图搜索的一般过程的几点说明：在搜索过程的第在搜索过程的第(4)步，一旦某个被考察的节点步，一旦某个被考察的节点是是目标节点目标节点，则搜索过程成功结束。此时，由，则搜索过程成功结束。此时，由初始节点到目标节点路径上的所有操作就构成初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第了该问题的解，而路径由第(6)步所形成的指向步所形成的指向父节点的指针来确定。父节点的指针来确定。如果搜索过程终止在第如果搜索过程终止在第(2)步，即没有达到目标，步，即没有达到目标，
31、且且OPEN表中已无可供扩展的节点，则失败结表中已无可供扩展的节点，则失败结束。束。广度优先搜索v状态空间的广度优先搜索状态空间的广度优先搜索广度优先搜索的基本思想：广度优先搜索的基本思想：p从初始节点从初始节点S开始逐层向下扩展，在第开始逐层向下扩展，在第n层节层节点还没有全部搜索完之前，不进入第点还没有全部搜索完之前，不进入第n+1层层节点的搜索。节点的搜索。p未扩展节点表未扩展节点表OPEN表中的节点总是按进入表中的节点总是按进入的先后排序，先进入的节点排在前面，后进的先后排序，先进入的节点排在前面，后进入的节点排在后面。入的节点排在后面。广度优先搜索v状态空间的广度优先搜索状态空间的广
32、度优先搜索广度优先搜索算法流程：广度优先搜索算法流程：(1)把初始节点把初始节点S放入放入OPEN表中；表中；(2)如果如果OPEN表为空，则问题无解，失败退出；表为空，则问题无解，失败退出；(3)把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表，并记表，并记该节点为该节点为n；(4)考察节点考察节点n是否为目标节点。若是，则得到问题的解，是否为目标节点。若是，则得到问题的解，成功退出；成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的表的尾部尾部，并为每，并为每一个子节点设置指
33、向父节点的指针，然后转第一个子节点设置指向父节点的指针，然后转第(2)步。步。广度优先搜索v广度优先搜索的例子：广度优先搜索的例子：八数码难题八数码难题在在33的方格棋盘上，分别放置了表有数字的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态的八张牌，初始状态S0，目标状态，目标状态Sg，如，如下图所示。要求应用广度优先搜索策略寻找从初始状态下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径到目标状态的解路径。1238476528314765S0Sg广度优先搜索八八数数码码难难题题的的宽宽度度优优先先搜搜索索树树广度优先搜索v在上述广度优先算法中需
34、要注意两个问题：在上述广度优先算法中需要注意两个问题：对于任意一个可扩展的节点，总是按照固定的操作对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（符的顺序对其进行扩展（空格左移、上移、右移、空格左移、上移、右移、下移下移）。）。在对任一节点进行扩展的时候，在对任一节点进行扩展的时候，如果所得的某个子如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入不再重复画出（不送入OPEN表）表）。因此，广度优先搜索的本质是，以初始节点为根节因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的
35、原则，生成一点，在状态空间图中按照广度优先的原则，生成一棵搜索树。棵搜索树。广度优先搜索v广度优先搜索的特点：广度优先搜索的特点：优点：优点：p只要问题有解，用广度优先搜索总可以得到只要问题有解，用广度优先搜索总可以得到解，解，而且得到的是路径最短的解而且得到的是路径最短的解。缺点：缺点：p广度优先搜索盲目性较大，当目标节点距初广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索始节点较远时将会产生许多无用节点，搜索效率低。效率低。状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间
36、的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法深度优先搜索v状态空间的深度优先搜索状态空间的深度优先搜索深度优先搜索的基本思想：深度优先搜索的基本思想：p从初始节点从初始节点S开始，在其子节点中选择一个最新开始，在其子节点中选择一个最新生成的节点进行考察。生成的节点进行考察。p如果该子节点不是目标节点且可以扩展，则扩如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择展该子节点，然后再在此子节点的子节
37、点中选择一个最新生成的节点进行考察。一个最新生成的节点进行考察。p依此向下搜索，直到某个子节点既不是目标节依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行点，又不能继续扩展时，才选择其兄弟节点进行考察。考察。深度优先搜索v状态空间的深度优先搜索状态空间的深度优先搜索深度优先搜索算法流程：深度优先搜索算法流程：(1)把初始节点把初始节点S放入放入OPEN表中；表中；(2)如果如果OPEN表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表，并记表，并记该节点为该节点为n；(4)考
38、察节点考察节点n是否为目标节点。若是，则得到问题的解，是否为目标节点。若是，则得到问题的解，成功退出；成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的表的首部首部，并为，并为每一个子节点设置每一个子节点设置 指向父节点的指针，然后转第指向父节点的指针，然后转第(2)步。步。深度优先搜索v深度优先搜索：深度优先搜索：八数码难题八数码难题八数码难题的深度优八数码难题的深度优先搜索如右图先搜索如右图首先扩展最新产生的首先扩展最新产生的(最深的最深的)节点节点如果目标节点不在当如果目标节点不在当前搜索的分支
39、上？前搜索的分支上？深度优先搜索v深度优先搜索与广度优先搜索的唯一区别是：深度优先搜索与广度优先搜索的唯一区别是：广度广度优先搜索是将节点优先搜索是将节点n的子节点放入到的子节点放入到OPEN表的表的尾部尾部，而深，而深度优先搜索是把节点度优先搜索是把节点n的子节点放入到的子节点放入到OPEN表的表的首部首部。v在深度优先搜索中，搜索一旦进入某个分支，就将沿着该在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该较快地得到解。但是，如果目标节点不在
40、此分支上，而该分支又是一个无穷分支，则就不可能得到解。分支又是一个无穷分支，则就不可能得到解。所以深度优所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。先搜索是不完备的，即使问题有解，它也不一定能求得解。v深度优先搜索本质：深度优先搜索本质：以初始节点为根节点，在状态空间以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。图中按照深度优先的原则，生成一棵搜索树。有界深度优先搜索v有界深度优先搜索：有界深度优先搜索：动动机机：为为了了防防止止搜搜索索过过程程沿沿着着无无益益的的路路径径扩扩展展下下去去，往往往往给给出出一一个个节节点点扩扩展展的的最最大大深深度度，
41、即即深度界限。深度界限。思想：思想：对对状态空间的深度优先搜索引入搜索深状态空间的深度优先搜索引入搜索深度度界限，设为界限，设为dm，当搜索深度达到了深度界限，当搜索深度达到了深度界限而仍未出现目标节点时，就换一个分支进行搜而仍未出现目标节点时，就换一个分支进行搜索。索。有界深度优先搜索八数码难题：八数码难题：dm=4有界深度优先搜索v有界深度优先搜索：有界深度优先搜索：问问题题：如如果果问问题题有有解解，且且其其路路径径长长度度 dm，则则上上述述搜搜索索过过程程一一定定能能求求得得解解。但但是是，若若解解的的路路径径长长度度 dm,则则上上述述搜搜索索过过程程就就得得不不到到解解。这这说说
42、明明在在有有界界深深度度优优先先搜搜索索中中，深深度度界界限限的的选选择择是是很重要的。很重要的。要要恰恰当当地地给给出出dm的的值值是是比比较较困困难难的的。即即使使能能求求出解，它也不一定是最优解。出解，它也不一定是最优解。状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法代价树搜索v代价树：
43、代价树：边上标有代价边上标有代价(或费用或费用)的树称为代价树的树称为代价树v在代价树中，若用在代价树中，若用g(x)表示从初始节点表示从初始节点S到节点到节点x的代价，的代价，用用c(x1,x2)表示从父节点表示从父节点x1到子节点到子节点x2的代价，则有：的代价，则有：g(x2)=g(x1)+c(x1,x2)v代价树搜索：代价树搜索：考虑边的代价的搜索方法，代价树搜索的考虑边的代价的搜索方法，代价树搜索的目的是为了找到一条代价最小的解路径。代价树搜索方法目的是为了找到一条代价最小的解路径。代价树搜索方法包括：包括：代价树的广度优先搜索代价树的广度优先搜索代价树的深度优先搜索代价树的深度优先
44、搜索代价树的广度优先搜索v代价树的广度优先搜索代价树的广度优先搜索基本思想：基本思想：每次从每次从OPEN表中选择节点往表中选择节点往CLOSED表表传送时，传送时，总是选择其中代价最小的节点总是选择其中代价最小的节点。也就是说，。也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面，序的。代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。而不管节点在代价树中处于什么位置上。如果问题有解，代价树的广度优先搜索一定可以求得解，如果问题有解，代价树的广度优先搜索一定可以求
45、得解，并且求出的是最优解。并且求出的是最优解。该算法应用的条件：该算法应用的条件：该算法是针对代价树的算法。该算法是针对代价树的算法。为了采用该算法对图进行搜索，为了采用该算法对图进行搜索，必须先将图转换为代价必须先将图转换为代价树树。代价树的广度优先搜索v代价树的广度优先搜索算法流程：代价树的广度优先搜索算法流程：(1)把初始节点把初始节点S放入放入OPEN表中，置表中，置S的代价的代价g(S)=0；(2)如果如果OPEN表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表，并记该节表，并记该节点为点为n；(
46、4)考察节点考察节点n是否为目标。若是，则找到了问题的解，成功是否为目标。若是，则找到了问题的解，成功退出；退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；否则转第步；否则转第(6)步；步；(6)扩展节点扩展节点n，为每一个子节点都配置指向父节点的指针，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放入计算各子节点的代价，并将各子节点放入OPEN表中。表中。并根并根据各子结点的代价对据各子结点的代价对OPEN表中的表中的全部结点全部结点按由小到大的顺按由小到大的顺序排序序排序。然后转第。然后转第(2)步。步。代价树的广度优先搜索v例子：例子：城市交通
47、问题。设有城市交通问题。设有5个城市，它们之间的交通线个城市，它们之间的交通线路如下方左图所示，图中的数字表示两个城市之间的交通路如下方左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从费用，即代价。用代价树的广度优先搜索，求从A市出发市出发到到E市，费用最小的交通路线。市，费用最小的交通路线。ABCDE43 4 523城市交通图城市交通图代价树的广度优先搜索v解：解：首先将交通图转化为代价首先将交通图转化为代价树。具体转化方法如下：树。具体转化方法如下：从起始节点从起始节点A开始，把与它直接开始，把与它直接相邻的节点作为它的子节点相邻的节点作为它的子节点对其
48、他节点也做相同的处理对其他节点也做相同的处理若一个节点已经为某节点的直系若一个节点已经为某节点的直系先辈节点时，就不能作为这个节先辈节点时，就不能作为这个节点的子节点。点的子节点。图中除了起始节点图中除了起始节点A之外，其它之外，其它节点都可能要在代价树中出现多节点都可能要在代价树中出现多次，为了区分它们的多次出现，次，为了区分它们的多次出现，分别用下标分别用下标1,2，标出标出城市交通图的代价树城市交通图的代价树2 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35代价树的广度优先搜索v解：解：对此代价树进行广度优先搜索，可得到最优对此代价树进行广度优先搜索，可得到最优解
49、，如图红线部分为最优解，其代价为解，如图红线部分为最优解，其代价为8ABCDE43 4 5232 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35代价树的深度优先搜索v代价树的深度优先搜索代价树的深度优先搜索基本思想：基本思想：与代价树的广度优先搜索不同，代与代价树的广度优先搜索不同，代价树的深度优先搜索是价树的深度优先搜索是从刚扩展出的子节点中从刚扩展出的子节点中选择选择一个代价最小的节点送入一个代价最小的节点送入CLOSED表进行表进行考察，而不是在整个考察，而不是在整个OPEN表中选择代价最小表中选择代价最小的。的。代价树的深度优先搜索v代价树的深度优先搜索算法流程
50、：代价树的深度优先搜索算法流程：(1)把初始节点把初始节点S放入放入OPEN表中，置表中，置S的代价的代价g(S)=0；(2)如果如果OPEN表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表，并表，并记该节点为记该节点为n；(4)考察节点考察节点n是否为目标节点。若是，则找到了问题的是否为目标节点。若是，则找到了问题的解，成功退出；解，成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，生成其子节点，生成其子节点，将这些子节点按边代价将这些子节点按边代价由小