人工智能及其应用 教学课件 ppt 作者 李长河 第6章搜索
138页1、2019/5/20,第6章 搜 索 李长河主编,1,第6章 搜 索,2019/5/20,第6章 搜 索 李长河主编,2,第6章 搜 索,6.1 什么是搜索? 6.2 状态空间表示法 6.3 状态空间的基本搜索策略 6.4 启发式搜索策略 6.5 启发式搜索法 6.6 与/或树的启发式搜索 6.7 博弈对策(Game of Chess Strategy),学海无涯,2019/5/20,第6章 搜 索 李长河主编,3,6.1 概述,搜索(Search),即寻找,设法在庞大状态空间图中找到目标。也可以把搜索看作是一种推理,它是人工智能问题求解的基本方法之一。 主要分为两类性质的搜索:即基本搜索和智能搜索。 基本搜索是一种没有任何经验和知识起作用的、由某种规则所确定的非智能性的搜索; 启发式搜索(Heuristic Search):其特点在于是一种有准备的、追求效率而有的放矢的智能搜索,它要求依据某种知识及信息的指导,通过逐一状态比较而找到符合规定条件的目标状态解。,6.1.1 什么是搜索?,2019/5/20,第6章 搜 索 李长河主编,4,6.1.1 什么是搜索?,可把问题世界的全部信息空
2、间划分为三类: (1)全信息环境Ee; (2)部分已知信息环境Ep; (3)未知信息环境En,2019/5/20,第6章 搜 索 李长河主编,5,6.1.1 什么是搜索?,(1)全信息环境Ee。已知与问题的解有关的全部信息,其搜索的目标和任务是:运用知识和经验,设法找到最佳路径,以便取得理想搜索效果。例如,在国际象棋博奕中,选择最优算法来克敌制胜。,6.1.1 什么是搜索?,(2)部分已知信息环境Ep。当只有部分信息已知,这时,其目标和任务是:充分利用已知信息,把未知的信息不利影响设法降到最低程度,尽可能按照最佳搜索路径取得理想搜索效果。或者设法弥补信息损失,发挥已知信息作用,扬长避短,制定策略来克敌制胜。例如,在海陆空战棋或军棋游戏中,运用知识和经验猜测对方的军事布局,一方面用手榴弹对付比我方师长还要厉害的指挥官,另一方面要设法用最小代价摧毁对方强大火力,以便开辟夺取对方军旗的坦途。,2019/5/20,第6章 搜 索 李长河主编,7,6.1.1 什么是搜索?,(3)未知信息环境En。 对于未知信息环境的问题求解,首先要设法变En为部分已知信息环境Ep来解决。例如,为了探测海洋、极地
3、、外星球的奥秘,就需要实地探险或发射相应的探测器,以便取得必要的信息与知识;当进入陌生的地带作战时,需要派出侦察小分队了解地形地物和侦察敌人火力部署,或用侦察卫星探测敌情等。,2019/5/20,第6章 搜 索 李长河主编,8,6.1.2 问题的状态空间图搜索,问题的状态空间可用有向图来表达,如图6-2所示,又常称其为状态树(State Tree)。图中,节点Sk表示状态,状态之间的连接采用有向弧(Arc),弧上标以操作数OK来表示状态之间的转换关系。 用状态空间法搜索求解问题: 首先要把待求解的问题表示为状态空间图;把问题的解表示为目标节点Sg。 求解就是要找到从根节点S0到达目标节点Sg的搜索路径。,2019/5/20,第6章 搜 索 李长河主编,9,6.1.2 问题的状态空间图搜索,状态空间图在计算机中有两种存储方式:一种是图的显式存储,另一种是图的隐式存储。 图的显式存储: (1)概念:所谓图的显式存储,即把问题的全部状态空间图直接都存于计算机中的方式。诸如一般计算机文件、程序文件和库文件的存储等,均为图的显式存储方式。 (2)适用条件:通常图的显式存储方式需要占据计算机的大量
4、存储空间和处理时间,故这种存储方式仅适用于状态空间十分有限以及较简单的问题求解。 (3)特点:其优点是直观、明了,但缺点是占据存储空间大。,2019/5/20,第6章 搜 索 李长河主编,10,6.1.2 问题的状态空间图搜索,图的隐式存储: (1)概念:仅在计算机中存储关于要求解问题的相关各种知识,只在必要时再由相关的信息和知识逐步生成状态空间图的方式称为图的隐式存储。 (2)适用条件:适用于一般问题求解,尤其适宜于状态空间庞大的情况。 (3)特点:占据空间小,但不够直观,与图的显式存储刚好特点互补。 例如,针对问题的状态空间十分庞大的情况,人们可采用图的隐式存储:即只需要存入问题的参数、参数数值表和计算公式等,仅在问题求解中,按照推理或搜索过程的需要,进行参数和参数值的代换与公式计算,再求得状态空间各点的数值。通过数值的比较与搜索,最后再完成问题的求解,2019/5/20,第6章 搜 索 李长河主编,11,6.1.2 问题的状态空间图搜索,隐式图的搜索过程: (1)概念:根据机器中所存储的待求解问题的相关知识,逐步产生问题的状态空间图并检查解是否在其中的过程,叫做隐式图的搜索过程。
《人工智能及其应用 教学课件 ppt 作者 李长河 第6章搜索》由会员E****分享,可在线阅读,更多相关《人工智能及其应用 教学课件 ppt 作者 李长河 第6章搜索》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页