人工智能问题求解基本原理及搜索技术.PPT

上传人:国*** 文档编号:777085 上传时间:2018-10-31 格式:PPT 页数:49 大小:1.02MB
下载 相关 举报
人工智能问题求解基本原理及搜索技术.PPT_第1页
第1页 / 共49页
人工智能问题求解基本原理及搜索技术.PPT_第2页
第2页 / 共49页
人工智能问题求解基本原理及搜索技术.PPT_第3页
第3页 / 共49页
人工智能问题求解基本原理及搜索技术.PPT_第4页
第4页 / 共49页
人工智能问题求解基本原理及搜索技术.PPT_第5页
第5页 / 共49页
点击查看更多>>
资源描述

1、北京航空航天大学软件开发环境国家重点实验室 Slide 1人 工 智 能( 问题求解 基本原理及 搜索技术 )北京航空航天大学软件开发环境国家重点实验室 Slide 2问题求解基本原理n 问题求解: 在给定条件下,寻求一个能解决 某类 问题 且能在有限步骤内完成的算法。n 问题求解特征:w 传统软件 : 求解的问题是能够用 数学精确描述 的 良结构的问题 (如,解方程) ; 计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。w AI软件 : 求解的是 不可直接用数学模型描述 的所谓 不良结构问题 (如,几何证明、求不定积分、逻辑演算等) ,通常需要采用 弱方法 进行搜索求解; AI程序

2、 中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息,应表现人类进行推理所需要的各种 知识 。北京航空航天大学软件开发环境国家重点实验室 Slide 3问题求解基本原理一、问 题 求 解 的 基 本 方 法二、搜 索 技 术北京航空航天大学软件开发环境国家重点实验室 Slide 4问题求解基本原理n问题求解方法:w基于 状态空间 的问题求解方法w基于 问题空间 的问题求解方法 w基于 博弈 搜索 的问题求解方法北京航空航天大学软件开发环境国家重点实验室 Slide 5问题实例桌上固定了 3 根柱子,按 1, 2, 3 次序排例。有 n 个大小全不一样大的盘子 d1, , dn , 按从小

3、到大,小的在上的次序依次插在第一根柱子上,要把这 n 个盘子全部搬到第三根柱子上,每次只许搬一个,任何时候都不允许把大盘子放在小盘子上面,问该 如何搬法。 设 n = 3, 该 如何搬法 ?1 2 3 1 2 3梵塔问题北京航空航天大学软件开发环境国家重点实验室 Slide 6基于 状态空间 的问题求解方法( 1, 1, 1) ( 1, 1, 2)( 1, 1, 1) ( 1, 1, 3)( 1, 1, 2) ( 1, 3, 2)。状态 合法 变换规则(满足约束条件):状态定义 -( i大 , j中 , k小 ) : 设向量下标分别表示大盘、中盘、小盘;向量值分别表示盘子所在柱子的编号。状态描

4、述 - 大盘在第 i 根柱子上;中号盘在第 j 根柱子上,小号盘在第 k 根柱子上。 北京航空航天大学软件开发环境国家重点实验室 Slide 7基于 问题空间 的问题求解方法n 问题: 如何将 i 柱子上的 m 个盘子搬到 k 柱子上 ?w 将 i 柱子上的 m 1 个盘子搬到 j 柱子上;w 将 i 柱子上的 第 m 个盘子搬到 k 柱子上;w 将 j 柱子上的 m 1 个盘子搬到 k 柱子上。n 问题描述:问题( a, b, c): 将 b 柱子上的 a 个盘子搬到 c 柱子上。问题分解合法规则:( 3, 1, 3) - ( 2, 1, 2) (1, 1, 3) ( 2, 2, 3)。北京

5、航空航天大学软件开发环境国家重点实验室 Slide 8基于 问题空间 的问题求解方法北京航空航天大学软件开发环境国家重点实验室 Slide 9状态空间法 有关概念n 状态空间法 :从问题的 初始状态 出发,通过一系列的 状态变换 找到 目标状态 的问题求解方法。n 状态 : 描述问题中事物形状或状况的符号或数据结构。n 状态空间 : 所有状态的全体构成的集合;用 四元组 ( S, S0, O, G) 表示 :S: 非空状态子集, S0 = 初始状态(非空)。G: 非空目标状态子集。O: 操作算子集 合 ,一个状态 合法 转换为 另一个状态的 描述 规则n 问题求解过程 : 隐含 求一个 普通有向图 , 节点 - 状态, 边 算子 n 搜索空间 : 问题求解过程中 到达 过的所有状态(节点)的集合 。北京航空航天大学软件开发环境国家重点实验室 Slide 10状态空间法 有关概念状态空间、搜索空间及解径的关系:n 问题的解(解径) : 初始状态 到 目标状态 通路上的每一条规则 (或 状态)构成 序列,称为 解径 。 解不唯一。S0 R1 S2 R2 Sk . Rk Gn 问题有解 : 从代表 初始状态 s 节点出发, 存在一条通向 目标节点 的路径。

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 重点行业资料库 > 1

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。