当前位置：文档之家 › 第三章搜索策略(ppt)PracticalReaso(1)

第三章搜索策略(ppt)PracticalReaso(1)

  • 格式：ppt
  • 大小：1.75 MB
  • 文档页数：111

下载文档原格式

  / 111

合集下载

第3章 搜索策略

第3章 搜索策略
小 ←─费用─→ 大
总费用 操作费用 控制费用
小 ←─── 启发式信息量 ───→ 大
搜索的费用
一般地，盲目搜索算法需要搜索的空间比较大， 因而，其操作的费用较高；而启发式搜索算法的控制 策略比较复杂，因而，其控制的费用较高。 一方面，启发式信息利用程度越高，问题的搜索 空间越小，操作的费用越低。另一方面，启发式信息 利用程度越高，控制策略越复杂，控制的费用越高。 操作费用与控制费用的这种辨证关系对于我们设 计或选择图搜索算法具有指导意义。
搜索的策略和算法
在状态图（树）中，寻找由起始节点通向目标节点的 路径可以有各种不同的搜索策略。不同的策略以不同的方 式控制着搜索的过程。因此，搜索策略又称控制策略。 与问题相关的信息往往能帮助我们进行更为有效的搜 索，当然，这取决于相关信息的质和量。依据控制策略利 用与问题相关信息的情形来对图搜索算法进行分类，可将 其分为： (1) 盲目搜索算法 (Blink Search) (2) 启发式搜索算法 (Heauristic Search)
搜索的相关定义
开节点(open node)：未进行扩展操作的节点； 闭节点(closed node) ：已进行扩展操作的节点；
扩展节点(expended node)：已进行扩展操作，并生长 出子结点的节点；
死节点(dead node)：闭节点，但不是扩展节点； 叶节点(leaf node)：无子节点或未生成子节点的节点。
深，搜索图上的节点数将成几何级数地增长，这意
味着，对于大的问题，宽度优先搜索算法需要巨大 的记忆体或存储空间。
A
B
C
D
宽度优先搜索
K
E
F
G
H
I
J
L
M

人工智能之搜索策略介绍课件

人工智能之搜索策略介绍课件
基本概念：模拟生物进化过程， 通过选择、交叉、变异等操作，
实现搜索策略的优化
2
步骤：初始化种群、计算适应 度、选择、交叉、变异、迭代
3
优点：全局搜索能力强，能够 找到最优解
4
缺点：计算复杂度高，收敛速 度慢，容易陷入局部最优解
搜索策略的优化
优化目标
01 提高搜索效率：减少搜索 时间，提高搜索结果的准 确性
01
02
03
信息检索：搜索引擎、 路径规划：地图导航、 问题求解：数学问题、
学术论文检索等
物流配送等
逻辑问题等
04
05
06
游戏AI：棋类游戏、 电子游戏等
机器人控制：自主导 航、路径规划等
优化问题：生产调度、 资源分配等
搜索策略的实现
启发式搜索
概念：根据问题特点，选择 合适的搜索策略，提高搜索
效率
01
03
02
剪枝策略：提前 终止无效或低效 的搜索路径，提 高搜索效率
04
自适应搜索：根 据搜索过程中的 反馈信息，动态 调整搜索策略， 提高搜索效果
优化效果评估
准确率：衡量搜索 结果的准确性
召回率：衡量搜索 结果中相关结果的
比例
速度：衡量搜索算 法的执行效率
稳定性：衡量搜索 算法在不同数据集
上的表现一致性
演讲人
人工智能之搜索策略介 绍课件
目录
01. 搜索策略概述 02. 搜索策略的实现 03. 搜索策略的优化 04. 搜索策略的应用案例
搜索策略概述
搜索策略的定义
搜索策略是指在解
1 决一个问题时，如 何找到最优解或近 似最优解的方法。
搜索策略可以分
2 为两类：无信息 搜索和有信息搜 索。

