当前位置：文档之家 › 状态空间搜索解读

状态空间搜索解读

  • 格式：ppt
  • 大小：4.64 MB
  • 文档页数：81

下载文档原格式

  / 81

合集下载

人工智能之状态空间搜索.ppt

人工智能之状态空间搜索.ppt

§01 Three-S 的基本思想 Ruan Xiaogang Institute of Artificial Intelligence & Robots Beijing University of Technology
1.2 事物的特性
变化的和运动的
事物有事物的特性。 事物既有内在特性又有外在特性，内在特性通 常表现为事物固有的和本质的特征，而外在特性通 常表现为事物与环境的关系。 事物的特性是在不断地变化的，或不断地运动 的，因而，被称为动态特性。 事物特性的变化或运动必定是在一定的时间和 空间中发生的。
(问题原态的描述)
在问题求解活动中，事物的特性代表着问题的性 质，事物特性的变化意味着问题性质的变化。
因此，状态空间中状态的运动，意味着事物特性 的变化，意味着问题性质的变化。重要的是，这种运 动是可以通过对事物进行操作来控制的。
§01 Three-S 的基本思想 Ruan Xiaogang Institute of Artificial Intelligence & Robots Beijing University of Technology
1.4 状态是问题的性质
问题求解过程搜索过程
关于状态空间搜索 (Three-S)：
状态 (State)：状态空间中的点，代表问题的性质； 问题原态对应的状态称为初始状态，问题终态所对 应的状态称为目标状态。
状态空间 (State Space)：所有可能的状态的集合。
状态空间搜索 (Search in State Space)： 在状态空间 中搜寻一条由初始状态到目标状态的路径的过程， 即问题求解的过程。
2.1 Three-S 问题的形式化
定义：
状态空间搜索中的问题被定义为一个四元组：

3 状态空间搜索

3 状态空间搜索

2 3 1 8 4 7 6 5
1 2 3 8 4 7 6 5
2 3 4 1 8 7 6 5
1 2 3 7 8 4 6 5
1 2 3 8 4 7 6 5
三、深度优先搜索
1. 深度优先搜索算法
1) 把初始节点S0放入OPEN表中。 2) 如果OPEN表空表，则问题无解，退出；否则继续。
3) 把OPEN表中的第一个节点（记为节点n）移出，并放入 CLOSED表中。
S4=（2，2） S7=（3，2）
S2=（1，3）
S5=（2，3） S8=（3，3）
初始状态集合：S={S0} 目标状态集合：G={S8} • 定义一组算符F：A（i, j) B(i, j)
共12个：A（1，2） A（1，3） A（2，1）
A（2，3） A（3，1） A（3，2）
三、求解过程 将适用的算符作用于初始状态，以产生新的状态；然后把 另一些使用的算符作用于新的状态；继续下去，直到产生目标 状态为止。
五、代价树的宽度优先搜索 1.代价树：有向边上标有代价的搜索树。 C（i, j)：节点i 到其后继节点j的连线代价
g(x)：初始节点S0到节点x的路径代价
则 g（j）=g（i ）+ C（i, j) 2.代价树的宽度优先搜索算法 1) 把初始节点S0放入OPEN表中，令g（S0）=0。
2) 如果OPEN表空表，则问题无解，退出；否则继续。
2. 建立CLOSED表，且置为空表。 3. 判断OPEN表是否为空，若为空，则问题无解，退出。
4. 选择OPEN表中的第一个节点，把它从OPEN表中移出并放入 CLOSED表中，将此节点记为节点n。
5. 考察节点n是否为目标节点，若是，则问题有解，并成功退出。 问题的解即可从图G中沿着指针从n到S0的这条路径得到。 6. 扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集 合M，将M中的这些节点作为n的后继节点加入到图G中。

人工智能第六讲 状态空间搜索策略(1)

