当前位置：文档之家 › 人工智能第3章

人工智能第3章

  • 格式：ppt
  • 大小：380.00 KB
  • 文档页数：83

下载文档原格式

  / 83

合集下载

人工智能教程习题及答案第3章习题参考解答

人工智能教程习题及答案第3章习题参考解答

第三章确定性推理方法习题参考解答3.1 练习题3.1 什么是命题？请写出3个真值为T 及真值为F 的命题。

3.2 什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？3.3 谓词逻辑和命题逻辑的关系如何？有何异同？3.4 什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。

3.5 什么是谓词公式？什么是谓词公式的解释？设D= {1,2} ，试给出谓词公式（ x）（ y）（P（x,y） Q（x,y））的所有解释，并且对每一种解释指出该谓词公式的真值。

3.6对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的辖域。

（1）( x)(P(x, y) ( y)(Q(x, y) R(x, y)))（2）( z)( y)(P(z, y) Q(z, x)) R(u, v)（3）( x)(~ P( x, f (x )) ( z)(Q(x,z) ~ R(x,z)))（4）( z)(( y)(( t)(P(z, t) Q(y, t)) R(z, y))（5）( z)( y)(P(z, y) ( z)(( y)(P(z, y) Q(z, y) ( z)Q(z, y))))什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含？3.7什么是置换？什么是合一？什么是最一般的合一？3.8判断以下公式对是否可合一；若可合一，则求出最一般的合一：3.9（1）P(a,b) ，P(x, y)（2）P(f(z),b) ，P(y, x)（3）P(f(x), y) ，P(y, f(a))（4）P(f(y), y,x) ，P(x, f(a), f(b))（5）P(x, y) ，P(y, x)什么是范式？请写出前束型范式与SKOLEM 范式的形式。

3.10什么是子句？什么是子句集？请写出求谓词公式子句集的步骤。

3.113.12谓词公式与它的子句集等值吗？在什么情况下它们才会等价？3.13 把下列谓词公式分别化为相应的子句集：(1)( z)( y)(P(z, y) Q(z, y))(2)( x)( y)(P(x, y) Q(x, y))(3)( x)( y)(P(x, y) (Q(x, y) R(x, y)))(4)( x)( y)( z)(P(x, y) Q(x, y) R(x, z))(5)( x)( y)( z)( u)( v)( w)(P(x, y,z,u,v,w) (Q(x, y, z,u, v, w) ~R(x, z, w)))3.14 判断下列子句集中哪些是不可满足的：(1)S {~ P Q,~ Q,P,~ P}(2)S {P Q,~ P Q,P ~ Q,~ P ~ Q}(3)S {P(y) Q(y), ~ P(f(x)) R(a)}(4)S {~ P(x) Q(x), ~ P(y) R(y), P(a),S(a),~ S(z) ~ R(z)}(5)S {~ P(x) ~ Q(y) ~ L(x, y), P(a), ~ R(z) L(a, z), R(b), Q(b)}(6)S {~ P(x) Q(f(x), a), ~ P(h(y)) Q(f(h(y)), a) ~ P(z)}(7)S {P(x) Q(x) R(x),~ P(y) R(y),~Q(a),~ R(b)}(8)S {P(x) Q(x),~ Q(y) R(y), ~ P(z) Q(z),~ R(u)}3.15 为什么要引入Herbrand 理论？什么是H 域？如何求子句集的H 域？3.16 什么是原子集？如何求子句集的原子集？3.17 什么是H 域解释？如何用域D 上的一个解释I 构造H 域上的解释I *呢？3.18 假设子句集S＝{P(z) ∨Q(z),R(f(t))} ，S 中不出现个体常量符号。

人工智能 chapter3

人工智能 chapter3

29
● 启发式搜索策略
假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一
个搜索空间。因此，问题就在于如何有效地搜索这个给定空间。 启发信息按其用途可分为下列3种： (1) 用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索 中那样盲目地扩展。 (2) 在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节 点，以免盲目地同时生成所有可能的节点。
22ห้องสมุดไป่ตู้
有深度界限的深度优先搜索算法如下： (1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得 到一个解。 (2) 如果OPEN为一空表，则失败退出。 (3) 把第一个节点(节点n)从OPEN表移到CLOSED表。 (4) 如果节点n的深度等于最大深度，则转向(2)。 (5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后 裔，则转向(2)。 (6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，
度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。
从图可见，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必 须搜索完本层的所有节点。
14
宽度优先搜索算法如下： (1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得 一个解答)。 (2) 如果OPEN是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节
1
状态图的例子：
设有三枚钱币，其排列处在“正，正，反”状态，现允许每次 可翻动其中任意一个钱币，问只允许操作三次的情况下，如何 翻动钱币使其变成“正，正，正”或“反，反，反”状态。 若“正面”用“1”表示，“反面”用“0”表示，则问题化成求 解从初始状态（1,1,0）到目标状态（1，1，1）或(0,0,0)的路 径问题，且该路径的长度为3。 （1，1，0）--------->（1，1，1）或（1,1,0）--------->(0,0,0)

人工智能第三章遗传算法、蚁群算法、粒子群算法

人工智能第三章遗传算法、蚁群算法、粒子群算法
而遗传算法为解决这类问题提供了一个有效的途径和通用框架， 开创了一种新的全局优化搜索算法。
2020/5/23
10
遗传算法中，将n维决策向量 X x1 x2 xn T 用n个记号Xi (n＝
l，2，，n)所组成的符号串X来表示：
X X1X 2 X n X x1 x2 xn T
把每一个Xi看作一个遗传基因，它的所有可能取值称为等位基因， 这样，X就可看做是由n个遗传基因所组成的一个染色体。 —般情况下，染色体的长度n是固定的，但对一些问题n也可以是 变化的。
基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种 人工系统具有优良的自适应能力和优化能力。
遗传算法所借鉴的生物学基础就是生物的遗传和进化。
2020/5/23
3
虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机 制，也不完全清楚染色体编码和译码过程的细节，更不完全了解 其控制方式，但遗传与进化的以下几个特点却为人们所共识：
下面是在遗传算法的发展进程中一些关键人物所做出的一些主 要贡献。
2020/5/23
21
1、J．H．Holland
60年代，Ho11and提出在研究和设计人工自适应系统时，可以借 鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分 认识到了交叉、变异等运算策略在自适应系统中的重要性。
70年代初，Ho11and教授提出了遗传算法的基本定理——模式定 理(schema Theorem)，从而奠定了遗传算法的理论基础。模式定 理揭示出了群体中的优良个体(较好的模式)的样本数将以指数级 规律增长，因而从理论上保证了遗传算法是一个可以用来寻求 最优可行解的优化过程。1975年，Ho11and出版了第一本系统论 述遗传算法和人工自适应系统的专著《自然系统和人工系统的 自适应性(Adaptation in natural and artificial system)》。

人工智能第三章搜索推理技术

人工智能第三章搜索推理技术

人工智能第三章搜索推理技术教学内容：本章在上一章知识表示的基础上研究问题求解的方法，是人工智能研究的又一核心问题。

内容包含早期搜索推理技术，如图搜索策略与消解原理；与高级搜索推理技术，如规则演绎系统、产生式系统、系统组织技术、不确定性推理与非单调推理。

教学重点：图搜索策略、消解原理、规则演绎系统、产生式系统。

教学难点：启发式搜索、规则双向演绎系统等。

教学方法：课堂教学为主，辅以恰当的实验。

注意结合前面所学知识表示的基础内容，将其与问题求解方法融为一体。

及时提问、收集学生学习情况。

尽量使用实例与网络课程中的多媒体素材进行讲解。

教学要求：重点掌握通常图搜索策略与消解原理，掌握各类搜索方法与产生式系统原理，熟悉规则演绎系统的基本原理，对系统组织技术、不确定性推理与非单调推理等高级推理技术作通常性熟悉。

3.1 图搜索策略教学内容：本节介绍图搜索的通常策略，作为各类图搜索技术的基础。

教学重点：图搜索的通常过程、OPEN表与CLOSE表的概念。

教学难点：OPEN表与CLOSE表的物理意义。

教学方法：课堂教学为主，通过提问完全弄清图搜索的基本概念。

教学要求：重点掌握图搜索通常策略，掌握OPEN表与CLOSE表的构成及作用。

1、图搜索策略的定义图搜索策略可看作一种在图中寻找路径的方法。

初始节点与目标节点分别代表初始数据库与满足终止条件的数据库。

求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。

研究图搜索的通常策略，能够给出图搜索过程的通常步骤。

2、图搜索算法中的几个重要名词术语（1）OPEN表与CLOSE表（2）搜索图与搜索树3、图搜索(GRAPHSEARCH)的通常过程(1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。

(2) 建立一个叫做CLOSED的已扩展节点表，其初始为空表。

(3) LOOP：若OPEN表是空表，则失败退出。

(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

人工智能第三章归结推理方法

人工智能第三章归结推理方法

Y
失败退出
成功退出
逆向推理的流程图
22
逆向推理




对上例，采用逆向推理，其推理过程如下： 推理开始前，综合数据库和假设集均为空。 推理开始后，先将初始证据A和目标C分别 放入综合数据库和假设集，然后从假设集中取 出一个假设C，查找C是否为综合数据库中的 已知事实，回答为“N”。 再检查C是否能被知识库中的知识所导出， 发现C可由r1 导出，于是r1 被放入可用知识集。 由于知识库中只有r1可用，故可用知识集中仅 含r1。
13
正向推理


正向推理是从已知事实出发、正向使用推理规 则，亦称为数据驱动推理或前向链推理。 算法描述 (1) 把用户提供的初始证据放入综合数据库； (2) 检查综合数据库中是否包含了问题的解， 若已包含，则求解结束，并成功推出；否则执 行下一步； (3) 检查知识库中是否有可用知识，若有，形 成当前可用知识集，执行下一步；否则转(5)。
11
推理的控制策略

推理过程不仅依赖于所用的推方法，同时也依 赖于推理的控制策略。 推理的控制策略是指如何使用领域知识使推理 过程尽快达到目标的策略。


控制策略的分类：由于智能系统的推理过程一 般表现为一种搜索过程，因此，推理的控制策 略可分为推理策略和搜索策略。
推理策略：主要解决推理方向、冲突消解等问 题，如推理方向控制策略、求解策略、限制策 略、冲突消解策略等
18
正向推理

正向推理的主要优点
比较直观，允许用户主动提供有用的事实信息， 适合于诊断、设计、预测、监控等领域的问题求 解。 正向推理的主要缺点

推理无明确目标，求解问题是可能会执行许多 与解无关的操作，导致推理效率较低。

人工智能第三章_搜索策略-2


30
与或图搜索
1)与或图搜索的基本概念 3、解图的生成★
解图纯粹是一种“与”图 解图中，节点或节点组间不存在“或”关系； 所有叶节点都是终节点
与或图中存在“或”关系，搜索到多个解图；
2019/12/21
31
与或图搜索
2) 解图、解图代价、能解节点和不能解节点的定义
(1)解图——与或图（记为G）任一节点（记为n）到终 节点集合的解图（记为G‘）是G的子图。
5
回溯策略和爬山法
2）回溯策略
三种失败状态：
不合法状态（如传教士和野人问题中所述的那样） 旧状态重现（如八数码游戏中某一棋盘布局的重现，会导 致搜索算法死循环）， 状态节点深度超过预定限度（例如八数码游戏中，指示解 答路径不超过6步）。
回溯条件
失败状态，由算法第（2）句指示； 搜索进入“死胡同”，由该算法的第(4)句定义。
引入K-连接
父子节点间可以存在“与”关系 结果——解图。
解答路径往往不复存在，代之以广义的解路径—— 解图。
2019/12/21
24
与或图搜索
1)与或图搜索的基本概念 1、K-连接★ 从父节点到K个子节点的连接，子节点间有“与”关系； 以圆弧指示这些子节点间的“与”关系； 一个父节点可以有多个K-连接
(1,3,3)(3,3,3)
2019/12/21
(3,1,1)(3,2,1)
22
(1,2,3)(1,3,3)
梵塔问题
子问题间有交互作用， 问题分解注意正确的顺序
(1,1,1)(3,3,3)
1
5
6
(1,1,1)(2,2,1) (2,2,1)(2,2,3) (2,2,3)(3,3,3)

人工智能原理及应用第3章 确定性推理方法


3.1 推理概述
3.1.2 推理的方法
1．演绎推理： 例：有如下三个判断： ①计算机系的学生都会编程序；（一般性知识） ②程强是计算机系的一位学生；（具体情况） ③因此程强会编程序。（结论）
这是一个三段论推理。其中：“①计算机系的学生都会编程序” 是大前提，“②程强是计算机系的一位学生”是小前提，那么“③ 程强会编程序”是经演绎推出来的结论。其结论蕴含在大前提中， 这就是典型的演绎推理三段论。
N
Y Y
以正向推理结果为假设
输入进行反向推理
N
输出结果
Y
成功退出
需要进行正向推理吗？
3.1 推理概述
3.1.4 推理中的冲突
在推理过程中，系统要不断地用数据库中的事实与知识库中的 规则进行匹配，当有一个以上规则的条件部分和当前数据库相匹配 时，就需要有一种策略来决定首先使用哪一条规则，这就是冲突解 决策略。冲突解决策略实际上就是确定规则的启用顺序。
33演绎推理方法332演绎推理的特点正向演绎推理逆向演绎推理问题求解的描述事实文字与或形事实文字合取式规则lw规则wl目标文字析取形目标文字与或形初始与或图相应于事实表达式事实表达式的与或树相应于目标公式事实表达式的与或树演绎推理f规则事实目标b规则目标事实结束条件包含所有目标节点的一致解图以事实节点作为所有终节点的一致解图34归结推理方法341子句集及其化简342herbrand海伯伦定理343robinson鲁宾逊归结原理344利用归结推理进行定理证明345应用归结原理进行问题求解在谓词演算中利用前面列出的等价式和永真蕴含式可以从已知的一些公式推导出新的公式这个导出的公式叫做定理在推导过程中使用的推理规则序列就成了该定理的一个证明而这种推导就是归结推理方法
形成可用知识集

人工智能教程习题及答案第3章习题参考解答

第三章确定性推理方法习题参考解答3.1 练习题3.1 什么是命题？请写出3个真值为T 及真值为F 的命题。

3.2 什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？3.3 谓词逻辑和命题逻辑的关系如何？有何异同？3.4 什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。

3.5 什么是谓词公式？什么是谓词公式的解释？设D= {1,2} ，试给出谓词公式（ x）（ y）（P（x,y） Q（x,y））的所有解释，并且对每一种解释指出该谓词公式的真值。

3.6对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的辖域。

（1）( x)(P(x, y) ( y)(Q(x, y) R(x, y)))（2）( z)( y)(P(z, y) Q(z, x)) R(u, v)（3）( x)(~ P( x, f (x )) ( z)(Q(x,z) ~ R(x,z)))（4）( z)(( y)(( t)(P(z, t) Q(y, t)) R(z, y))（5）( z)( y)(P(z, y) ( z)(( y)(P(z, y) Q(z, y) ( z)Q(z, y))))什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含？3.7什么是置换？什么是合一？什么是最一般的合一？3.8判断以下公式对是否可合一；若可合一，则求出最一般的合一：3.9（1）P(a,b) ，P(x, y)（2）P(f(z),b) ，P(y, x)（3）P(f(x), y) ，P(y, f(a))（4）P(f(y), y,x) ，P(x, f(a), f(b))（5）P(x, y) ，P(y, x)什么是范式？请写出前束型范式与SKOLEM 范式的形式。

3.10什么是子句？什么是子句集？请写出求谓词公式子句集的步骤。

3.113.12谓词公式与它的子句集等值吗？在什么情况下它们才会等价？3.13 把下列谓词公式分别化为相应的子句集：(1)( z)( y)(P(z, y) Q(z, y))(2)( x)( y)(P(x, y) Q(x, y))(3)( x)( y)(P(x, y) (Q(x, y) R(x, y)))(4)( x)( y)( z)(P(x, y) Q(x, y) R(x, z))(5)( x)( y)( z)( u)( v)( w)(P(x, y,z,u,v,w) (Q(x, y, z,u, v, w) ~R(x, z, w)))3.14 判断下列子句集中哪些是不可满足的：(1)S {~ P Q,~ Q,P,~ P}(2)S {P Q,~ P Q,P ~ Q,~ P ~ Q}(3)S {P(y) Q(y), ~ P(f(x)) R(a)}(4)S {~ P(x) Q(x), ~ P(y) R(y), P(a),S(a),~ S(z) ~ R(z)}(5)S {~ P(x) ~ Q(y) ~ L(x, y), P(a), ~ R(z) L(a, z), R(b), Q(b)}(6)S {~ P(x) Q(f(x), a), ~ P(h(y)) Q(f(h(y)), a) ~ P(z)}(7)S {P(x) Q(x) R(x),~ P(y) R(y),~Q(a),~ R(b)}(8)S {P(x) Q(x),~ Q(y) R(y), ~ P(z) Q(z),~ R(u)}3.15 为什么要引入Herbrand 理论？什么是H 域？如何求子句集的H 域？3.16 什么是原子集？如何求子句集的原子集？3.17 什么是H 域解释？如何用域D 上的一个解释I 构造H 域上的解释I *呢？3.18 假设子句集S＝{P(z) ∨Q(z),R(f(t))} ，S 中不出现个体常量符号。

人工智能第三章_搜索策略-1

❖搜索什么
搜索什么通常指的就是目标。
❖在哪里搜索
在哪里搜索就是“搜索空间”。搜索空间通常 是指一系列状态的汇集，因此称为状态空间。
和通常的搜索空间不同，人工智能中大多数问题的状 态空间在问题求解之前不是全部知道的。
2020/10/31
6
所以，人工智能中的搜索可以分成两个 阶段：
状态空间的生成阶段 在该状态空间中对所求问题状态的搜索
（1）初始状态集合：定义了初始 的环境。
（2）操作符集合：把一个问题从 一个状态变换为另一个状态的 动作集合。
（3）目标检测函数：用来确定一 个状态是不是目标。
（4）路径费用函数：对每条路径 赋予一定费用的函数。
其中，初 始状态集 合和操作 符集合定 义了问题 的搜索空
间。
2020/10/31
5
➢ 在人工智能中，搜索问题一般包括两个重 要的问题：
分析：通过引入一个三维变量将问题表示出来。设 三维变量为：Q=[q1,q2,q3]，式中qi (i=1,2,3)=1表 示钱币为正面，qi (i=1,2,3)=0表示钱币为反面。 则三个钱币可能出现的状态有8种组合： Q0=(0,0,0),Q1=(0,0,1),Q2=(0,1,0),Q3=(0,1,1),Q4= (1,0,0),Q5=(1,0,1), Q6=(1,1,0), Q7=(1,1,1)。 即初始状态为Q5，目标状态为Q0或Q7，要求步数为3。
2020/10/31
21
钱币问题的状态空间图
2020/10/31
22
状态空间搜索
——1.状态空间及其搜索的表示
(2)状态空间表示的经典例子“传教士和野人问题” ★
问题的描述：
N个传教士带领N个野人划船过河； 3个安全约束条件：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
（2）深度优先搜索所求得的解答路径不一定是最 短路径；
（3）深度界限得选择很重要，过大，可能会影响 搜索效率，过小，有可能求不到解。有界深度 优先搜索策略是不完备的。 例3.3，P74，图3.8
3.1.4 等代价搜索
定义
有些问题并不要求有应用算符序列 为最少的解，而是要求具有某些特性的 解。宽度优先搜索可被推广用来解决这 种寻找从起始状态至目标状态的具有最 小代价的路径问题，这种推广了的宽度 优先搜索算法叫做等代价搜索算法。
（6）扩展节点n，同时生成不是n的祖先的那些 后继节点的集合M。把M中的这些成员作为n 的后继节点加入图G中。
（7）对那些未曾在G中出现过的（既未曾在 OPEN表上或CLOSED表上出现过的）M成员 设置一个通向n的指针。把M的这些成员加进 OPEN表。对已经在OPEN表或CLOSED表上 的每一个M成员，确定是否需要更改通到n的 指针方向。对已在CLOSED表上的每个M成员， 确定是否需要更改图G中通向它的每个后继节 点的指针方向。
A
90
80
B
170 160 110
C
85 140 100
65
D
E
80
第3章 搜索原理
3.1 盲目搜索 3.2 启发式搜索 3.3 博弈树搜索 3.4 遗传算法 3.5 模拟退火算法
3.1 启发式搜索
启发信息是进行搜索技术所需要的一 些有关具体问题领域的特性的信息。
利用启发信息的搜索方法称为启发式 搜索或有信息搜索。 1、启发信息分类
宽度优先搜索（续）
宽度优先搜索算法（P71） 宽度优先搜索方法分析
（1）将OPEN表作为“先进先出”的队列进行操 作；
（2）宽度优先搜索方法能够保证在搜索树中找到 一条通向目标节点的最短路径（即宽度优先搜 索策略是完备的）；
（3）搜索树提供了所有存在的路径； （4）盲目性较大，当目标节点较远时，将产生大
第3章 搜索原理
知识点 重难点 学习要求
知识点
盲目搜索 启发式搜索 博弈树搜索 遗传算法 模拟退火算法
重难点
宽度优先 深度优先 等代价搜索 有序搜索 A*算法 博弈树搜索
学习要求
重点掌握宽度优先和深度优先搜索算法 掌握等代价搜索算法 掌握启发式搜索相关知识 理解博弈树搜索相关技术 掌握遗传算法基本原理 理解模拟退火算法基本原理
度.
启发式搜索（续）
有序搜索的有效性直接取决于f的选 择，如果选择的f不合适，有序搜索就可 能失去一个最好的解甚至全部的解。
正确地选择估价函数对确定搜索结 果具有决定性地作用。使用不能识别某 些节点真实希望的估价函数会形成非最 小代价路径；而使用一个过多地估计了 全部节点希望地估价函数又会扩展过多 的节点。
用两个表分别存放已扩展节点和未扩展
节点，OPEN表存放未扩展节点， CLOSED表存放已扩展节点。两个表的 结构如下：
OPEN表： 节点
父节点
CLOSED表： 编号 节点 父节点
图搜索策略（续）
状态空间图的一般搜索算法：
（1）建立一个只含有起始节点S的搜索图G，把S 放到OPEN表中。
（2）建立CLOSED表，且置为空表。
量无用节点。
例3.2，P72，图3.5
3.1.3 深度优先搜索
定义
深度优先搜索也是一种盲目搜索策略，其 基本思想是：首先扩展最新产生的（即最深） 节点，即从初始节点S开始，在其后继节点中 选择一个节点，对其进行考察，若它不是目标 节点，则对该节点进行扩展，并再从它的后继 节点中选择一个节点进行考察。依次类推，一 直搜索下去，当到达某个既非目标节点又无法 继续扩展的节点时，才选择其兄弟节点进行考 察。
4、图搜索方法的几点分析
（1）对OPEN表进行排序（盲目或启发式搜索）。 （2）被选作扩展的节点为目标节点时，成功，回
溯，可找到路径。否则，失败终止情况下没有解 路径。
在利用状态空间搜索方法求解问题时，并不是将整个 问题的状态空间图全部输入计算机，而是只存入问题有 关的部分状态空间图，这部分是在搜索过程中生成的， 并且每前进一步，都要检查是否到达目标节点，这样就 可尽量减少生成与问题求解无关的状态，从而提高了解 题效率，节省了存储空间。
图搜索策略（续）
（8）按某一任意方式或按某个探试值，重 排OPEN表。
（9）转第（3）步。
举例说明：P68，例3.1
图搜索策略（续）
3、搜索图与搜索树
图搜索过程生成一个明确的图G（称为搜索图）和一
个G的子集T（称为搜索树），树T上的每个节点也在 图G中。
例：二阶Hanoi塔问题。状态空间图如下。
启发式搜索（续）
应用举例： （P78） 采用简单的估价函数f(n)=d(n)+w(n), 其中，d(n)是搜索树中节点n的深度； w(n)用来计算节点n与目标状态节点Sg 相比较，错位的数码个数。
按用途可分为3种。 （1）用于决定要扩展的下一个节点，以免
像在宽度优先或深度优先搜索中那样盲目 地扩展。
启发式搜索（续）
（2）在扩展一个节点的过程中，用于决 定要生成哪一个或哪几个后继节点，以 免盲目地同时生成所有可能的节点。
（3）用于决定某些应该从搜索树中抛弃 或修剪的节点。
2、估价函数 用来估算希望程度的量度，叫做估价
有序搜索又可分为两种：局部最佳优先 搜索和全局最佳优先搜索。
启发式搜索（续）
有序搜索算法（见P76-77） 宽度优先搜索、等代价搜索和深度优
先搜索均是有序搜索的特例。 宽度优先搜索，f(i)是节点i的深度。 等代价搜索，f(i)是从起始节点至节点i这段
路径的代价。 深度优先搜索，f(i)是节点i距目标节点的深
等代价搜索（续）
（3）从OPEN表中选择一个节点i，使其g(i)为最小。 如果有几个节点都合格，那么就要选择一个目标节点 作为节点i（如果有目标节点）；否则，就从中选一 个作为节点i。把节点i从OPEN表移至CLOSED表中；
（4）如果节点i为目标节点，则求得一个解；
（5）扩展节点i。如果没有后继节点，则转向步骤（2）
盲目搜索（续）
启发式搜索又称有信息搜索，指搜索求 解过程中，根据问题本身的特性或搜索 过程中产生的一些信息来不断改变或调 整搜索的方向，使搜索朝着最有希望的 方向前进，加速问题的求解，并找到最 优解。求解的效率更高，更易于求解复 杂的问题。
盲目搜索（续）
3、研究和选用搜索算法的原则 （1）有限搜索还是无限搜索？ （2）搜索空间是静态还是动态生成？ （3）已知目标还是未知目标？ （4）只要目标还是也要路径？ （5）状态空间搜索还是问题空间搜索？ （6）有约束还是无约束？ （7）数据驱动还是目标驱动？ （8）单向搜索还是双向搜索？ （9）盲目搜索还是启发式搜索？ （10）有对手搜索还是无对手搜索？
（6）对于节点i的每个后继节点j，计算 g(j)=g(i)+c(i,j)，并把所有后继节点j放进OPEN表。 提供回到节点i的指针。
（7）转向步骤（2）。
等代价搜索（续）
举例分析
例：推销员旅行问题。
假设A，B，C，D，E是5个城市，推销员从
城市A出发，到达城市E，走怎样的路线费用
最省？5个城市间的交通图及每两个城市间的
函数。
启发式搜索（续）
一个节点的“希望”有几种不同的 定义方法。在状态空间问题中，一种定 义是估算目标节点到此节点的距离；另 一种定义是整条路径（包括被估价过的 节点）的长度或难度。
用符号f来标记估价函数，用f(n) 表示节点n的估价函数值。
启发式搜索（续）
3、有序搜索
用估价函数f来排列OPEN表上的节点， 选择OPEN表上具有最小f值的节点作为 下一个要扩展的节点。这种搜索方法叫 做有序搜索或最佳优先搜索。它总是选 择最有希望的节点作为下一个要扩展的 节本思想:
首先将问题的初始状态(即状态空间图中的 初始节点)当做当前状态，选择一适当的算符 作用于当前状态，生成一组后继状态（或称后 继节点），然后检查这组后继状态中有没有目 标状态。如果有，则说明搜索成功，从初始状 态到目标状态的一系列算符即是问题的解；若 没有，则按某种控制策略从已生成的状态中 再选一个状态作为当前状态，重复上述过程， 直到目标状态出现或不再有可供操作的状态及 算符为止。
等代价搜索（续）
记号
S：起始节点。 c(i,j): 节点i到它的后继节点j的连接弧线代价。 g(i): 起始节点S到任一节点i的路径代价，在搜索
树上它也是从起始节点S到节点i的最少代价路 径上的代价。
等代价搜索（续）
等代价搜索算法
与宽度优先搜索算法区别，以g(i)的递增 顺序扩展其节点，即根据节点的代价大小对 OPEN表中的所有节点进行从小到大的排序。 （1）把起始节点S放到OPEN表中。如果此起始 节点为一目标节点，则求得一个解；否则令 g(S)=0； （2）如果OPEN表是个空表，则没有解而失败 退出；
（3）若OPEN表是空表，则问题无解，失败退出。
（4）选择OPEN表中的第一个节点，把它从 OPEN表移出，并放入CLOSED表中，将此节点 记为节点n，它是CLOSED表中节点的编号。
（5）若n为一目标节点，则有解并成功退出。问 题的解即可从图G中沿着指针从n到S这条路径 而得到。
图搜索策略（续）
盲目搜索（续）
搜索包含两层含义：一是要找到从初始事实 到问题最终答案的一条推理路线，另一是找到 的这条路线是时间和空间复杂度最小的求解路 线。
2、搜索的种类
分为盲目搜索和启发式搜索。
盲目搜索又称无信息搜索，即在搜索过程中， 只按预先规定的搜索控制策略进行搜索，而没 有任何中间信息来改变这些控制策略。即问题 本身的特性对搜索控制策略没有任何影响，这 就使搜索带有盲目性，效率不高。只用于解决 比较简单的问题。
3.1.2 宽度优先搜索