第三章-搜索策略11.

第三章-搜索策略11.

5.3.1 回溯策略
end; 将CS加入PS；
end else
begin 将CS子状态（不包括PS、NPS和NSS中已有的） 加入NPS； CS：= NPS中第一个元素；
将CS加入到PS； end end； return FAIL; end.
5.3.1 回溯策略
回溯搜索示意图的回溯轨迹： 初值：PS=[A]； NPS=[A]； NSS=[ ]； CS=A。
为了保证找到解，应选择合适的深度限制值，或 采取不断加大深度限制值的办法，反复搜索，直 到找到解。
5.3.3 深度优先搜索策略
深度优先搜索过程：
Procedure depth_first_search
begin
open:=[start];closed:=[ ];d:=深度限制值
while open[ ] do
A BC
(a) 初始状态
积木问题
A B C
(b) 目的状态
5.3.2 宽度优先搜索策略
操作算子为MOVE（X，Y）：把积木X搬到Y（积 木或桌面）上面。
MOVE（A，Table）：“搬动积木A到桌 面上”。
操作算子可运用的先决条件：
（1）被搬动积木的顶部必须为空。 （2）如果 Y 是积木，则积木 Y 的顶部也必须为空。 （3）同一状态下，运用操作算子的次数不得多于一次。
第3章 搜索策略
第3章 搜索求解策略
3.1 搜索的概念 3.2 状态空间的搜索策略 3.3 盲目的图搜索策略 3.4 启发式图搜索策略 3.5 与/或图搜索策略
第3章 搜索求解策略
3.1 搜索的概念 3.2 状态空间知识表示方法 3.3 盲目的图搜索策略 3.4 启发式图搜索策略 3.5 与/或图搜索策略

人工智能第三版课件第3章搜索的基本策略

人工智能第三版课件第3章搜索的基本策略

人工智能第三版课件第3章搜索的基本策略搜索引擎是当今互联网时代不可或缺的工具，而人工智能技术在搜索引擎中起着举足轻重的作用。

本文将介绍《人工智能第三版课件》中第3章的内容，讨论搜索的基本策略。

基于这些策略，搜索引擎能够更加高效、准确地满足用户的信息需求。

1. 初始搜索空间在进行搜索之前，需要建立一个初始的搜索空间，即包含可能相关信息的一组文档或网页。

这个搜索空间的建立可以通过爬虫程序和抓取技术来收集网络上的信息，并将其存储在搜索引擎的数据库中。

2. 关键词匹配搜索引擎通过用户输入的关键词与搜索空间中的文档进行匹配，以找到与用户需求相关的内容。

关键词匹配可以使用词频、倒排索引等算法来实现。

其中，词频是指对于一个给定的关键词，在搜索空间中出现的频率；倒排索引则是一种将关键词与对应的文档进行关联的索引结构。

3. 分析用户意图搜索引擎还需要通过分析用户的搜索历史、点击行为等数据来了解用户的真实意图。

这可以通过机器学习算法来实现，例如基于用户行为的推荐系统。

通过了解用户的意图，搜索引擎可以更加准确地推荐相关内容。

4. 搜索结果排序搜索引擎会对匹配到的文档进行排序，以便将最相关的结果显示在前面。

排序算法通常通过计算文档与用户查询的相似度来实现。

相似度计算可以使用向量空间模型、BM25等算法。

5. 反馈与迭代搜索引擎不断根据用户的反馈进行迭代，以提供更好的搜索结果。

用户的反馈可以包括点击率、停留时间等指标，这些指标可以通过机器学习算法来进行分析和预测。

搜索引擎可以根据用户的反馈来调整排序算法，从而不断改进搜索结果的准确性和相关性。

综上所述，搜索引擎的基本策略包括建立初始搜索空间、关键词匹配、分析用户意图、搜索结果排序以及反馈与迭代。