人工智能第六讲 状态空间搜索策略(1)
宽度优先搜索 深度优先搜索 特点
◼ 搜索过程中不使用与问题有关的经验信息 ◼ 采用固定策略对OPEN表排序 ◼ 搜索效率低 ◼ 不适合大空间的实际问题求解
6.2.2 广度优先搜索
◼ 基本思想：
从初始节点S0开始，逐层地对节点进行扩 展并考察它是否为目标节点。在第n层的 节点没有全部扩展并考察之前，不对第n ＋1层的节点进行扩展。
CLOSE表用于存放将要扩展的节点。对一个节点的扩展是指：用所 有可适用的算符对该节点进行操作，生成一组子节点
OPEN表
状态节点 父节点
CLOSE表
编号 状态节点 父节点
搜索的一般过程
1. 把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G； 2. 检查OPEN表是否为空，若为空则问题无解，退出； 3. 把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n； 4. 考察节点n是否为目标节点。若是，则求得了问题的解，退出； 5. 扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点
5 283 164 75
6
7
8
9 10
11 12
13
83 214 765
283 714
65
23 184 765
23 184 765
28 143 765
283 145 76
283 164 76
283 164 75
14
83 214 765
15
283 714 65
16
123 84
765
17 18
234 18 765
5. 若节点n不可扩展，则转第2步。
6. 扩展节点n，将其子节点放入OPEN表的尾部， 并为每一个子节点都配置指向父节点的指针， 然后转第2步。

状态空间搜索

状态空间搜索
• 为了在最普遍的情况下（是图而不是树）定义回溯算法， 有必 要检测并删除多次出现的某些状态，以避免造成 路径循环。检测可以通过对每一个新生成的状态判断它 是否在上述3张表中来实现，如果它属于某一张表，就 说明它已被搜索过不必再考虑。
图搜索的实现（续）
• 当前正在搜索的结点叫CS，即当前状态。CS总 是等于最近加入SL中的状态，是当前正在探寻 的解题路径的“前锋”。博弈中走步用的推理 规则或者其他合适的问题求解操作都可应用于 CS，得到一些新状态，即CS的子状态的有序集， 重新视该集合中第一个状态为当前状态，其余 的按次序放入NSL中，用于以后的搜索。新的 CS加入SL中，搜索就这样继续进行。若CS没 有子状态，就要从SL，NSL中删除它，将其加 入DE，然后回溯查找NSL中的下一个状态。
图搜索的实现（续）
• 重复 CS
•0
A
•1
B
•2
E
•3
H
•4
I
•5
F
•6
J
•7
C
•8
G
SL [A] [BA] [EBA] [HEBA] [IEBA] [FBA] [JFBA] [CA] [GCA]
NSL [A] [BCDA] [EFBCDA] [HIEFBCDA] [IEFBCDA] [FBCDA] [JFBCDA] [CDA] [GCDA]
状态空间的一般搜索过程
• 一个节点经一个算符操作后一般只生成一个子 节点，但适用于一个节点的算符可能有多个， 此时就会生成一组子节点．在这些子节点中可 能有些是当前扩展节点(即节点n)的父节点，祖 父节点等，此时不能把这些先辈节点作为当前 扩展节点的子节点．余下的子节点记作集合Ｍ， 并加入图Ｇ中．
•
•

人工智能之状态空间搜索

人工智能之状态空间搜索

操作称为合法操作，否则称为非法操作。
可行的操作称为合法操作。 不可行的操作称为非法操作。
§02 Three-S 问题的描述
2.3 Three-S 问题描述示例
Ruan Xiaogang Institute of Artificial Intelligence & Robots Beijing University of Technology
§02 Three-S 问题的描述
2.3 Three-S 问题描述示例
Ruan Xiaogang Institute of Artificial Intelligence & Robots Beijing University of Technology
八数码问题：
状态 (State) 状态的编码或表达方法：
§01 Three-S 的基本思想
1.1 所谓状态空间搜索：
Ruan Xiaogang Institute of Artificial Intelligence & Robots Beijing University of Technology
机器的一种思维方式
模拟人的问题球解过程，模拟人的思维或逻辑推 理，是人工智能，特别是符号计算学的重要任务。 人工智能的问题求解方法，是人的思维和逻辑推 理的形式化，是机器或计算机的思维和逻辑推理。 状态空间搜索 (The Search in State Spaces, Three-S)
§02 Three-S 问题的描述
2.3 Three-S 问题描述示例
Ruan Xiaogang Institute of Artificial Intelligence & Robots Beijing University of Technology

状态空间的搜索策略

状态空间的搜索策略

状态空间的搜索策略图1 状态空间的搜索策略一般说来，搜索策略讨论对于具有树状结构图的问题状态空间更加方便。

因此，对于非树状结构图的问题，例如网状结构等，往往需要化为树状结构图，以便更好地应用搜索策略进行讨论。

