第三讲搜索与求解 周文晖 杭州电子科技大学
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. 如何寻找最短路径？ 路径搜索过程