下载文档原格式
算法导论答案第一章：算法概述啊算法的定义算法是一系列解决问题的明确指令。
它是一个有穷步骤集，其中每个步骤或操作由确定性和可行性特征。
算法是通过将预期的输入转换为输出来解决问题的工具。
第二章：插入排序插入排序的思想插入排序是一种简单直观的排序算法，其基本思想是将待排序的序列分为已排序和未排序两部分，每次从未排序的部分中取出一个元素，并将其插入到已排序部分的正确位置，直到所有元素都被排序。
插入排序的算法实现以下是插入排序的伪代码：INSERTION-SORT(A)for j = 2 to A.lengthkey = A[j]// Insert A[j] into the sorted sequence A[1.. j-1].i = j - 1while i > 0 and A[i] > keyA[i + 1] = A[i]i = i - 1A[i + 1] = key插入排序的时间复杂度插入排序的时间复杂度为O(n^2)，其中n是排序的元素个数。
虽然插入排序的最坏情况下的复杂度很高，但是对于小规模的数据集，插入排序是一种较快的排序算法。
第三章：分治策略分治策略的基本思想分治策略是一种解决问题的思想，它将问题的规模不断缩小，直到问题足够小而可以直接解决。
然后将子问题的解合并起来，得到原问题的解。
分治策略的应用实例一种经典的应用分治策略的算法是归并排序。
归并排序将待排序的序列划分为两个子序列，分别排序后再将两个有序子序列合并为一个有序序列。
以下是归并排序的伪代码：MERGE-SORT(A, p, r)if p < rq = floor((p + r) / 2)MERGE-SORT(A, p, q)MERGE-SORT(A, q + 1, r)MERGE(A, p, q, r)MERGE(A, p, q, r)n1 = q - p + 1n2 = r - qlet L[1..n1+1] and R[1..n2+1] be new arraysfor i = 1 to n1L[i] = A[p + i - 1]for j = 1 to n2R[j] = A[q + j]L[n1 + 1] = infinityR[n2 + 1] = infinityi = 1j = 1for k = p to rif L[i] <= R[j]A[k] = L[i]i = i + 1elseA[k] = R[j]j = j + 1分治策略的时间复杂度归并排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。
11.1dynamic programming decision process 20 50 R. E. Bellman (multistep decision process) principle of optimality 1957 Dynamic Programming11 AG121 3 623 24 0.51.2discrete-timedecision process continuous-time decision process deterministic decision process stochastic decision process§22.12.1.1(step) n k ,,2,1 1 A 1 k )2,1( i B i 2 k )2,1( i F i 6 k 6 n 2 4,3,2,1 k2.1.2statestate variable (set of admissible states) k x k k X k 1 2x 21,B B i B )2,1( i i 12 x 2 }2,1{2 Xn 1 n 1 n x n x 1 7x G 1 17 x2.1.3decision controldecision variable set of admissible decisions )(k k x u k k xk x)(k k x U k x 1 )(12B u 21,C C 3C 3,2,1)1(2 u }3,2,1{)1(2 U2.1.4policy 1x )(11x p n)}(,),(),({)(221111n n n x u x u x u x p .k k x )(k kn x p)}(,),({)(n n k k k kn x u x u x p 1,,2,1 n k .k j)}(,),({)(j j k k k kj x u x u x p .(set of admissible policies) )(),(),(11k kj k kn n x P x P x P2.1.5.equation of state transition.,,2,1),,(1n k u x T x k k k k 1 1 )(1k k k x u x2.1.6.(objective function) ),,,,(11, n k k k n k x x u x V n k ,,2,1 n k V , n k k k V u x ,1,,)),,,(,,(),,,,(111,111, n k k n k k k k n k k k n k x u x V u x x x u x Vk n k V ,1 j j x j u ),(j j j u x v ),,2,1(n j v jn kj j j j n k k k n k u x v x x u x V ),(),,,,(11,n kj j j j n k k k n k u x v x x u x V ),(),,,,(11,),((min)max ),,,,(11,j j j nj k n k k k n k u x v x x u x V . k j ),,,(1, j k k j k x u x Vn k V , k x kn p),(,kn k n k p x Vk x n k V , kn p optimal value function )(k k x f),(opt )(,)(kn k n k x P p k k p x V x f k kn knopt max min2.1.7n k V , k },,{***n k kn u u p *1n p optimal policy )(*11x x *1n p },,,{*1*2*1 n x x x optimal trajectory2.1.81,,)},(),({opt )(10)(11)(11 n k x f u x v x f x f k k k k k x U u k k n n k k k 2 0)(11 n n x f 1)(11 n n x f 1 2 1 n k 1 kn k u x T x k k r k k ,,1),,(1n k x f u x v x f x f k k k k k x U u k k k r k k ,,1)},(),({opt )(10(11)(110113 lingo 1model: Title Dynamic Programming; sets: vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L; road(vertex,vertex)/A B1,A B2,B1 C1,B1 C2,B1 c3,B2 C2,B2 C3,B2 C4, C1 D1,C1 D2,C2 D1,C2 D2,C3 D2,C3 D3,C4 D2,C4 D3, D1 E1,D1 E2,D2 E2,D2 E3,D3 E2,D3 E3, E1 F1,E1 F2,E2 F1,E2 F2,E3 F1,E3 F2,F1 G,F2 G/:D; endsets data: D=5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3; L=0,,,,,,,,,,,,,,,; enddata @for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i))); endiii k x k Xiii k u )(k k x Uivv ),(k k k u x v kn Vvi§31,1,11,,2,1),()( n i n i n n n i x x f (3)}{}{*111x x Xk x k u k x n k n i n i x X k k ki k ,,2,1,,,2,1},,,2,1|{ .)(ki ki x un k n i n j u U k ki j ki ki ,,2,1,,,2,1},,,2,1|{)( .k x ki x ki u )(j ki u),()(j ki ki k k u x T T ),()(j ki ki k u x v v k x ki x.1,2,,,,,2,1,,,2,1),(opt )()),,((),()()()(1)()( n k n i n j x f x f u x T f u x v x f k ki ki j k j ki k j ki ki k k j ki ki k ki j k 423 4 )(*11x f ki x)(*ki ki x u *1x )(*ki ki x u *k x )(**k k x u )}(,),(),({***2*2*1*1n n x u x u x u2)(*11x f )(ki k x f )(*ki k x u)(ki k x f 1 k f 1 k f 1 k f k f )(*ki k x u )(**k k x u)}(,),(),({***2*2*1*1n n x u x u x u },,,{**2*1n x x x§4n u u u ,,,21 ),,,(2111n n u u u x V4n k k k u g 1)(maxs.t. n k k k u a u10,.)(k k u gk u n 121,,, n x x x n u u u ,,,21.,,2,1,,11n k u x x a x k k k)(k k u g 01 n x)]()([max )(110 k k k k x u k k x f x g x f kk 1,2,,1,,0 n n k a x k0)0(1 n f .k x )(*k k x u )(1a f }{*k x )}({**k k x uiiiiiiiii curse of dimensionality m n k x n m )(k k x f n§55.11 shortest Path Problem )(1k k k x u x ))(,(k k k k x u x d )(k k x f k x;1,,)],())(,([min )(11)( n k x f x u x d x f k k k k k k x u k k k k .0)(11 n n x fl G F E D C AB 2212118 5.22 Production planning problem k x k u k d.,,2,1,0,1n k x d u x x k k k k k (5)a b c00,),(k k k k k k u bu a cx u x v (6)kn V k v )(k k x f k k x.1,,)],(),([min )(11 n k x f u x v x f k k k k k U u k k kk k U 01 n x.0)(011 n n x f 75 ~ 75.3resource allocating Problem5 u )(u g )(u h 1a 1b 1011 a b m n n u u g )( u u h )( 0n k ,,2,1 k x k k u k k x k ua b 11a a 11b b b a k k k u x)(1k k k k u x b au x 8k v k)()(),(k k k k k k u x h u g u x v 9)(k k x f.1,2,,,0 )],(),([max )(110 n k m x x f u x v x f k k k k k k x u k k kk (10).0,0)(111m x x f n n n 11k v h g , ku u g )( u u h )(10 )](),([1k k k k k x f u x v k u k k x u 0 0 k u k k x u§66 1000 B A x Ax 5 y B y 4 A 20% B 10% 55,4,3,2,1 kk x k k u k A k k u x k B k k x u 01 kk k k k k k u x u x u x 1.09.0))(1.01()2.01(1 12 ),(k k k u x v k )(k k x f k0)(66 x f 13)}(),({max )(110 k k k k k x u k k x f u x v x f kk )}(4{max )}()(45{max 110110 k k k k x u k k k k k x u x f x u x f u x u kk k k 14 1 5 k 13 14}4{max )(5505555x u x f x u 554x u 5u 554x u 5u 5x 55x u 5555)(x x f2 4 k 12 14}54{max )(54404444x x u x f x u }5.85.0{max )}1.09.0(54{max 440444404444x u u x x u x u x u 44x u 4449)(x x f3 3 k}94{max )(43303333x x u x f x u }1.121.0{max )}1.09.0(94{max 330333303333x u u x x u x u x u 33x u 3332.12)(x x f4 2 k}98.1422.0{max }2.124{max )(2203220222222x u x x u x f x u x u 02 u 22298.14)(x x f5 1 k}482.17498.0{max }98.144{max )(1102110111111x u x x u x f x u x u 01 u 111482.17)(x x f10001 x129001.09.0112 u x x8101.09.0223 u x x6481.09.0334 u x x4.5181.09.0445 u x x4.5185 x 0.4 0.4 73221max u u u z 3,2,10)0(321i u c c u u u i4321,,,x x x x c x 1 321,,u u u )(k k x f k k x k 333u x 223x u x c x u x 11233x u 220x u 110x u3333}{max )(33x u x f x u 3*3x u ),(max )}({max )}({max )(2220222203322022222222x u h u x u x f u x f x u x u x u 032222222 u x u du dh 2232x u 02 u 22222262u x du h d 02232222222 x du h d x u 2232x u 3222274)(x x f 2*232x u })(274{max )}({max )(311102*********u x u x f u x f x u x u 4111641)(x x f 1*141x u 1xc u 41*1 411641)(c x f c c c u x x 4341*112c x u 21322*2322161)(c x fc c c u x x 412143*223c u 41*3c x f 41)(33 c u 41*1 c u 21*2 c u 41*341641)(max c c f z1. Matlab 62. 4 13. 321,,E E E 8000 221E2E3E1E2E3E1 2 30.3 0.4 0.50.2 0.5 0.90.1 0.2 0.71 2 33 5 62 3 44. 100 I II I 45 65 II 35 355 3 1 26 3。