（1）广度优先搜索——先进先出，生成的节点插入OPEN表的后面。

基本方法：从根节点S0开始，向下逐层逐个地对节点进行扩展与穷尽搜索，并逐层逐个地考察所搜索节点是否满足目标节点Sg的条件。

若到达目标节点Sg，则搜索成功，搜索过程可以终止。

注意：在广度优先搜索法的过程中，同一层的节点搜索次序可以任意；但在第n层的节点没有全部扩展并考察之前，不应对第n+1层的节点进行扩展和考察。

特点：显然，宽度优先搜索法是一种遵循规则的盲目性搜索，它遍访了目标节点前的每一层次每一个节点，即检查了目标节点前的全部的状态空间点，只要问题有解，它就能最终找到解，且最先得到的将是最小深度的解。

可见，宽度优先搜索法很可靠。

但是，当目标节点距离初始节点较远时将会产生许多无用的中间节点。

因此，速度慢，效率低，尤其对于庞大的状态空间实用价值差。

（2）深度优先搜索——后进先出，生成的节点插入OPEN表的前面。

基本方法：从根节点S0开始，始终沿着纵深方向搜索，总是在其后继子节点中选择一节点来考察。

若到达目标节点Sg，则搜索成功；若不是目标节点，则再在该节点的后继子节点中选一考察，一直如此向下搜索，直到搜索找到目标节点才停下来。

若到达某个子节点时，发现该节点既不是目标节点又不能继续扩展，就选择其兄弟节点再进行考察。

依此类推，直到找到目标节点或全部节点考察完毕，搜索过程才可以终止或结束。

特点：方式灵活，规则易于实现，对于有限状态空间并有解时，必能找到解。

例如，当搜索到某个分支时，若目标节点恰好在此分支上，则可较快地得到解。

故在一定条件下，可实现较高求解效率。

但是，在深度优先搜索中，一旦搜索进入某个分支，就将沿着该分支一直向下搜索。

这时，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。

第五章状态空间搜索策略

第五章状态空间搜索策略

• CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。
•
状态空间的一般搜索算法
一般搜索算法的描述：
① 建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中
② 建立CLOSED表，且置为空表
③ 判断OPEN表是否为空表，若为空，则问题无解，退出
④ 选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节 点记为节点n
•((1,1) (2,4) (3.2))
•((1,2) (2,4) (3,1))
•((1,2) (2,4) (3,1) (4,3))
•
5.1 搜索的概念及种类
5.2 盲目搜索 5.3 启发式搜索
•5.2.1 状态空间图的一般搜索算法 •5.2.2 宽度优先搜索策略 •5.2.3 深度优先搜索策略 •5.2.4 代价树的宽度优先搜索策略
•
•Q •( )
•((1,1))
•((1,2))
•((1,1) (2,3)) •((1,1) (2,4))
•((1,1) (2,4) (3.2))
•
•( ) •((1,1))
•((1,2))
•Q •Q
•((1,1) (2,3)) •((1,1) (2,4)) •((1,2) (2,4)) •((1,1) (2,4) (3.2))
•
搜索例子：回溯搜索算法
BACKTRACK（DATA）
• DATA：当前状态。 • 返回值：
– 成功：返回从当前状态到目标状态的 路径（以规则表的形式表示）
• 失败：返回FAIL。
•
四皇后问题
• 皇后问题 – 在一个4*4的国际象棋棋盘上，一次一个地摆布四

02第二讲(状态空间搜索策略)

02第二讲(状态空间搜索策略)


引子：问题求解
3X+5=14， X=？
60 ° 40° ？

引子：问题求解

引子
◦ 人能够采用试探的搜索方法求解很多问题 ◦ 人工智能也可以利用搜索来求解问题 在可能的解空间内寻找一个解
状态
2.1.1 问题状态描述