这些策略通过人工智能技术的应用，使得搜索引擎能够更加智能化地满足用户的信息需求。

未来随着人工智能技术的不断发展，搜索引擎将会变得更加准确、个性化，并为用户提供更多智能化的服务。

34问题归约和ANDOR图启发式搜索PPT课件

34问题归约和ANDOR图启发式搜索PPT课件

2020/11/23
人工智能 丁世飞
5
3.4.1 问题归约的描述
问题归约表示方法就是由初始问题出发， 运用操作算子产生一些子问题，对子问 题再运用操作算子产生子问题的子问题， 这样一直进行到产生的问题均为本原问 题，则问题得解。
2020/11/23
人工智能 丁世飞
6
3.4.1 问题归约的描述
看如下符号积分问题： 初始问题——∫f ( x ) dx 变换规则——积分规则 本原问题——可直接求原函数的积分，
在状态空间表示法中，由表示一个问题的全部状态以及 一切可用的算符构成的集合称为该问题的状态空间，它一般
表示为一个三元组：（S,F,G)
其中：S表示问题的所有初始状态的集合，F是算符的集合， G是目标状态的集合。
其状态搜索过程通常用搜索图或搜索树来表示。 本节我们将学习问题归约法。
2020/11/23
上一节介绍的启发式搜索算法，如最好优先算法（ 或 OR图算法）、启发式图搜索算法（或A算法）、A*算法等等。 都属于状态空间搜索问题。
2020/11/23
人工智能 丁世飞
2
引言
在状态空间搜索中，搜索过程只记录状态空间中被搜索过 的状态，它们构成一个搜索图G,G由Open节点与Closed节点组成。
如∫sin ( x ) dx，∫cos ( x ) dx等。
注意：所有问题归约的最终目的是产生 本原问题。
2020/11/23
人工智能 丁世飞
7
3.4.2 AND-OR图表示
用AND-OR图把问题归约为子问题替换集合。 例如，假设问题A既可通过问题C1与C2，也可通过
问题C3、C4和C5，或者由单独求解问题C6来解决，如 下图所示。图3.6中各节点表示要求解的问题或子问题。

第三章状态空间搜索策略ppt课件

第三章状态空间搜索策略ppt课件
(5)假设节点n的深度dn等于最大深度dm，那么转第(2) 步。
(6)假设节点n不可扩展，即没有后继节点，那么转第(2) 步；否那么继续第(7)步。
(7)扩展节点n，将其后继节点放入OPEN表的前端，并为
第三章 状态空间搜索策略
第三章 状态空间搜索策略
例3.3 设八数码难题的初始形状及目的形状分别如以下图 (a)和图(b)所示，试用有界深度优先搜索战略求解问题。 深度界限dm=5。
在搜索过程中，未扩展节点表OPEN 中的节点排序准那么是：“后入先出 〞，即后进入的节点排在前面，先进 入的节点排在后面。
第三章 状态空间搜索策略
第三章 状态空间搜索策略
算法3.3 形状空间图的深度优先搜索算法 (1)把初始节点S0放人OPEN表； (2)假设OPEN表为空，那么问题无解，退出； (3)从OPEN表中将其第一个节点(节点n)移出，放入已扩展
第三章 状态空间搜索策略
3.2 盲目搜索战略
3.2.1 形状空间图的搜索战略
形状空间表示法：是一种用形状和算符表示问题的方法。
当把一个待求解的问题表示为形状空间以后，就可以经过对 形状空间的搜索，实现对问题的求解。
形状空间图：形状空间的图示表示问题方式。形状空间图是 一个有向图，节点表示形状，有向边〔弧〕表示算符。
第三章 状态空间搜索策略
3.2.5 代价树的宽度优先搜索
搜索代价问题：在实践问题的搜索求解中，在将一个形状变 换成另一个形状时，往往所付出的操作代价(或费用)是不一 样的，也就是形状空间图中各有向边的代价是不一样的。这 是前面讨论搜索算法没有思索的。
➢ 深度优先搜索与宽度优先搜索的区别就在于：在对节 点n进展扩展时，其后继节点在OPEN表中的存放位置。

