数据结构14

数据结构PPT

第14章 分治算法

数据结构PPT

学习内容 分治算法思想

应用 最大最小问题 矩阵乘法 残缺棋盘 排序

选择 求二维空间中距离最近的点

复杂性分析的数学方法

数据结构PPT

14.1 算法思想

原问题的解决方法1)2) 3)

分解为若干个小问题 分别解决每个小问题 将小问题的解组合为原问题的解

数据结构PPT

关键：小问题如何解决呢？

采用与原问题完全相同的求解方法，继 续分而治之！

分解为更小的问题，再继续… 什么时候是个头呢？——直至分解为原子 问题，原子问题是自然可解的

递归

问题分解——递归规则 原子问题——基本规则(停止条件)

数据结构PPT

例：寻找伪币 16个硬币，有1个是伪造的，比其他的轻

找出伪币，可利用一比较硬币重量的仪器 在16个硬币中找伪币——原始大问题 分解 两组，各8个硬币，比较两组重量

若相等，无伪币；若不等，较轻一组有伪币

数据结构PPT

例：寻找伪币 较轻的一组继续分解，两组各4个硬币，比较

较轻的一组继续分解，两组各2个硬币，比较 较轻的一组2个硬币——原子问题，比较重量

得到较轻的那个即为伪币 无需组合过程

数据结构PPT

例：金块问题 老板有一袋金块，每月选出两名优秀员

工，第一名奖励最重金块，第二名奖励 最轻的 平凡算法：

对n个金块进行n-1次比较找出最重的 剩余n-1个金块用n-2次比较找出最轻的

数据结构PPT

例：金块问题 分治算法

原子问题——2个金块 分解方法： 1)n个金块分为数目相等的两组A和B 2)找出A的最重、最轻HA和LA,B的最重、最 轻HB和LB 3)HA和HB较重者为最重金块，LA和LB较轻者为 最轻 简单的复杂性分析

c(2)=1,c(n)=2c(n/2)+2 c(n)=3n/2-2

数据结构PPT

例：矩阵乘法C (i, j ) A(i, k ) * B(k , j ),1 i n,1 j nk 1 n

运算次数：n3m+n2(n-1)a 分治算法 原子问题：n=1的情况

数据结构PPT

分解方法

复杂性分析

C1=A1B1+A2B3 C2=A1B2+A2B4 C3=A3B1+A4B3 C4=A3B2+A4B4 8次n/2阶矩阵乘法，4次n/2阶矩阵加法，总运算次 数并未减少，分解、组合——性能反而下降

数据结构PPT

Strassen方法 D=A1(B2-B4)

E=A4(B3-B1)

F= (A3+A4)B1 G=(A1+A2)B4 H=(A3-A1)(B1+B2) I=(A2-A4)(B3+B4) J=(A1+A4)(B1+B4) 7次矩阵乘，6次矩阵加，4次矩阵减 C1=E+I+J-G C2=D+G C3=E+F C4=D+H+J-F 6次矩阵加，4次矩阵减

数据结构PPT

Strassen方法实例D=1(6-8)=-2 E=4(7-5)=8 F=(3+4)5=35 G=(1+2)8=24 H=(3-1)(5+6)=22 I=(2-4)(7+8)=-30 J=(1+4)(5+8)=65 C1=8-30+65-24=19 C2=-2+24=22 C3=8+35=43 C4=-2+22+65-35=50

直接计算：8次乘法，7次加减法 分治方法：7次乘法，18次加减法——加减法必 须远快于乘法，才有提高

数据结构PPT

Strassen方法(续) n<8——原子问题 n=8

7次矩阵乘(64m+48a)和18次矩阵加减(16a) 总运

算次数：448m+624a 直接计算：512m+448a 当一次乘法开销大于2.75次加减法的开销时， Strassen更优

数据结构PPT

矩阵乘法(续) n<16——原子问题 n=16:7(512m+448a)+18(64a)=3584m+4288a 直接计算：4096m+3840a

d,n k t (n) 2 7t ( n / 2) cn , n k t ( n ) (nlog2 7

) (n

2.81

)

数据结构PPT

例：金块问题

数据结构PPT

非递归实现template<class T> bool MinMax(T w[], int n, T& Min, T& Max) {// Locate min and max of w[0:n-1]. // Return false if fewer than one element. // special cases, n <= 1 if (n < 1) return false; if (n == 1) {Min = Max = 0; return true;}

数据结构PPT

非递归实现(续)// initialize Min and Max int s; // start point for loop if (n % 2) {// n is odd Min = Max = 0; s = 1;} else {// n is even, compare first pair if (w[0] > w[1]) { Min = 1; Max = 0;} else {Min = 0; Max = 1;} s = 2;}

数据结构PPT

非递归实现(续)// compare remaining pairs for (int i = s; i < n; i += 2) { // find larger of w[i] and w[i+1] // then compare larger with w[Max] // and smaller with w[Min] if (w[i] > w[i+1]) { if (w[i] > w[Max]) Max = i; if (w[i+1] < w[Min]) Min = i + 1;} else { if (w[i+1] > w[Max]) Max = i + 1; if (w[i] < w[Min]) Min = i;} } return true; }

数据结构PPT

14.2 应用残缺棋盘 2k×2k个方格的棋盘，有一个方格残缺 14.2.1

数据结构PPT

问题要求

用三格板(triominoes)覆盖残缺棋盘 三格板不能重叠，不能覆盖残缺方格，但要覆 盖其他所有方格——需用(22k-1)/3个三格板 k=0,需0个 k=1,按残缺方格位置选择一个三格板即可达 到要求

数据结构PPT

分治法解残缺棋盘问题 分解：2k×2k棋盘 4个2k-1×2k-1棋盘 但只有1个子棋盘有残缺——与原问题相似 可继续分解，其他3个棋盘不行 解决方法：

原棋盘中央放置一三格板 覆盖三个无残缺的棋盘 均变为残缺的 4个棋盘都可继续分治了