人工智能及其应用 教学课件 作者 李长河 第6章搜索.ppt

《人工智能及其应用 教学课件 作者 李长河 第6章搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章搜索10/5/20211第6章搜索李长河主编第6章搜索6.1什么是搜索?6.2状态空间表示法6.3状态空间的基本搜索策略6.4启发式搜索策略6.5启发式搜索法6.6与/或树的启发式搜索6.7博弈对策（GameofChessStrategy）学海无涯10/5/20212第6章搜索李长河主编6.1概述搜索（Search），即寻找，设法在庞大状态空间图中找到目标。也可以把搜索看作是一种推理，它是人工智能问题求解的基本方法之一。主要分为两类性质的搜索：即基本搜索和智能搜索。基本搜索是一种没有任何经验和知识起作用的、由某种规则所确

2、定的非智能性的搜索；启发式搜索（HeuristicSearch）：其特点在于是一种有准备的、追求效率而有的放矢的智能搜索，它要求依据某种知识及信息的指导，通过逐一状态比较而找到符合规定条件的目标状态解。6.1.1什么是搜索?10/5/20213第6章搜索李长河主编6.1.1什么是搜索？可把问题世界的全部信息空间划分为三类：（1）全信息环境Ee；（2）部分已知信息环境Ep；（3）未知信息环境EnEpEnEe图6-1问题世界的信息环境10/5/20214第6章搜索李长河主编6.1.1什么是搜索？（1）全信息环境Ee。已知与问题的解

3、有关的全部信息，其搜索的目标和任务是：运用知识和经验，设法找到最佳路径，以便取得理想搜索效果。例如，在国际象棋博奕中，选择最优算法来克敌制胜。EpEnEe图6-1问题世界的信息环境10/5/20215第6章搜索李长河主编6.1.1什么是搜索？（2）部分已知信息环境Ep。当只有部分信息已知，这时，其目标和任务是：充分利用已知信息，把未知的信息不利影响设法降到最低程度，尽可能按照最佳搜索路径取得理想搜索效果。或者设法弥补信息损失，发挥已知信息作用，扬长避短，制定策略来克敌制胜。例如，在海陆空战棋或军棋游戏中，运用知识和经验猜测对方

4、的军事布局，一方面用手榴弹对付比我方师长还要厉害的指挥官，另一方面要设法用最小代价摧毁对方强大火力，以便开辟夺取对方军旗的坦途。EpEnEe图6-1问题世界的信息环境10/5/20216第6章搜索李长河主编6.1.1什么是搜索？（3）未知信息环境En。对于未知信息环境的问题求解，首先要设法变En为部分已知信息环境Ep来解决。例如，为了探测海洋、极地、外星球的奥秘，就需要实地探险或发射相应的探测器，以便取得必要的信息与知识；当进入陌生的地带作战时，需要派出侦察小分队了解地形地物和侦察敌人火力部署，或用侦察卫星探测敌情等。EpEn

5、Ee图6-1问题世界的信息环境10/5/20217第6章搜索李长河主编6.1.2问题的状态空间图搜索问题的状态空间可用有向图来表达，如图6-2所示，又常称其为状态树(StateTree)。图中，节点Sk表示状态，状态之间的连接采用有向弧(Arc)，弧上标以操作数OK来表示状态之间的转换关系。用状态空间法搜索求解问题:首先要把待求解的问题表示为状态空间图;把问题的解表示为目标节点Sg。求解就是要找到从根节点S0到达目标节点Sg的搜索路径。图6-2问题求解的状态树表示sg10/5/20218第6章搜索李长河主编6.1.2问题的状态

6、空间图搜索状态空间图在计算机中有两种存储方式：一种是图的显式存储，另一种是图的隐式存储。图的显式存储:（1）概念：所谓图的显式存储，即把问题的全部状态空间图直接都存于计算机中的方式。诸如一般计算机文件、程序文件和库文件的存储等，均为图的显式存储方式。（2）适用条件：通常图的显式存储方式需要占据计算机的大量存储空间和处理时间，故这种存储方式仅适用于状态空间十分有限以及较简单的问题求解。（3）特点：其优点是直观、明了，但缺点是占据存储空间大。图6-2问题求解的状态树表示sg10/5/20219第6章搜索李长河主编6.1.2问题的状

7、态空间图搜索图的隐式存储:（1）概念：仅在计算机中存储关于要求解问题的相关各种知识,只在必要时再由相关的信息和知识逐步生成状态空间图的方式称为图的隐式存储。（2）适用条件：适用于一般问题求解，尤其适宜于状态空间庞大的情况。（3）特点：占据空间小，但不够直观，与图的显式存储刚好特点互补。例如，针对问题的状态空间十分庞大的情况，人们可采用图的隐式存储：即只需要存入问题的参数、参数数值表和计算公式等，仅在问题求解中，按照推理或搜索过程的需要，进行参数和参数值的代换与公式计算，再求得状态空间各点的数值。通过数值的比较与搜索，最后再完成

8、问题的求解10/5/202110第6章搜索李长河主编6.1.2问题的状态空间图搜索隐式图的搜索过程:（1）概念：根据机器中所存储的待求解问题的相关知识，逐步产生问题的状态空间图并检查解是否在其中的过程，叫做隐式图的搜索过程。（2）隐式图的搜索过程与步骤：搜索之先，必须配置一个