第三章检索策略与技巧精品PPT课件

第三章检索策略与技巧精品PPT课件
这是一种精确检索
课题2：查找有关面包添加剂方面的文献资料
这是对文献内容特征的检索，是一种相关性检索。
可有两种检索途径 分类途径：分类号 主题途径：主题词
检索字段及检索标识：
分类号字段：TS202.3 （食品添加剂）、TS213.21（面包类） 题名、文摘、关键词字段：面包、添加剂
4
分类检索表达式： 分类号: (TS202.3 * TS213.21) *为布尔逻辑运算符
采用精确检索可以加强检索的针对性，检索结果精准 注：慎用精确检索，用的不好可能会造成很大漏检。
23
23
5、 位置限定检索
是用位置算符限制检索词之间的位置关系，以提高检索精 确度的检索技术。
词与词的位置关系：
词序：两个检索词之间的先后次序，即哪个在先，哪个在后 词距：两个检索词之间的距离，有无间隔单词，间隔多少个词
代表词头相同的所有词 代替1个字符的变化 表示词根相同的所有词
举例说明： 用Absorb* 可检出下列词：
Absorb、Absorbs、Absorbing、Absorbtion、Absorbtivity
妇女Women 和woman：可用wom?n代表 用$manage可检索含有词根manag的所有词： manage、managed、managing、 management
名词变化 采用截词检索可扩展检索范围、简化检索词。 常用的截词符号：?、＊
截词类型： 后方截词：comput* 前方截词：*sea 中间截词： wom?n
（又叫前方一致） （具备此功能的数据库很少） （通配符）
20
20
以EI compendex数据库为例
前方一致截词符 * 通配符？ 自动取词根$
课题4：查找有关图书馆人事管理的文献资料

3.第三章 信息检索策略

3.第三章 信息检索策略

例：查找关于唐宋诗歌的文献
2 截词检索
截词检索就是用截断的词的一个局部 进行的检索，并认为凡满足这个词局部中 的所有字符（串）的文献，都为命中文献。 eg: market/marketable/marketing market?

常用截词符 ？、$、*
前方一致： “protect?”表示protect, protected, protecting 后方一致： “?computer”表示computer、 microcomputer、minicomputer

布尔逻辑运算符 与（AND、*）
A
B
或（OR、+）
A
B
非（NOT、-）
A
B
旅游 * 营销（旅游 AND 营销 ） 杜甫 + 杜诗 + 李杜 （杜甫 OR 杜诗 OR 李杜） 能源 - 核能（能源 not 核能）
布尔逻辑运算级别

“ - ” 优先，“ * ” 次之，“+” 最低， 即布尔逻辑的优先执行顺序是：NOT, AND，OR，但可根据需要，用括号 改变执行顺序。 在有括号的情况下， 先执行括号内的运算。
第二节 信息检索步骤与检索效果
1. 信息检索步骤 ◆分析课题 ﹡分析课题研究的意图和目的 ﹡分析课题所涉及的内容及学科范围 ﹡分析课题所需信息的类型
◆ 检索系统的选择 ◆ 检索点的确定 ◆制定检索式 例：灌溉用的橡塑多孔管 (橡胶 or 塑料 or 橡塑) and 多孔管 and 灌溉
◆查找文献线索并整理检索结果
文章)
la =Chinese (只查语种为中文的文献)

4 位置检索 位置检索是指运用位置算符表达
检索词概念之间的位置邻近关系， 也叫邻近检索。

第三章_搜索策略

第三章_搜索策略