定义：状态（State）
◦ 为描述某类不同事物间的差别，引入一组最少
变量 q0，q1，…，qn 的有序集合，记作Q
起始节点 S L M F P O Q
N
A
B
C
2、深度优先搜索过程
S L M N A F P B O Q C M N A L F P B S O Q C
3、最大深度约束
◦ 优先扩展最深的节点，使得搜索沿着状态 空间某条单一的路径从起始节点向下进行 下去；只有当搜索到达一个没有后续的状 态时，它才考虑另一条替代的路径。 ◦ 为了防止搜索过程沿着无益的路径扩展下 去，往往给出一个节点扩展的最大深度约 束。超过这个深度约束时不再产生后继。
目标
11
2 8 3 1 6 4 7 5
12
8 3 2 1 4 7 6 5
13
2 8 3 7 1 4 6 5
14 2 8 1 4 3 7 6 5
3、性质
◦ 当问题有解时，一定能找到解 ◦ 方法与问题无关，具有通用性
◦ 效率较低
2.1 问题的状态和状态空间 2.2 盲目搜索方法 2.3 启发式搜索策略 2.4 通用图搜索算法 2.5 启发式图搜索算法
内容回顾
内容提要：
1.1 什么是人工智能 1.2 人工智能的发展历史 1.3 人工智能研究的方法 1.4 人工智能研究的课题
国际象棋人机大战

第一章第一讲--状态空间与图搜索

