[精选]第2章基于状态空间图表示的搜索技术.pptx

[精选]第2章基于状态空间图表示的搜索技术.pptx

ID:62445425

大小:3.62 MB

页数:163页

时间:2021-05-06

[精选]第2章基于状态空间图表示的搜索技术.pptx_第1页
[精选]第2章基于状态空间图表示的搜索技术.pptx_第2页
[精选]第2章基于状态空间图表示的搜索技术.pptx_第3页
[精选]第2章基于状态空间图表示的搜索技术.pptx_第4页
[精选]第2章基于状态空间图表示的搜索技术.pptx_第5页
资源描述:

《[精选]第2章基于状态空间图表示的搜索技术.pptx》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、第2章基于图的知识表示与图搜索技术2021/8/9人工智能2第2章基于图的知识表示与图搜索技术2.1概述2.2状态空间图表示2.3状态空间图的盲目搜索2.4状态空间图的启发式搜索2.5与或图表示及搜索技术2.6博弈树及搜索技术2021/8/9人工智能32.1概述2.1.1知识与问题求解框架2.1.2知识表示2.1.3图搜索技术2021/8/9人工智能42.1.1知识与问题求解框架(1)1.知识的定义心理学:个体通过与环境相互作用后获得的信息及其组织。费根鲍姆:知识是经过消减、塑造、解释和转换的信息。博

2、恩斯坦(Bernstein):知识是由特定领域的描述、关系和过程组成的。概括地说,知识是高度组织起来的信息集团,是人们在长期的生活和社会实践中、科学研究和科学实验中积累起来的经验或对客观世界规律的认识等。2.1.1知识与问题求解框架(2)2.知识的分类(1)从应用领域来划分常识性知识领域(专业)性知识(2)从在问题求解中的作用来划分叙述性知识过程性知识控制性知识(3)从确定性来划分确定性知识非确定性知识(4)从知识的表现形式来划分,可分为文字、符号、声音、图形、图像等。2021/8/9人工智能52.1

3、.1知识与问题求解框架(3)3.问题求解框架问题:是指事件或事物的已知或当前状态与目标状态之间有差异。问题求解:是指在一定的控制策略下,通过一系列的操作或运算来改变问题的状态,使之与目标状态接近或一致。例如,李明在北京,他要去西安(办事)。又如,博弈问题。2021/8/9人工智能6问题的求解框架(1)叙述性知识:描述问题的状态有关的各种知识。(2)过程性知识:描述状态之间的变换关系的各种知识。(3)控制性知识:描述如何在当前状态下选择合适操作的知识。2021/8/9人工智能82.1.2知识表示(1)知

4、识表示:就是研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识,包括构成问题求解框架的全部知识。常用的知识表示形式状态空间图与或图谓词逻辑产生式框架语义网络……2.1.2知识表示(2)2021/8/9人工智能9例2.1麦卡赛问题。在一个2n2n的方格棋盘中,去掉对角的两个方格,如图(a),问能否将它全部划成若干12的小长方块?目标状态初始状态可达状态同构问题同态问题2021/8/9人工智能102.1.3图搜索技术(1)1.搜索搜索,简单地说就是“寻找”,目的是找到问题的解。在问题求

5、解过程中,待求解的问题被抽象成一定空间上的图,搜索过程就是从图中初始节点出发,沿着与之相连的边试探着前进,寻找目标节点或可解节点的过程。2.搜索树搜索过程中经过(考察过)的节点和边,按原图的连接关系,便会构成一个树型的有向图,称为搜索树。搜索树是一个搜索过程的搜索轨迹,或称之为搜索空间。2.1.3图搜索技术(2)2021/8/9人工智能11图2-2搜索空间示意图问题的状态空间、搜索空间及解的示意图:2.1.3图搜索技术(3)3.搜索策略搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪

6、些节点。盲目搜索:无向导的搜索,也称穷举搜索。启发式搜索:利用“启发性信息”作为导航的搜索过程。对于较大或无限状态空间问题,盲目搜索效率太低,所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中,如博弈、机器学习、数据挖掘、智能检索等。2021/8/9人工智能122021/8/9人工智能132.2状态空间图表示2.2.1状态空间图2.2.2隐式状态空间图2021/8/9人工智能142.2.1状态空间图(1)1.状态状态对应叙述性知识,描述一个问题在开始、结束或中间的某一时刻所处的状况或状

7、态。通常引进一组变量,表示与问题状态相关的各种要素,并用这组变量所构成的多元组来表示状态。状态在状态图中表示为节点。2021/8/9人工智能152.2.1状态空间图(2)2.操作操作对应过程性知识,即状态转换规则,描述状态之间的关系。描述一个操作要包含两个部分条件:指明被作用的状态要满足的约束条件动作:指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤、过程、规则或算子。操作在状态图中表示为边。在程序中,状态转换规则可用数据对、条件语句、规则、函数、过程等表示。如:如果室内温度低

8、于26度,则关闭空调。2021/8/9人工智能162.2.1状态空间图(3)3.状态空间图问题的状态空间图是一个描述该问题全部可能的状态及相互关系的图,如考虑操作的代价,状态空间图就是一个赋值有向图。状态空间常记为三元组:S:初始状态的集合F:操作的集合G:目标状态的集合。由问题的状态空间表示就可以构造出状态空间图。2.2.1状态空间图(4)4.求解在状态空间表示法中,问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题,也就是寻找操

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。