思考：为什么不把船的状态放到状态空间中去？
2020/7/20
29
解析:四元组(m、f、s、v)
2020/7/20
30
状态空间搜索
——1.状态空间及其搜索的表示
(3)状态空间的搜索 状态空间的搜索记为SE，可表示为五元组：
SE=(S,O,E,I,G)； E——搜索引擎； I——问题的初始状态，I ∈ S； G——问题的目标状态集合，G S。 搜索引擎E——可以设计为实现任何搜索算法的控制系统。 基本思想——通过搜索引擎E寻找一个操作算子的调用序 列，使问题从初始状态I变迁到目标状态G之一。 解答路径——初-目变迁过程中的状态序列或相应的操作 算子调用序列。
搜索就是找到智能系统的动作序列的过程。
2020/7/20
3
搜索算法的输入是给定的问题，输出是表示为 动作序列的方案。
一旦有了方案，就可以执行该方案所给出的动 作了。（执行阶段）
因此，求解问题包括：
目标表示 搜索 执行
2020/7/20
4
➢一般给定问题就是确定该问题的一 些基本信息，一个问题由4部分组成:
共有10个操作算子
2020/7/20
24
渡河问题的状态空间有向图
2020/7/20
25
状态空间搜索
——1.状态空间及其搜索的表示
由此例可以看出
用状态空间方法表示问题时，首先必须定义状 态的描述形式，通过使用这种描述形式可把问 题的一切状态都表示出来。另外，还要定义一 组操作，通过使用这些操作可把问题由一种状 态转变为另一种状态。
问题的求解过程是一个不断把操作作用于状态 的过程。如果在使用某个操作后得到的新状态 是目标状态，就得到了问题的一个解。这个解 是从初始状态到目标状态所用操作构成的序列。

人工智能之搜索策略介绍课件

人工智能之搜索策略介绍课件
1 划中用于寻找最短 路径，如Dijkstra 算法和A*算法。
游戏AI：启发式搜 索策略在游戏中用
3 于寻找最优策略， 如国际象棋、围棋 等棋类游戏的AI算 法。
任务调度：启发式 搜索策略在任务调
2 度中用于优化任务 分配，如最小化任 务完成时间和资源 消耗。
机器人控制：启发 式搜索策略在机器
4 人控制中用于规划 机器人运动路径， 如自主导航和避障。
务调度、资源分配等。
启发式搜索策略的分类
局部搜索策略：只考虑当前状态
01
附近的解空间 全局搜索策略：考虑整个解空间
02
的所有状态 启发式搜索策略：根据问题特点， 03 选择合适的搜索策略 自适应搜索策略：根据搜索过程
04
中的信息，动态调整搜索策略
启发式搜索策略的应用实例
路径规划：启发式 搜索策略在路径规
强化学习搜索 策略：将强化 学习和搜索策 略相结合，以 实现更优的决 策和行动
强化学习搜索策略的分类
01 基于模型的搜索策略：使
用模型来预测状态和动作 的价值，如Q-learning 和Deep Q-Networks。
02 基于策略的搜索策略：直
接优化策略，如Policy Gradients和ActorCritic方法。
游戏AI：游戏策略、游戏 角色行为等
机器人控制：机器人路径 规划、机器人行为控制等
启发式搜索策略的定义
1
启发式搜索策略是一种基于 启发式信息的搜索策略。
2
它通过使用启发式信息来指 导搜索过程，以减少搜索空
间，提高搜索效率。
3
启发式信息可以是问题领域 的知识、经验或启发式函数。
4
启发式搜索策略广泛应用于 各种问题，如路径规划、任

第三讲如何制订检索策略PPT课件

