第三讲搜索与求解 周文晖 杭州电子科技大学
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 第三讲 搜索与求解 周文晖 杭州电子科技大学
什么是状态图？ 状态图搜索 树式搜索，线式搜索，广度优先搜索、深度优先搜索、启发式搜索… 加权状态图？ 什么是加权状态图？ 代价函数、启发函数、A/A*算法 如何构建状态图？ 如何构建状态图？ 个 状态图表示、规则转换 与或图搜索 与或图搜素 与图、或图、解树 博弈树 博弈树 极大极小分析、剪枝 Hangzhou Dianzi University杭州电子科技大学 Schoof of Computer Science and Tecfmnology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 状态图搜索 与或图搜索 加权状态图？ 如何构建状态图？ 博弈树 什么是状态图？ 树式搜索，线式搜索，广度优先搜索、深度优先搜索、启发式搜索 … 什么是加权状态图？ 代价函数、启发函数、A／A＊算法 如何构建状态图？ 与或图搜素 与图、或图、解树… 博弈树 ？ 极大极小分析、剪枝 状态图表示、规则转换
什么是状态图？ 状态图搜索 树式搜索，线式搜索，广度优先搜索、深度优先搜索、启发式搜索… 加权状态图？ 什么是加权状态图？ 代价函数、启发函数、A/A*算法 如何构建状态图？ 如何构建状态图？ 个 状态图表示、规则转换 与或图搜索 与或图搜素 与图、或图、解树 博弈树 博弈树 极大极小分析、剪枝 Hangzhou Dianzi University杭州电子科技大学 Schoof of Computer Science and Tecfmnology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 状态图搜索 与或图搜索 加权状态图？ 如何构建状态图？ 博弈树 什么是状态图？ 树式搜索，线式搜索，广度优先搜索、深度优先搜索、启发式搜索 … 什么是加权状态图？ 代价函数、启发函数、A／A＊算法 如何构建状态图？ 与或图搜素 与图、或图、解树… 博弈树 ？ 极大极小分析、剪枝 状态图表示、规则转换
3.1状态图搜索 实际问题求解与图搜索间联系？ ·状态图是实际问题求解的数学模型。 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 3.1 状态图搜索 实际问题求解与图搜索间联系？ • 状态图是实际问题求解的数学模型
问题求解：迷宫问题 S1T S2T S3 从起点S。>终点Sg 如何寻找最短路径？ S5 S6 路径搜索过程 S8LS9☐T Sg Hangzhou Dianzi University杭州电子科技大学 Schoofo时Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 问题求解：迷宫问题 从起点So ‐> 终点Sg. 如何寻找最短路径？ 路径搜索过程
问题提出和模型建立 问题提出 2T S3 •盲目搜索？按某种顺序搜索？ •如何判断是否得到最短路径？ S4 S5 S6 0 模型建立 •图模型的建立 S7 S8 S9■ Sg ·每个格子及入口和出口都作为节点 •通道作为边 •构成有向图 Hangzhou Dianzi University杭州电子科技大学 Schoofo时Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 问题提出和模型建立 问题提出 •盲目搜索？按某种顺序搜索？ •如何判断是否得到最短路径？ 模型建立 •图模型的建立 •每个格子及入口和出口都作为节点 •通道作为边 •构成有向图
有向图模型 S S 迷宫可用有向图表示。 走迷宫变为从有向图的初始节点（入口）出 发，寻找通向目标节点（出口）的路径问题。 西安电子科 S1一S2一S3 登其发应 S称为源，S称为汇，是图中的两个特殊 6套电多份 学女税自 西买电子背发大堂其夜阻 的节点。 S。S4- S5一 S6 S1 Sg Hang2 hou Dian2 iUniversity杭州电子科技大学 Schoof of Computer Science and Tecfmology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 有向图模型 迷宫可用有向图表示。 走迷宫变为从有向图的初始节点(入口)出 发, 寻找通向目标节点(出口)的路径问题。 So称为源，Sg称为汇，是图中的两个特殊 的节点
八数码问题/华容道/拼图 赵云 问题描述： 黄忠 曹操 ·在一个3×3的方格棋盘上放置着1,2,3,4,5,6,7， 8八个数码，每个数码占一格，且有一个空格。 马超 •从初始棋局到目标棋局 张飞 2 8 3 8 1 3 1 4 2 大受 4 关羽 6 5 7 6 5 黄刀立 初始棋局 目标棋局 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 八数码问题/华容道/拼图 问题描述： •在一个3×3的方格棋盘上放置着1, 2, 3, 4, 5, 6, 7, 8八个数码, 每个数码占一格, 且有一个空格。 •从初始棋局到目标棋局
拓扑图模型 技巧：逆向思维，棋子移动等效于空格移动 图中的一条边（即相邻两个节点的连线）对应一次移动。 一次移动也对应着图中的一条边。 但移动是按规则进行的。 所以图中的一条边也代表了一个移动规则或移动规则的一次执行。 八数码问题也就是要在该拓扑图中寻找目标节点，或找一条从初始节 点到目标节点的路径问题。 Hangzhou Dianzi University杭州电子科技大学 Schoolo时Computer Science and Tecfmnology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 拓扑图模型 技巧：逆向思维，棋子移动等效于空格移动 图中的一条边(即相邻两个节点的连线) 对应一次移动。 一次移动也对应着图中的一条边。 但移动是按规则进行的。 所以图中的一条边也代表了一个移动规则或移动规则的一次执行。 八数码问题也就是要在该拓扑图中寻找目标节点, 或找一条从初始节 点到目标节点的路径问题
状态图搜索方法 问题求解转换为状态图搜索过程。 搜索的效率（速度和准确性）是关键。 两种搜索方法 •树式搜索 •线式搜索 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and1 ecfmology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 状态图搜索方法 问题求解转换为状态图搜索过程。 搜索的效率（速度和准确性）是关键。 两种搜索方法 •树式搜索 •线式搜索