sch2补充.pdf

算法设计与分析 算法设计与分析 算法设计与分析 Design and Analysis of Algorithms Design and Analysis of Algorithms Design and Analysis of Algorithms 主讲人 徐 云 主讲人 徐 云 Fall 2010, USTC Fall 2010, USTC 第2章(补充) 回溯法 第2章(补充) 回溯法 2.1 方法概述 2.1 方法概述 2.2 树和图的遍历 2.2 树和图的遍历 2.3 n后问题 2.3 n后问题 2.4 排列生成问题 2.4 排列生成问题 2.5 TSP 问题 2.5 TSP 问题 2.6 0-1 背包 2.6 0-1 背包 2.1 方法概述 有哪些信誉好的足球投注网站算法介绍 回溯算法 相关术语 回溯算法的基本步骤 实例分析 2010-10-13 算法设计与分析 3 有哪些信誉好的足球投注网站算法介绍 （1） 有哪些信誉好的足球投注网站算法 (1)穷举有哪些信誉好的足球投注网站(Exhaustive Search) Exhaustive Search (2)盲目有哪些信誉好的足球投注网站(Blind or Brute-Force Search) Blind or Brute-Force Search - 深度优先(DFS) 或回溯有哪些信誉好的足球投注网站(Backtracking); DFS Backtracking - 广度优先有哪些信誉好的足球投注网站(BFS); BFS - 迭代加深有哪些信誉好的足球投注网站(Iterative Deepening); Iterative Deepening - 分枝限界法(Branch Bound); Branch Bound - 博弈树有哪些信誉好的足球投注网站(α-βSearch) α-βSearch (3)启发式有哪些信誉好的足球投注网站(Heuristic Search) Heuristic Search - A*算法和最佳优先(Best-First Search) Best-First Search - 迭代加深的A*算法 - B*,AO*,SSS*等算法 - Local Search, GA等算法 2010-10-13 算法设计与分析 4 有哪些信誉好的足球投注网站算法介绍 （2） 有哪些信誉好的足球投注网站空间的三种表示 - 表序表示: 有哪些信誉好的足球投注网站对象用线性表数据结构表示; - 显式图表示: 有哪些信誉好的足球投注网站对象在有哪些信誉好的足球投注网站前就用图(树) 的数 据结构表示; - 隐式图表示: 除了初始结点, 其他结点在有哪些信誉好的足球投注网站过 程中动态生成. 缘于有哪些信誉好的足球投注网站空间大, 难以全部存储. 2010-10-13 算法设计与分析 5 有哪些信誉好的足球投注网站算法介绍 （3） 提高有哪些信誉好的足球投注网站效率的思考：随机有哪些信誉好的足球投注网站 - 上世纪70 年代中期开始, 国外一些学者致力于 研究随机有哪些信誉好的足球投注网站求解困难的组合问题, 将随机过程 引入有哪些信誉好的足球投注网站;