第三讲如何制订检索策略PPT课件
研究生文献检索
研究生文献检索
2009.11
研究生文献检索
在上例中，运动会这一检索词有很多下
位词（比如奥运会、亚运会、全运会等），
选词不当，很容易漏检。在这种情况下，
可以将检索范围限定在体育类里，检索
词用“公共关系”。
研究生文献检索
研究生文献检索
研究生文献检索
检索技巧5：分类结合篇名
在“运动会中的公共关系”这个检索 案例中，我们用到了分类结合篇名的方法， 当检索题目中的某个概念十分宽泛难以用 某个具体的检索词来概括时（如运动会）， 我们可以将其限定在检索主题所属的类里 （体育类），这样可以保证既查得全，又 查得比较准确。
数据库检索常见问题
研究生文献检索
研究生文献检索
常用检索工具
一、文献信息检索
（一）图书：读秀学术搜索（读秀与超星电
子书的区别）
（二）期刊论文：《中国期刊全文数据库》
研究生文献检索
（三）学位论文：
《中国博士论文全文数据库》 《会议论文数据库》
研究生文献检索
检索案例6：
皮划艇运动中的放松技术
检索式为：皮划艇 and 放松
研究生文献检索
研究生文献检索
研究生文献检索
研究生文献检索
研究生文献检索
研究生文献检索
检索技巧6：中心词限定法
在检索题目中，一般都会有一个中心词 （最核心的检索词），当检索结果很少的 时候，可以只限定最核心的检索词在篇名 中出现，其余检索词则放宽至摘要或全文 中出现，一方面可以保障检索结果的相关 度，另一方面也能有更全面的检索结果。
研究生文献检索
❖如果江苏人写了一篇《论山芋的营养 功效》，四川人用“红苕”一词去查 ，能查出来吗？查不出来怎么办？

Practical Reasoning(2020年整理).ppt

Practical Reasoning(2020年整理).ppt

Artificial Intelligence
Expert System: 5
概述（2）
© Graduate University , Chinese academy of Sciences.
• 一个专家系统应该具备以下三个要素： （1）具备某个应用领域的专家级知识； （2）能模拟专家的思维； （3）能达到专家级的解题水平。
Expert System: 15
© Graduate University , Chinese academy of Sciences.
专家系统工具CLIPS(1)
• 早期的专家系统工具大都用LISP、Prolog等编程语言开发， 它们的共同问题是运行速度慢，可移植性差， 解决复杂问题 的能力差。
<slot-definition>的定义可以为： ( slot <slot-name> ) | ( multislot <slot-name>)
Artificial Intelligence
Expert System: 18
© Graduate University , Chinese academy of Sciences.
Artificial Intelligence
Expert System: 13
© Graduate University , Chinese academy of Sciences.
专家系统的基本结构(3)
• 知识获取负责建立、修改和扩充知识库，是专家系统中把问 题求解的各种专门知识从人类专家的头脑中或其他知识源那 里转换到知识库中的一个重要机构。
Expert System: 11
专家系统的基本结构(1)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Q () ((1,1))
第三章搜索策略 (ppt)PracticalReaso(1)
() ((1,1)) ((1,1) (2,3))
Q Q
第三章搜索策略 (ppt)PracticalReaso(1)
() ((1,1)) ((1,1) (2,3))
Q
第三章搜索策略 (ppt)PracticalReaso(1)
7
5
765
第三章搜索策略 (ppt)PracticalReaso(1)
搜索控制策略（3）
• 不可撤回的控制策略
283
164
7
5
283
1
4
765
f=4
f=3
12
3
184
765
f=3
123
8
4
765
f=0
123 84
765
f=1
23 184 765
f=2
第三章搜索策略 (ppt)PracticalReaso(1)
状态空间表示法(2)
状态空间:由问题的全部状态及一切可用算符所构成的集合称为问题的状态
空间.一般表示为: (S, F, G)
S:问题所有的初始状态集合; F:算符集合; G:目标状态集合
算符: 引起状态中某些分量发生变化, 从而使问题由一个状 态变为另一个状态的操作称为算符.
状态空间表示法是用“状态”和“算符”表示问题的一种 方法
状态空间图:状态空间的图式表示,称为状态空间图.其中节 点表示状态,有向边(弧)表示算符.
第三章搜索策略 (ppt)PracticalReaso(1)
状态空间表示法(3)
• 路径
– 状态序列
• 搜索
– 寻找从初始状态到目标状态的路径;
S0
Sg
第三章搜索策略 (ppt)PracticalReaso(1)
第三章搜索策略 (ppt)PracticalReaso(1)
搜索(4)
▪ 盲目搜索:也称为无信息搜索，即只按预定的控制策 略进行搜索,在搜索过程中获得的中间信息不用来改 进控制策略
▪ 启发式搜索: 在搜索中加入了与问题有关的启发性信 息,用于指导搜索朝着最有希望的方向进行,加速问题 的求解过程并找到最优解
搜索控制策略（4）
• 不可撤回的控制策略
283
1
4
765
2283
14
765
f=3
f=3
1
3
824
765
f=1
13 824 765
f=2
83 214 765
f=3
813 24
765
f=3
8
3
214
765

