数据结构:链表结构、基于BIN的结构、 邻接指针、角勾链、四叉树、二叉排序 树、邻接矩阵、关联矩阵 版图数据的基本操作:点查找、邻接查 找、区域搜索、定向区域遍历、模块插 入、模块删除、推移、压缩、建立通道 2021/2/21
2021/2/21 11 • 数据结构：链表结构、基于BIN的结构、 邻接指针、角勾链、四叉树、二叉排序 树、邻接矩阵、关联矩阵。 • 版图数据的基本操作：点查找、邻接查 找、区域搜索、定向区域遍历、模块插 入、模块删除、推移、压缩、建立通道
算法及算法复杂性 处理对象是亿量级数量的图形。哪怕是 二次方量级的算法时间都可能是无法实 现的 1、要解决的算法问题: 算法复杂性、最优化问题、可行解问题、 NP问题 2021/2/21 12
2021/2/21 12 二、算法及算法复杂性 处理对象是亿量级数量的图形。哪怕是 二次方量级的算法时间都可能是无法实 现的。 1、要解决的算法问题： 算法复杂性、最优化问题、可行解问题、 NP问题
2、一些图论中问题的复杂性 判别平面性O(n) 最小生成树O(n2) 最短路(从一点到所有点)O(n2) 所有节点间的最短路O(n3) 平面化:NP 着色:NP 最长路:NP 斯坦纳树:NP 旅行商问题:NP 2021/2/21
2021/2/21 13 2、一些图论中问题的复杂性 判别平面性O（n） 最小生成树O（ ） 最短路（从一点到所有点）O（ ） 所有节点间的最短路O（ ） 平面化：NP 着色：NP 最长路：NP 斯坦纳树：NP 旅行商问题：NP 2 n 2 n 3 n
3、几种求解NP-困难问题的方法 限制问题的范围:只对某一类问题求解 例如在求图上的最小树时只求最小生成 树,即限制数的交叉点只能是原有的顶 点,求最小生成树是一个多项式时间内 可求解的,但它不一定能获得最小树。 狠制问题的规模:例如旅行商问题的分 区优化。 分支定界法: 启发式算法: 2021/2/21
2021/2/21 14 3、几种求解NP-困难问题的方法 • 限制问题的范围：只对某一类问题求解。 例如在求图上的最小树时只求最小生成 树，即限制数的交叉点只能是原有的顶 点，求最小生成树是一个多项式时间内 可求解的，但它不一定能获得最小树。 • 限制问题的规模：例如旅行商问题的分 区优化。 • 分支定界法： • 启发式算法：
基本算法 1.图论算法:DFS、BFS、最短路径、最 小生成树、斯坦纳树算法、匹配算法 网络流问题 2.计算几何算法:扫描线算法。 3基于运筹学的算法:构形图和局部搜 索、线性规划、整数规划、动态规划、 非线性规划、模拟退火法。 2021/2/21 15
2021/2/21 15 三、基本算法 1.图论算法：DFS、BFS、最短路径、最 小生成树、斯坦纳树算法、匹配算法、 网络流问题。 2. 计算几何算法：扫描线算法。 3.基于运筹学的算法：构形图和局部搜 索、线性规划、整数规划、动态规划、 非线性规划、模拟退火法