《算法设计技术》doc版.doc

蒂羂肄芈螀羁膇蒄蚆羀艿芇薂聿罿蒂蒈肈肁芅螇肈膃蒀螃肇莆芃虿肆肅蕿薅蚂膈莂蒁蚁芀薇蝿蚁羀莀蚅螀肂薅薁蝿膄莈蒇螈莆膁袆螇肆蒆螂螆膈艿蚈螅芁蒅薄螅羀芈蒀螄肃蒃蝿袃膅芆蚅袂芇蒁薁袁羇芄薇袀腿薀蒂衿节莂螁衿羁薈蚇袈肄莁薃袇膆薆葿羆芈荿螈羅羈膂蚄羄肀莇蚀羃节膀薆羃羂蒆蒂羂肄芈螀羁膇蒄蚆羀艿芇薂聿罿蒂蒈肈肁芅螇肈膃蒀螃肇莆芃虿肆肅蕿薅蚂膈莂蒁蚁芀薇蝿蚁羀莀蚅螀肂薅薁蝿膄莈蒇螈莆膁袆螇肆蒆螂螆膈艿蚈螅芁蒅薄螅羀芈蒀螄肃蒃蝿袃膅芆蚅袂芇蒁薁袁羇芄薇袀腿薀蒂衿节莂螁衿羁薈蚇袈肄莁薃袇膆薆葿羆芈荿螈羅羈膂蚄羄肀莇蚀羃节膀薆羃羂蒆蒂羂肄芈螀羁膇蒄蚆羀艿芇薂聿罿蒂蒈肈肁芅螇肈膃蒀螃肇莆芃虿肆肅蕿薅蚂膈莂蒁蚁芀薇蝿蚁羀莀蚅螀肂薅薁蝿膄莈蒇螈莆膁袆螇肆蒆螂螆膈艿蚈螅芁蒅薄螅羀芈蒀螄肃蒃蝿袃膅芆蚅袂芇蒁薁袁羇芄薇袀腿薀蒂衿节莂螁衿羁薈蚇袈肄莁薃袇膆薆葿羆芈荿螈羅羈膂蚄羄肀莇蚀羃节膀薆羃羂蒆蒂羂肄芈螀羁膇蒄蚆羀艿芇薂聿罿蒂蒈肈肁芅螇肈膃蒀螃肇莆芃虿肆肅蕿薅蚂膈 算法设计技术常用技术分治法 （Divide and Conquer）贪心法 （Greedy）动态规划法 （Dynamic programming）回溯法 （Backtracking）分枝界限法 （Branch and Bound）局部搜索法 (Local search algorithms）一、 分治法 定义：对于一个输入大小为n的函数或问题，用某种方法把输入分划成k个子集。（ k n）。从而产生L个子问题，解出这L个子问题后再用某种方法把它们组合成原来的解。如子问题相当的大，则递归使用分治法。 时间复杂度 T(n) g(n) n足够小 T(n)= 2T(n/2)+f(n). 其它 g(n) n很小时，直接计算时间。 f(n) 分成二个子问题解后的整合时间。例1.1 求一个集合中的最大元素和最小元素。 Procedure maxmin(s);1. if |s|=22. then begin 设|s|=c,d;3. (a,b)(MAX（c,d),MIN(c,d). end else begin4. 把S分成二个子集S1，S2，各存一半元素；5. (maxl, minl) maxmin(S1 );6. (max2, min2) maxmin(S2 );7. （a,b） (MAX(max1,max2), MIN(min1,min2) end 例：1.2 找第k个最小元素。 一般先分类为递减序列，得到第k个最小元素，要O (nlogn). 分治法可以O (n)内得到第k个最小元素。当k=n/2时，成为在线性时间内找一个序列的中值问题。 procedure SELECT(k,s) bagin.1. if |s|50 then2. begin 3. 把S分类4. return S的第K个最小元素. end5. else 6. begin 7. 把S划分成各为五个元素的|s|/5个子序列；8. 设L是剩余元素（如果有的话）；9. 把上述各个5元素序列分类；10. 设M是5个元素的中值序列；11. m SELECT( |M|/2 ,M)；12. 设S1，S2，S3为S的分别 m的元素序列；13. if |S1|k then return SELECT(k, S1 ) else14. if (|S1|+|S2|k) then return m15. else 16. return SELECT(k-|S1|-|S2|, S3 ) end end说明：1.把S大问题化为S1，S2，S3 三个小问题。 2.选合适中值，原n变为n/5个数中选，速度就快5倍。 至少有1/4的元素 m, 至少有1/4的元素 m 。 3.子序列用5分割是算法中有二个SELECT递归调用，每次是对r|s|的序列调用， 二个序列之和必须，=，2，删去大的，只留下2个。 7 0 27 22 6 删除时，如果其列只有二个元素的， 要保留。 Cij 每行（或每列）只剩两个加标元素。 检查是否成圈，如为几个子圈，则合一。 47 15 37 11 7 1-5-6-2-4-3-1cost = 75 这是一条COST 最小的路线 47 31 19 23 8 15 31 16 63 27 37 19 16 13 22 11 23 63 13 6 7 8 27 22 6 procedure EXPLORETOURnegin1 cost 0;2 TOUR ;3 for i1 to n do begin4 设cij和cik (kj) 是矩阵 (cij) 第i行中的最小和次小元素；5 if ( i, j ) v TOUR then begin6 TOUR TOUR 4 (i, j) 4 (j, i);7 cost COST + cij end 8 if ( i, k ) v TOUR then begin 9 TOUR TOUR 4 (i, k) 4 (k, i);10 cost COST + cik end end11 从集合TOUR中找出所在行和列都至少有三条边在TOUR中的那些边（ i, j ）,并将相应的cij排成递增序列S;12 while S do begin13 从S中删去最大元素cij；14 TOUR TOUR - (i, j), (j, i);15 cost cost - cij 16 从S中删去所在行和列都只有二条边在TOUR中的那些边所对应的元素cik 或ckj。 end17 当TOUR中边构成二个以上圈时，合并成一个圈， end 三、 动态规划法 问题： xi 仅限值于和的 0/1背包问题。 方法：贪心法在每一决策步都得到一个局部最优解，但背包问题上就不能得到最优 解。 动态规划法是 在每一决策步上，列出各解可能的局部解。按某些条件，舍弃那些肯定不能得到最优解的局部解，这就是“最优性原理”。 最优性原理： 一个最优的决策（判定）序列具有下列性质：不论初始的状态和策略如何，余下的 决策必须相对于前一次决策所产生的新状态构成一个最优决策序列。例. 流水作业调度（Flow shop scheduling） 问题：流水作业上有n个作业T1, T2, , Tn. 每个作业分为m个任务Ti1,Ti2,Tin. (1in) 计算机系统有m台，计算机 Pj (1jm) 要求：任务Tij必须由处理机Pj处理,Pj同时只能作一项任务。 任务Tij完成的时间为Tij,在Ti,j-1完成时，Tij才能开工。 目标：为任务Tij在Pi上安排工作时间表，使用最少时间来完成一批作业。 例如： T11 T12 T13 2 3 5 T1 J= 二批作业 3 2 T2 T21 T22 T23 三个处理机 Pj (1j3) 0 2 5 6 10 12 “优先调度”P1 T11 允许一个任务末完成时，P2 T22 T12 T22 被另一任务中断。P3 T13 T23 11 “非优先调度”P1 T11 不允许一个任务被中断P2 T22 T12 所以“非优先调度”比 P3 T23 T13 “优先调度”好。 fi(s) 作业i在调度S下完工时间 FT(s) 调度S总的完成时间 FT(s)= MAX fi(s) (1in) MFT(s) 流水作业的平均完工时间 MFT(s)=1/n fi(s) (1in) OFT(s) 最优完工时间为非优先调度的FT(s)最小值作业调度满足最优性原理： 排列中确定第一个作业后，随着第一个作业的完成，余下的作业排列仍是一个最优排列。 按某一确定顺序执行情况的好坏，用t=f2-f1来表示。设g(s,t)为最优作业调度长度。 f1, f2为S调度下，二个处理机P1, P2 (假如只有2个处理机) 各自完成T1, T2, Tk的时间。f1 为处理机P1 完成T11, . 时间f2 为处理机P2完成T12, . 时间最优调度长度：g(s, t)假定处理机在t时刻之前不能工作，则最优调度长度为g ( 1, 2, ，n, 0)g (1, 2, , n, o ) = minai + g ( 1, 2, , n - i , bi) (1in)如果g (, t) = max t, o 和 ai0 1ing (S, t) = min ai + g(S-i, bi + max t - ai, o)因为f2 - f1 = bi + maxai,t ai = bi + maxt - ai, o.可证：对任一对相邻作业i和j, 若有minbi, aj minbj, ai。则总存在一个最优调度，而且具有这种性质的所有调度有相同的长度。最优调度方案：1. 将a1,a2,a3,an, b1,b2,bn排成非递减序列2. 依次从序列中抽出最小元素 m，如果m = aj。且作业j还设有排入调度表，则把作业安排在调度表可达的最左面一项定位上。（n个作业的调度有n项。开始全部为空。）如果m = bj，且作业j未排入，则把作业j排在最右项上。如果作业j 已排入，则取序列下一个最小元素。3. 继续1、2，直到元素取完为止。例3.2 n=4(a1, a2, a3, a4 ) = (3, 4, 8, 10)(b1, b2, b3, b4) = (6, 2, 9, 15)排序后为（b2, a1, a2, b1, a3, b3, a4, b4）= (2, 3, 4, 6, 8, 9, 10, 15)设 a1 a2 a3 a4 为最优调度。 M = b2 = 2 t a4 = T2 (最右) a1 = 3 t a1 = T1 (最左) a2 = 4 作业2已被调度 b1 = 6 作业1已被调度 a3 = 8 t a2 = T3 (最左) a3 = T40 3 9 11 21 25 35 37 a1 a3 a4 a2 b1 b3 b4 b2 0 3 7 9 11 15 24 25 40 a1 a2 a3 a4 b1 b2 b3 b4n = 2时，动态规则法能极大减低复杂度，（O(nlogn)）n 2时，已证为NP难题。（O(ni)）四、 回溯法基本思想若已有满足约束条件的部分解，设为（x1, x2, xi）, i n, 则添加 xi+1Si+1。查（x1,x2,xi ，xi+1）是否满足约束条件。如满足再添加如不满足，回溯到上个部分解（x1,x2,，xi-1 ），反复之，得到解或证明无解。例4.1 八皇后问题 1 2 3 4 5 6 7 81 Q 隐含约束2 Q 没有二个xi相等3 Q 没有二个xi在对角线上。4 Q5 Q6 Q 解：（4，6，8，2，7，1，3，5）7 Q8 Q树节点“问题的状态”状态空间从根到各个点的所有路径解状态集问题状态空间的子集S。状态空间树对应于解空间中的树形结构。从根到解状态集子集的每一条路径确定了解集合中的一个多元组，它满足这个问题的约束条件。 x1 =1 x1 =2 x1 =3 x1 =4 x2 =2 3 4 1 3 4 1 2 4 1 2 3x3 =3 4 2 4 2 3x4 = 4 3 4 2 3 2四后问题解空间的树形结构回溯法：根据约束条件建立状态空间树。从根开始逐步生成（深度优先、宽度优先）各节点，及时舍弃那些不满足约束条件的节点。（及可能产生的子树） x1 =1 x1 =2 x2 =2 3 4 x1 =1 3 4BBBB x3 =2 4 2 3 x3=1BBB x4 =3 x4 =3五、 分枝界限法特定类型的摒弃法，它利用对代价函数上下界计算把状态空间树上那些不可能产生最优解的子树剪去。一般采用广度优先的搜索技术。分枝界限法类似回溯法，但复杂，用于求最优解问题代价函数 C（a 1, a2, ., a k）对问题每一个可行解的代价值计算 C (a1, ., ak ) C (a1, . ak, ak+1)摒弃原则 如果部份解（a1, ., ak ）代价大于已经算出的某一可行解代价 则由（a1, a2, ., ak ）扩展出的可行解必不是最优。因此应予抛弃。 设定上界值U 当节点代价值大于U时，该节点不保留，并由它产生的子树全部剪去。 一般为计算方便，代价函数用易计算的函数 (a1, ., ak ) 代替。称为下界函数 (a1, ., ak ) C (a1, ., ak )搜索方法广度优先（F1F0）深度优先（L1F0）最小代价搜索法（LC） 利用判定函数，对每一个活动节点产生一函数值。选取最好点扩展例51旅行商问题 20 30 10 1115 16 4 23 5 2 419 6 18 316 4 7 16 行（列）归约： 代价矩阵中任一行（列）各元素中，减去这一行（列）中最小元素。 10 20 0 1 10 17 0 113 14 2 0 12 11 2 01 3 0 2 0 3 0 216 3 15 0 15 3 12 012 0 3 12 11 0 0 12 归约矩阵： 各行各列都是归纳的代价矩阵。r(i) i行的约数r(i) i列的约数r 矩阵的约数 r = r( I ) + r( j ) (1in, 1jn)C 10 17 0 1 r(1)=10 12 11 2 0 r(2)=2 0 3 0 2 r(3)=3 15 3 12 0 r(4)=3 11 0 0 12 r(5)=4r(1)= 1 0 3 0 0 最小价周游路线问题 = 归约矩阵C的最小代价周游路线问题 方法： 对每一个节点建立一个相应的归约代价矩阵。并定义下界值r.R根节点下界值 r = (root) 原始归约代价矩阵 (25)扩展节点下界值 r = ( S ) = ( R ) + Ar (i, j) + rsS ( R ) 父节点的下界值Ar (i, j) 归约代价矩阵的 Cij 代价rs 新矩阵归约后的r. 选取活动节点表中具有最小的点为当前扩展点。新矩阵归约： 选定一节点i扩展到k时， Ar(i, k)的 i 行， k列的点不可取, 相应元素量为 Ar(k, 1)为 再对新矩阵归约，求rs.25(1,5)1(1,4)(1,3)(1,2)542325(4,2)(4,5)315335(4,3)6(2,5)2887(2,3)50361092852(5,3)2811 11 2 0 12 11 0 0 0 2 0 3 2 15 12 0 3 12 0 11 0 12 11 0 0 rs=0 rs=0 (2)= (1) + C(1,2) + rs (4)= (1) + C(1,4) + rs=25+10+0=35 =25+0+0=25周游线路 1 u 4 u 2 u 5 u 3 u 1 代价 = 28六、局部搜索法局部搜索法：（1）取任一随机解 （2）应用适当变换改进当前解，为新的当前解。 （3）重复（2）直至没有变换能改进当前解为止。 一般对变换集有限制，当n为输入大小时，变换集取O（n2）或O（n3）,选择的变换以当前解与新解有密切关系为准，因此变换是“局部变换”。 局部搜索法的解不保证是最优的例61组件布局问题2（条） 8465436 abcde37 问题：如何安排a,b,c,d,e插件，使导线总长度最短。局部变换：1. 变换2相邻组件Pi和Pj. L(j) = W(PK , Pj ) (1 k j-1) R(j) = W(PK , Pj ) (j+1 k n) 长度变化 = L(i) - R(i) + R(i+1) - L(i+1) + 2W(Pi, Pi+1)i+1i-1iR(i)L(i) R(i+1)L(i+1)000如长度变换0，则交换i和j后，解得到改进。2.对某个i和j，把组件i插到Pj和Pj+1之间。3.交换任意二组件Pi和Pj.(a) 原cost=97(b) 如d, e交换L(d) 即a, b, c到d长度 = 2+6+5 = 13R(d) 即e 到d长度 = 6L(e) 即a, b, c, d到e长度 = 7+3+8+6 = 24R(e) 无后结点 = 0长度变化=L(d) - R(d) + R(e) - L(e) + 2w(d,e) = 13 6 + 0 24 + 26 = -5 0 cost =92(c) 如c, e交换 cost=91，相对(a)的局部最优解，不是全局最优。(d) 最优解 (a, c, e, d, b) cost=84 为最优解。图灵机（Turing machine） 什么是“计算”？ 什么是“可计算函数”？ 图灵机23世纪英国数学家图灵创造的一种计算模型，它可以确切地表达计算，可计算函数和计算复杂度等基本概念，也是描述NP问题的基本工具。图灵关于计算的精确定义实质上是模拟人的动作 图灵的限制条件 （不影响问题的实质）（1） 将运算介质确定为线性带子（不是二维的纸），带子可想象为磁带，带被划分为方格。（2） 规定一次只注视一个符号，“注视”由读写磁头执行。（3） 一组运算法则存放在“有限状态控制器”中。控制器根据当前“状态”和磁头注视的“符号”决定下一步动作。磁头每次只能动一步，并只能移动左右相近方格上。多带图灵机定义多带图灵机由K条带组成，这些带右边可以无限延伸。每一条带都划分成单元（方格），每个单元存放着有限个带符号集中的一个符号。每条带都有一个可以读和写的磁头来扫描带上的一个单元。图灵机的操作，由称之为有限控制器的原始程序来确定。有限控制器总是处于有限个状态中的某一个状态，由当前状态和磁头当前扫描的字符可以确定下一步所要的执行的指令。 K条带 多带图灵机图灵机的计算步骤 -根据有限控制器的当前状态以及每个磁头注视的带符号执行以下操作。1. 改变有限控制状态。2. 在某几个或全部磁头所指的单元内，擦去当前的带符号，印上新的带符号。3. 任几个或全部磁头不相关地向左移动一格（L）或向右移动一格（R）或保持不动（S）。可以用七元组 （Q, T, I, d, b, qo, qf）形式地表示图灵机其中1. Q是状态的有限集合；2. T是带符号的有限集合；3. I是输入符号的集合，IT;4. b 是空白符，bT - I;5. qo是初始状态；6. qf 是最后（接受）状态；7. d 转移函数d 转移函数-是 QTk 的子集到 Q ( T L, R, S) k的一个单值映射。即对于由一个状态和k个带上磁头扫描着的符号组成的某个k+1元组，它产生一个新状态和k个对偶，每一对偶含有一个新的带符号和带头的移动方向。假设（q,a1,a2,.ak）=(q,(a1,d1),(a2,d2),(ak,dk),则当图灵机处于状态q，第i个磁头扫描着符号ai(1ik)时，移动后图灵机就进入状态q，把符号ai 改为ai ，并按方向di来移动第i个磁头(1ik)。由于Q和T的有限性，保证了函数的定义域和值域的有限性。它们构成一台图灵机的指令表。确定图灵机（deterministic Turing machine简称DTM） -是单值映射的图灵机如果 图灵机的一个输入串是输入符号集I中的字符的有穷序列，且 一个输入符号串是可接受的（即从指定的初始状态开始，且所有带的磁头都处于带的最左端单元上）那么 图灵机在一系列的转移后最终都能进入接受状态（称为正常停机）。例1 非负整数的加法 筹码计数法加法指令表：（q0, 1, 0, R, q1） (意指 Q（q0, 1）= （q1,（0, R）2.(q1, 0, 1, R, q2)3.(q1, 1, 1, R, q1)4.(q2, 0, 0, L, q3)5.(q2, 1, 1, R, q4)6.(q3, 0, 0, R, q0)7.(q3, 1, 1, L, q3)8.(q4, 1, 1, R, q4) 9.(q4, 0, 0, L, q5)10.(q5, 1, 0, S, qf)布局（Configuration） - 一个K带图灵机M的一个布局是一个K单元组（a1,a2,ak）, ai(1ik)是形如x g y 的串，x y是的第i条带上的串（尾端空白略去），q是当前的状态,q右边的符号是第i条带上当前磁头扫描着的符号。M布局表示 - D1 D2 （D1 转入 D2 ） 停机布局（正常布局） - 含有qf的布局 对加法图灵机执行时的一个布局序列如下。（q01110011） (0q1110011) (01q110011) (011q10011) (0111q2011) (011q31011) (01q311011) (0q3111011) (q30111011) (0q0111011) (00q111011) (001q11011) (0011q1011) (00111q211) (001111q41) (0011111q40) (尾部为输入串后空白) (001111q510) (001111qf0)例“回文”（Palindromes）语言的识别. 带的第一个单元标以特殊符号X，且把带1的输入串（图a）复写到带上（图b）。. 然后把带的磁头移到X（图c）。. 重复地将带的磁头右移一个单元，且带的磁头左移一个单元，比较各自的符号。如果所有的符号都相符，则输入就是一个回文，图灵机接受状态q5（qf）。否则图灵机在某一时刻不作合法移动，它将停机且表明该字符串不是回文。 q0 q1 q2 0 1 11 0 bb . 0 1 11 0 b b . 0 11 1 0b b . b b bb b bb . x0 1 11 0 b . x0 1 1 10 b .（图a） （图b） （图c）。当前状态带上符号 新符号、 磁头移动新状态说 明带带带带q0bbbb0, S1, Sb, SX, RX, Rb, Sq1q1q5若输入非空，则在带上印X，磁头右移进入状态q1，否则进入状态q 。q101bbbb0, R1, Rb, S0, R1, Rb, Lq1q1q2把带复写到带的过程中，停留在状态q1，直至在带上遇到b为止。然后进入状态q。q2bbb01Xb, Sb, Sb, L0, L1, LX, Lq2q2q3带的磁头不动，移动磁头，直至遇到X才脱离此状态，然后进入状态q 。q301010, S1, S0, R1, Rq4q4控制状态在q3和q4间交替。在q3状态时，比较两条带上的符号，带的磁头右移，进入q4。在q4状态里，如果带上的磁头已到达b，则进入q5，被接受。否则磁头左移，返回状态q3。q 和q 交替可以防止输入磁头从带左端滑出。q40011010101bb0, L0, L1, L1, L0, S1, S0, S1, S0, S1, Sb, Sb, Sq