f=3
813
2
4
765
f=3
第三章搜索策略 (ppt)PracticalReaso(1)
搜索控制策略（5）
Q Q
((1,1) (2,3)) ((1,1) (2,4))
((1,2) (2,4))
((1,1) (2,4) (3.2))
((1,2) (2,4) (3,1))
((1,2) (2,4) (3,1) (4,3))
第三章搜索策略 (ppt)PracticalReaso(1)
与/或树表示法（1）
基本概念 ▪ 与/或树是用于表示问题及其求解过程的又一种形式化方 法. ▪ 复杂问题的简化方法 • 分解:把一个问题分解到不需再分解或不能再分解为 止,然后对每个子问题进行求解,然后把各子问题的解 复合起来,就得到原问题的解. • 等价变换:利用同构或同态的等价变换,把复杂问题转 换成若干个较为容易求解的新问题.若新问题中有一 个可求解,则就得到了原问题的解.
？
搜索策略反映了状态空间或问题空间扩展的方法，也决定了状态或问 题的访问顺序。
在AI领域，状态空间图由初始状态和算子隐含地表示，经常是无限的 ，它的复杂度根据下面三个值来表达：
分支因子b：任何节点的后继的最大个数 最浅的目标节点的深度d 状态空间中任何路径的最大长度m
第三章搜索策略 (ppt)PracticalReaso(1)
第三章搜索策略 (ppt)PracticalReaso(1)
与/或树表示法（2）
• 例子:三阶梵塔问题 设有A,B,C三个金片以及三个钢针,三个金片按自上而下从小到大的 顺序穿在1号钢针上,要求把它们全部移到3号钢针上,而且每次只能 移到一个金片,任何时候都不能把大的金片压在小的金片上面.
▪ 用与/或树表示:问题分解 (1)为了把三个金片全部移到3号针上,必须先把C移到3号针上 (2)为了移到C,必须把A和B移到2号针上 (3)当C移到3针后,就可把A和B移到3针上,完成问题求解
第三章搜索策略 (ppt)PracticalReaso(1)
概述(2)
1974年，Nilsson归纳出的AI研究的基本问题 • 知识的模型化和表示 • 常识性推理、演绎和问题解决 • 启发式搜索 • 人工智能系统和语言
搜索是人工智能中的一个基本问题,是推理不可分割的一部分 直接关系到智能系统的性能和运行效率
第三章搜索策略(ppt)PracticalReaso(1)
2020/12/7
第三章搜索策略 (ppt)PracticalReaso(1)
搜索策略
第三章搜索策略 (ppt)PracticalReaso(1)
主要内容
• 概述
• 状态空间搜索
状态空间的一般搜索过程 广度优先搜索 深度优先搜索 启发式搜索 A*算法
() ((1,1)) ((1,1) (2,3)) ((1,1) (2,4)) ((1,1) (2,4) (3.2))
Q Q
第三章搜索策略 (ppt)PracticalReaso(1)
() ((1,1)) ((1,1) (2,3)) ((1,1) (2,4)) ((1,1) (2,4) (3.2))
主要内容
• 概述
• 状态空间搜索
状态空间的一般搜索过程 广度优先搜索 深度优先搜索 启发式搜索 A*算法 ▪ 问题规约搜索 ▪ 博弈
第三章搜索策略 (ppt)PracticalReaso(1)
状态空间搜索过程要点（1）
• 求解一个能够满足目标条件的问题可以表达为搜索一个图以找到一个 满足目标状态描述的节点问题.搜索过程的要点如下: – 起始节点:对应于初始状态描述 – 后继节点:把适用于某个节点状态描述的一些算符用来推算该节点 而得到的新节点,称为该节点的后继节点 – 指针:从每个后继节点返回指向其父辈节点 – 检查各后继节点看是否为目标节点.
第三章搜索策略 (ppt)PracticalReaso(1)
状态空间表示法(1)
状态空间表示法：用来表示问题及其搜索过程的一种方法 状态
▪ 状态是描述问题求解过程中任一时刻状况的数据结构.
237 51
486
{A，B，C，D}
（2, 3,7 ,0 , 5, 2, 4, 8, 6）
第三章搜索策略 (ppt)PracticalReaso(1)
问题规约搜索
博弈
第三章搜索策略 (ppt)PracticalReaso(1)
概述(1)
• 问题求解 ▪ AI中每个研究领域都有其各自的特点和规律,但就求解问 的过程看,都可抽象为一个问题求解过程。 ▪ 问题求解过程实际上是一个搜索,广义地说,它包含了全部 计算机科学。 ▪ 任何问题求解技术都包括两个重要的方面:表示和搜索 ▪ 表示是基本的,搜索必须要在表示的基础上进行。表示关 到搜索的效率。 ▪ 本章讨论的表示主要包括: ▪ 状态空间表示 ▪ 问题空间表示
Q
第三章搜索策略 (ppt)PracticalReaso(1)
() ((1,1)) ((1,1) (2,3)) ((1,1) (2,4)) ((1,1) (2,4) (3.2))
第三章搜索策略 (ppt)PracticalReaso(1)
Q ()
((1,1))
((1,2))
((1,1) (2,3)) ((1,1) (2,4))
() ((1,1))
((1,2))
Q Q
Q
((1,1) (2,3)) ((1,1) (2,4))
((1,2) (2,4))
((1,1) (2,4) (3.2))
((1,2) (2,4) (3,1))
第三章搜索策略 (ppt)PracticalReaso(1)
() ((1,1))
((1,2))
Q Q
搜索控制策略（1）
搜索控制策略 – 不可撤回的控制策略; – 试探性控制策略 • 回溯型 • 图搜索
第三章搜索策略 (ppt)PracticalReaso(1)
搜索控制策略（2）
• 不可撤回的控制策略 • 例：八数码问题 • 评价函数:f： （规定: 评价函数非增）
283
123
164 与 8
4 的差异为4
• 不可撤回的控制策略 可能无解
125 84
763
f=2
123 84
765
目标
第三章搜索策略 (ppt)PracticalReaso(1)
搜索控制策略（6）
• 回溯策略 • 例：四皇后问题
第三章搜索策略 (ppt)PracticalReaso(1)
()
第三章搜索策略 (ppt)PracticalReaso(1)
AI为什么要研究search?
– 问题没有直接的解法; – 需要探索地求解;
第三章搜索策略 (ppt)PracticalReaso(1)
搜索(3)
• 什么是搜索 ▪ 根据问题的实际情况不断寻找可利用的知识,构造 出一条代价较少的推理路线,使问题得到圆满解决 的过程称为搜索 包括两个方面： --- 找到从初始事实到问题最终答案的一条推理 路径 --- 找到的这条路径在时间和空间上复杂度最小