第一章第一讲--状态空间与图搜索
A B A B
1
《人工智能》
2 S0
3
1
2 Sg
3
猴子摘香蕉问题
c
a
《人工智能》
b
状态：(w,t,x,y,z) w:猴子的水平位置 {a,b,c}
初始状态：(c,a,b,0,0) 目标状态：(a,a,a,1,1)
t:天花板上香蕉对应的地面位置 {a,b,c}
x:箱子的水平位置 y:猴子是否在箱子上 z:猴子是否拿到香蕉 操作符： Goto(u):猴子走到u处 Push(v):猴子推箱到v处 {a,b,c} {0,1} {0,1}
《人工智能》
状态空间表示法
状态：描述问题求解中任一时刻的状况；变量的有序组合 算符：一个状态→另一状态的操作
状态空间：所有求解路径构成的图；{状态，算符} 表示
问题求解过程：
初始状态：描述问题求解中的初始状况 算符(规则应用）：一个状态→另一状态的操作 目标测试：确定给定的状态是否为目标状态
（3）除根结点外的其余数据元素被分为m（m≥0）个互不相
交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m） 本身也是一棵树，被称作原树的子树（subtree）。
《人工智能》
树节点深度： 根节点深度=0 其它节点深度=父节点深度+1
0 1 2 3
《人工智能》
路径的代价（耗散值）
《人工智能》
1.2 图搜索算法：一般框架
保留全部搜索路径，便于信息利用； 根据可用算符集合（相当于回溯搜索算法中 的规则集合）扩展当前节点（状态）的全部 （可能）子节点（即生成新状态） 引入open表和closed 表，对搜索过程进行控 制，实现不同方式的搜索策略（包括回溯） 从隐含的状态空间图中产生包含解路径的显 式搜索子图（产生的搜索图越小、搜索效率 越高）

状态空间搜索策略

状态空间搜索策略

开始
把S放入OPEN表
OPEN表为空表？
是 失败
否
把第一个节点(n)从OPEN表移至CLOSED表
n为目标节点吗？
是 成功
否
把n的后继节点放入OPEN表的末端， 提供返回节点n的指针
修改指针方向 重排OPEN表
图3.1 图搜索过程框图
3.2 盲目搜索
• 特点：不需重排OPEN表 • 种类：宽度优先、深度优先、等代价搜索等。
03
虽然问题求解可通过搜索方法， 也可用逻辑推理，但二者的侧 重点是不一样的。前者着重于 寻求问题解答的过程，而后者 强调前提（初始）问题空间 （公理集合）与问题解答间连 接的逻辑正确性。或者简单地 讲，搜索着重于发现 （Discovery），而推理强调证 明（Proof）。
搜索
在状态图中寻找目标或路径的基本方法 从初始节点，沿着与之相连的边，寻找目标节点的过程
过多无用节点。 ○ 用于删除节点的选择,即用于决定应删除哪些无用节点, 以免造成进一
步的时空浪费。
3.3 启发式搜索
3.3.1 启发式搜索策略和估价函数
特点：重排OPEN表，选择 最有希望的节点加以扩展
1
种类：有序搜索、A*算法 等
○ 盲目搜索可能带来 组合爆炸
○ 启发式信息 用来加速搜索过程 的有关问题领域的 特征信息。
3.2.1 宽度优先搜索
❖ 定义
以接近起始节点的程度逐必能 找❖ 到算法它。
广度（宽度）优先搜索 (Breadth-first search, BFS)
○ 优先在同一级节点中考察，只有当同一级节点考察完毕之后，才考 察下一级节点
○ 自顶向下一层一层逐渐生成的
75
10
11

《状态空间搜索》课件

《状态空间搜索》课件

应用领域
人工智能
状态空间搜索可以应 用于机器学习、自然 语言处理和图像识别 等人工智能领域。
游戏设计
状态空间搜索是游戏 中人物行动和决策的 基础，使游戏更具挑 战性和智能性。
自动规划和调 度
在生产、物流和交通 等领域中，状态空间 搜索可以优化资源规 划和任务调度。
数据分析
状态空间搜索可以帮 助发现数据中隐藏的 模式和关联，为决策 制定提供有力支持。
案例研究
人工智能
使用状态空间搜索优化机器学习 算法的参数选择，提高准确性和 效率。
游戏设计
通过状态空间搜索实现游戏中的 智能NPC行为，使游戏更具挑战 性。
自动规划和调度
利用状态空间搜索优化物流系统 的路径规划和车辆调度，降低成 本和提高效率。
《状态空间搜索。通过定义和搜索问题的 状态空间，我们能够找到最佳解决方案，并解决各种实际挑战。
定义与背景
状态空间搜索是一种以状态和操作为基础的搜索算法。它可用于查找特定问题的解决方案，并在搜索空间中找 到最佳路径。 状态空间搜索在人工智能、游戏设计、自动规划和调度以及数据分析等领域都有广泛的应用。
挑战和解决方案
1 空间复杂度
随着状态空间的增大，搜索算法需要占用更多的内存。优化技术和剪枝策略可以减少空 间需求。
2 时间复杂度
在大规模状态空间中搜索最优解需要花费较长的时间。智能的启发式函数可以提高搜索 效率。
3 剪枝技术和优化策略
通过剪掉冗余的搜索路径和使用启发式函数进行优化，可以加速状态空间搜索。
常见的搜索算法
盲目搜索算法
通过无信息的搜索策略，在状态空间中逐步探 索并找到解决方案。
最佳优先搜索算法
根据启发式函数评估搜索节点，并选择评估函 数值最小的节点进行扩展。

状态空间搜索实验报告

状态空间搜索实验报告

一、实验目的1. 理解状态空间搜索的基本概念和原理。

2. 掌握状态空间搜索方法在解决问题中的应用。

3. 比较不同搜索算法的优缺点，提高搜索效率。

二、实验内容本次实验主要涉及以下内容：1. 状态空间搜索的基本概念和原理。

2. 常用搜索算法：深度优先搜索（DFS）、广度优先搜索（BFS）、A搜索算法。

3. 状态空间搜索在解决实际问题时（如八数码问题、十五数码难题）的应用。

三、实验步骤1. 理解状态空间搜索的基本概念和原理。

状态空间搜索是一种求解问题的方法，将问题求解过程表示为从初始状态到目标状态的搜索过程。

状态空间搜索主要包括以下几个步骤：（1）确定问题的初始状态；（2）确定问题的目标状态；（3）定义状态空间，包括所有可能的状态和状态之间的转换关系；（4）确定搜索策略，选择合适的搜索算法。

2. 学习并实现常用搜索算法。

（1）深度优先搜索（DFS）：按照一定的顺序前查找完一个分支，再查找另一个分支，直至找到目标状态。

（2）广度优先搜索（BFS）：从初始状态一层一层向下搜索，直至找到目标状态。

（3）A搜索算法：结合启发式信息和代价函数，在搜索过程中优先考虑估计距离目标状态较近的状态。

3. 应用状态空间搜索解决实际问题。

以八数码问题为例，实现以下步骤：（1）定义问题状态：将8个数码排成一行，空白格用0表示。

（2）确定操作符集合：包括上下左右四个方向移动空白格。

（3）建立状态空间：根据初始状态，通过操作符集合生成所有可能的状态。

（4）选择搜索算法：实现DFS、BFS和A搜索算法，分别求解八数码问题。

4. 比较不同搜索算法的优缺点。

通过实验结果，分析DFS、BFS和A搜索算法在解决八数码问题时的搜索效率、空间复杂度和时间复杂度。

四、实验结果与分析1. 八数码问题的初始状态和目标状态如下：初始状态：1 2 3 4 5 6 7 8 0目标状态：0 1 2 3 4 5 6 7 82. 实验结果如下：（1）深度优先搜索（DFS）：- 找到目标状态的搜索路径：10步- 空间复杂度：递归调用栈的深度，约为8层- 时间复杂度：由于DFS搜索过程可能遍历大量无效路径，因此时间复杂度较高（2）广度优先搜索（BFS）：- 找到目标状态的搜索路径：31步- 空间复杂度：队列的长度，约为31层- 时间复杂度：BFS搜索过程较为平稳，时间复杂度相对较低（3）A搜索算法：- 找到目标状态的搜索路径：15步- 空间复杂度：约为15层- 时间复杂度：由于A搜索算法结合了启发式信息，因此时间复杂度相对较低3. 分析：（1）DFS搜索过程可能遍历大量无效路径，导致搜索效率较低。

状态空间搜索策略

状态空间搜索策略

希望：
• 引入启发知识;在保证找到最佳解的前提下;尽可能减 少搜索范围;提高搜索效率
• 搜索算法的效果： – 可以用启发能力的强弱来度量 – 考虑解路径的消耗值和求得路径所需搜索的消耗 值两者的某种组合最小 – 考虑搜索方法对求解所有可能遇见的问题;其平均 的组合消耗最小
问题的关键
• 如何寻找最有希望的节点 – 启发搜索过程中;要对OPEN表进行排 序;这就需要有一种方法来计算待扩展 节点有希望通向目标节点的不同程度 – 我们总希望能找到最有希望通向目标 节点的待扩展节点优先扩展
123 784
65
12 3 84 7 65
283 64
175
283 16 754
83 214 765
283 714 65
28 143 765
283 145 76
目标
深度优先搜索的性质
• 一般不能保证找到最优解 • 当深度限制不合理时;可能找不到解 • 最坏情况时;搜索空间等同于穷举
5 2 4 代价树的宽度优先搜索
基本思想
• 定义一个估价函数fEvaluation Function;对当前的 搜索状态进行评估;找出一个最有希望的节点来扩 展
• 估价函数的格式：
fn = gn + hn
fn：估价函数 gn：代价函数;
初始节点到节点n已实际付出的代价 hn：启发函数;
从节点n到目标节点的最优路径的估计代价
5 3 2 最佳优先搜索
否则转向第2步
5 2 2 宽度优先搜索策略
例：把宽度优先搜索应用于八数码难题时所生成的搜索树;这个问 题就是要把初始棋局变为如下目标棋局的问题：
123 84 765
5
283 164 75

第四章状态空间搜索

第四章状态空间搜索

初始状态：任何状态都可以被指定为初始状态。注意要到 达任何一个给定的目标，可能的初始状态中恰好只有一半 可以作为开始。
后继函数：用来产生通过四个行动（把空位向Left，Right ，Up或Down移动）能够达到的合法状态。
目标测试：用来检测状态是否能匹配所要求的目标格局。
路径耗散：每一步的耗散值为1，因此整个路径的耗散值为 路径中的步数。
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
4
4.2 问题实例
1. 二阶梵塔问题 2. 设有三根钢针，它们的编号分别是1号、2号和3号。在初
始情况下，1号钢针上穿有A、B两个金片，A比B小，A 位于B的上面。要求把这两个金片全部移到另一根钢针 上，而且规定每次只能移动一个金片，任何时刻都不能 使大的位于小的上面。
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
4.1 用搜索法对问题求解
一个问题可以形式化地定义为四个组成部分： 初始状态 可能行动的描述 目标测试 路径耗散 问题的解就是从初始状态到目标状态的路径
14
4. 八皇后问题
*
* *
* *
*
* *
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
15

第五章状态空间的各种搜索

第五章状态空间的各种搜索

四.等代价搜索 等代价搜索
分析：城市间旅费=节点间代价，制约条件是代价最小，先扩展代 价最小的节点。如从A->B->E， cost(B)=7,cost(E)=cost(B)+m(B,E)=7+12=19.设计以A为起点， 用等代价搜索得出部分搜索树，连线上数字为从父节点到子节点 的代价.节点上方小圆圈内数字为节点扩展顺序，方框左上方为 从A到该节点总代价.
例：图中各点间连线表示从一处到另一处所消耗的费 用，试编一程序求任意两地之间的最小费用(代价最小) 的路线，并打印所付出费用.
六.分枝限界法 分枝限界法
设求从v1->v5所付出代价最小路径 设变量s=从始点到某点总代价 (1)第一步扩展v1获得第一级子节点: v1->v2:2 v1->v3:4 V1->v4:5
五.A*算法 算法
例：炸迷宫问题 有一个N*N迷宫，每一格或是空，或者是实，如果 有一人位于迷宫的一空格(x,y)中，则他仅能到达相邻 的空格(指上下左右).现有一人从(1,1)始点出发，目 标是(N,N)，他随身带着K个炸弹(0<=K<=N)，一个炸弹 的威力能把与他相邻的一个实格炸成空格. 编一程序，求出R个被炸实格位置(0<=R<=K)和 此人从起始点到目标的路径，并要求R满足条件中的最 小值. 要求：
第五章 状态空间的各种搜索
一.概述 概述
广度优先搜索法：以接近起始节点的程度依次 广度优先搜索法 扩展节点，即对下一层节点搜索前，必须先搜 索完本层所有节点 深度优先搜索法：首先扩展最新产生的节点， 深度优先搜索法 每层只对一个节点进行扩展，除非搜索失败或 已达到预先约定的最大深度，才会退回去搜索 原来忽略节点
三.深度优先搜索 深度优先搜索

图搜索-状态空间表示

图搜索-状态空间表示

4）一般图搜索例——八数码游戏
制定操作算子集： * 直观方法——为每个棋牌制定一套可能的走步： 左、上、右、下四种移动， 这样就需32个操作算子。 * 简易方法——仅为空格制定这4种走步， 因为只有紧靠空格的棋牌才能移动。 * 空格移动的唯一约束是不能移出棋盘。
八数码问题的搜索图： 参见图2.3 棋盘布局（问题状态）总共9!=362880个， 但搜索图小得多。
用一般图搜索方法解决该问题：
为问题状态的表示建立数据结构：3×3的一个矩阵， * 矩阵元素S ij∈{0,1,…,8}；其中1≤i,j≤3， * 数字0指示空格， * 数字1 - 8指示相应棋牌。 1 0 3 图2.2中的八数码问题就可表示为： 7 2 4 6 8 5

1 2 3 8 0 4 7 6 5
渡河问题就有无数条解答路径（因为划船操作可逆），但只有4条是最短的，都包含11 个也称一般图
操作算子的可选（渡河问题的初始状态节点就有 3 个），在逻辑上称为“或”关系，意 指只要其中有一条路径通往目标状态，就能获得成功解答。除了少数像渡河这样的简单 问题外，描述状态空间的一般图都很大，无法直观地画出，只能将其视为隐含图。
2类操作算子：
2）状态空间表示的经典例——传教士和野人问题
渡河问题状态空间的有向图： 参见图2.1
1 状态空间及其搜索的表示
3）状态空间的搜索 状态空间的搜索以SE指示，其可表示为1个五元组：
SE = (S,O,E,I,G) I——问题的初始状态，I ∈ S; E——搜索引擎； G——问题的目标状态集，G S。
特例：N=3，K=2；
变量m——传教士在左岸或船上的实际人数， 变量c——野人在左岸或船上的实际人数， 变量b——指示船是否在左岸（1、0）。 上述约束条件转变为m + c ≦2, m ≧ c。 左岸状态描述为一个三元组： （m, c, b）
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
问题实例——八数码问题
状态：8个棋子在3×3 的棋盘上的任意一个 摆放 初始状态：右上图 算子（后继函数）： left、right、up、down 目标函数：右下图 路径代价：1
计算机与信息学院 刘勇
1 2 7 5 8 3 4 6
初始状态
1 2 3 4 5 6 7 8
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
深度优先搜索
open
1 2 3 4 5 6 7 8 9 10 A B,F C,D,E,F D,E,F E,F F G,I H,I I
close
A A,B A,B,C A,B,C,D A,B,C,D,E A,B,C,D,E,F A,B,C,D,E,F,G A,B,C,D,E,F,G,H A,B,C,D,E,F,G,H,I
最
优
化
理
论
与
应
用
B1 广度优先搜索
breadth-first search，BFS A B F C D E G I
A B C D E G H F I
先扩展出的节 点先被考察
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
广度优先搜索算法
1. 初始化open表、close表为空，定义S为初始状态 结点 2. 将S放入到open表中 3. 如果open表为空，则搜索失败，否则从open表中 取出第一个结点N,将N放入到close表中。 4. 如果N是目标结点，搜索成功，返回N 5. 对N的每一个子结点 i，如果open表和close表中 都没有结点i，那么将结点i其追加到open表的最 后一个元素之后 6. goto 3
可把状态空间记为三元状态(S，F，G)。
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
2、状态空间的搜索策略
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
3. 状态空间的一般搜索过程
对一个确定的具体问题来说，与解题有关的状态空 间往往只是整个状态空间的一部分，因此只要能生成并 存储这部分状态空间就可求得问题的解。 人工智能采用的基本思想：首先把问题的初始状态( 即初始节点)作为当前状态，选择适用的算符对其进行 操作，生成一组子状态(或称后继状态、后继节点、于 节点)，然后检查目标状态是否在其中出现。若出现， 则搜索成功，找到了问题的解；若不出现，则按某种搜 索策略从已生成的状态中再选一个状态作为当前状态。 重复上述过程，直到目标状态出现或者不再有可供操作 的状态及算符时为止。
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
3、基于搜索的问题求解模式
问题的形式化：将环境状态简化为适于问题求解 的状态，用状态空间图描述问题。
给出初始状态 设计算子：对动作建模 目标函数：目标的形式化 给出路径代价函数
求解过程：在状态空间图中找到一条从初始结点 到达目标的路径。这条路径上的所有边对应算子 组成的序列，就是解决问题的一个方案 关键技术：搜索
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
B2 深度优先搜索（depth-first search）
A B C D E F G H I
A B C D E G H F I
新扩展出的节 点先被考察
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
深度优先搜索算法
1. 初始化open表、close表为空，定义S为初始状态 结点 2. 将S 放入open表中 3. 如果open表为空，则搜索失败，否则从open表中 取出第一个结点N，将N放入close表中 4. 如果N是目标结点，搜索成功，返回N 5. 对N的每一个子结点 i，如果open表和close表中 都没有结点i，那么将结点i其插入到open表的第 一个元素之前 6. goto 3
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
广度优先搜索
open
1 2 A B,F
close
A
A B C D E G H F I
3 4 5 6 7 8 9
F,C,D,E C,D,E,G,I D,E,G,I E,G,I G,I I,H H
A,B A,B,F A,B,F,C A,B,F,C,D A,B,F,C,D,E A,B,F,C,D,E,G A,B,F,C,D,E,G,I
目标状态
最
优
化
理
论
与
应
用
1 2 7 5 8 3 4 6
right up left
1 2 7 5 8 3 4 6
up left
1 2 7 5 3 4 8 6
right up down left
1 2 7 5 8 3 4 6
right up
……
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
二. 状态搜索法
1、状态（State）的基本概念
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
2、搜索的定义和分类？
定义：根据问题的实际情况不断寻找可利用的知识， 从而构造一条代价较少的推理路线，使问题得到圆满 解决的过程称为搜索。 分类：盲目搜索和启发式搜索。
盲目搜索是按预定的控制策略进行搜索，在搜索过程中获 得的中间信息不用来改进控制策略。效率不高，不便于复杂问 题的求解。 启发式搜索是在搜索中加入了与问题有关的启发性信息， 用以指导搜索朝着最有希望的方向前进，加速问题的求解过程 并找到最优解。
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
4. 状态空间搜索数据结构表示
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
5. 状态空间搜索一般过程
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
计算机与信息学院 刘勇
ห้องสมุดไป่ตู้
最
优
化
理
论
与
应
用
6. 常用搜索方法 （盲目Blindfold＋启发式Heuristic）
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
常用搜索策略
基础知识 状态空间搜索法 与或树搜索法 博弈树搜索法
随机搜索－遗传算法
分析与讨论
计算机与信息学院 刘勇
最
优
化
理
论
与
应
用
一. 基础知识
1、为何要搜索？
人工智能所要解决的问题大部分是结构不良或非 结构化的问题，对这样的问题一般不存在成熟的算法 可供利用，而只能是利用已有的知识一步丛地摸索着 前进。如何确定推理路线，使其付出的代价尽可能的 少，而问题又能得到较好的解决? 在人工智能中，即使对结构性能较好，理论上有 算法可依的问题，由于问题本身的复杂性以及计算机 在时间、空间上的局限性，也需要通过搜索来求解。