1、實現(xiàn)這種分治策略的ehessBoanl 實現(xiàn)這種分治策略的ehessBoanl 口J實現(xiàn)如卜: public void chessBoard (int trtint tcint dr,int int size)if (size = = 1) return；int t = tile + + ,/ L 型骨牌號s = size/2:/分割棋盤/覆蓋左上角子棋盤if (dr tr + s & de tc, s)；else /此棋盤中無特殊方格/用t號L型骨牌覆蓋右卜角board tr + s - 1 tc + s - 1 = t;/覆蓋其余方格chessBoard (tr tc, tr + s 1

2、tc + s - 1 s) ； /覆蓋右上角子棋盤if (dr tr + s & d = tc + s)/特殊方格在此棋盤中chessBoard (tr tc + s,drt = tr + s & dr tctr + tc + s - 1 s) ； /覆蓋右下角子棋盤if (dr = tr + s & de = tc + s)/特殊方格在此棋盤中法設(shè)計與分析chessBoard (tr + tc + s, Hr, s);dse /用t號L型骨牌覆蓋左上角tileboard ir + b tc + s = t；了入/覆蓋其余方格chessBoard (tr + s tc + tr + s tc

3、+ s s) ； size: 2，棋盤規(guī)格為2“ x2設(shè)TOO是算法chessBoard覆蓋一個2x2“棋盤所需的時間。從算法的分割策略 可知，仏)滿足如下遞歸方程：T2 =* =0(4TG - 1) + 0(1) /t 0解此遞歸方程可得TG) =0(4)。由于覆蓋2k x2J棋盤所需的L型骨牌個數(shù)為(- 1)/3,故算法chessBoard是個在漸近意義下最優(yōu)的算法。如果 f(n)=O(s(n)并且 g(n)=O(r(n),則 f(n)+g(n)=O(s(n)+r(n) 如果 f(n)=O(s(n)并且 g(n)=O(r(n),則 f(n)*g(n)=O(s(n)*r(n) 根據(jù)符號o的定

4、義，存在正常數(shù)C1, C2和自然數(shù)N1，N2,使得對所有的n=Ni, f (n) =N/g(n) =qr(n)所以 f (n) + g(n) = Cs(n)+qr(n), f (n) *g(n)= s(n)r(n)； 令 C3=max( C1,C2)， C4=C1*C2； 則：f (n) + g(n) = C3s(n)+ r(n)=O(s(n)+ r(n)f( n) *g(n) O時，將2*x2棋盤分割為4個x2A 子棋盤如圏2-石所示.迭代模型(算法)。(18分)圖2-6 棋盤分剛圖2-6 棋盤分剛特殊萬格必位于4個較小產(chǎn)棋盤之 中，英余3個r*其盤屮無特殊方格為了將 這3個無特殊力格的了棋

5、盤轉(zhuǎn)化為特殊棋盤，町以用-個L型丹牌覆施這3個較小機 盤的會O處，如圖2( 6)所示，這3個子棋盤上被L型皆牌槻歲的力格就成溝該棋盤 I：的特殊力格，從而將原r-j趣轉(zhuǎn)化為4個較小規(guī)模的棋麻覆豫問題遞)地使川這種 分割直至桃盤簡化為1 X I棋盤.struct node int low,high;St10000；void quickso廠七2(int data?int int t)int top=-l.,low.,high;top+;sttop.low=s;sttop.high=t; while(top-l)low=sttop.low;high=sttop.high; top-;int w;i

6、f(loww(v),則將v 從T刪除之后，T變?yōu)閮蓚€連同的分支，此時，一定有T的邊v1連同這兩個分支，否則T將是 不連通的。從而將v1加入到T中構(gòu)成一新的生成樹T =T-v+v1。且有w(v1)w(v )w(v),從而 w(T )=w(T-v+v1)w(T)。這與T為最小生成樹矛盾。證畢。據(jù)此利用prim算法或者Kruskal算法 算得 G 的最小生成樹即可1證明0-1背包問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)假設(shè)第k個物品是最優(yōu)解中的一個物品，則從中拿出Wk對應(yīng)的物品后所對應(yīng)的解一定是其余n-1回溯法貨郎擔(dān)問題的解空間是一棵排列樹令到第i層為止所構(gòu)早路徑的權(quán)和為：cw(i):X呱工丿一1，工川假設(shè)已經(jīng)知道部

7、分解d,盟2,.，心-1)，則從第i-l層節(jié)點選擇頂點孟i往下走的限界函數(shù)為: B (i) = cw(il) +wxi-l, xi若B(i) bestw,則停止搜索xi分枝及其下面void backtrack (int i) if (i 二二 n) Iif (axn - lxn MAX_VALUE & axn 1 MAX_VALUE &i(bestc = MAX_VALUE | cc+axn - 1xn+axn1bestc) for (int j = 1; j = n; j+) bestxtj = xj;ibestc = cc+axn - 1xn+axn1:else for (int j 二

8、i; j - n; j+)if (axi - MAX_VALUE(bestc = MAX_VALUE | | cc+axi - 1 x j bestc) / 搜索子樹第1行測試：如果i=n，表示已經(jīng)搜索到了葉節(jié)點。如果從xn-1到xn以及從xn到起點x1有一條邊，則找到了一條回路。此時，第3行需要判斷該回路是否是目前發(fā)現(xiàn)的最優(yōu)回路。如果是，第4行-6行則更新回路 的權(quán)和bestw以及最優(yōu)回路。第7-13行繼續(xù)回溯，在第8行，如果從xi-1到xj有一條邊，且B(i) 小于當前最優(yōu)解的值bestw，則表示可以繼續(xù)往下搜索，同時更新目前所構(gòu)造路徑的權(quán)值cw。 證明一個問題具有貪心選擇性質(zhì)的一般方法令

9、子問題S.H0且ai為子問題S.中的最優(yōu)解，則ai 一定包含在子問題S.中某個任務(wù)相互兼容的 ij1ij1ij最大子集中。TSP 問題此問題相當于在一個有向賦權(quán)圖中尋找一個最短的哈密頓回路。畑卩)=fmind)f6F lki + s(dk,V - dk)卩工 0Ili0 K = 0個物品，裝入背包最大承載重量為C-Wk的最優(yōu)解，否則與假設(shè)矛盾。2 對計算復(fù)雜性的研究能夠使人們弄清所求解問題的固有難度，并得出評價某類算法優(yōu)劣的準則， 用以指導(dǎo)設(shè)計出更高效的算法。試用簡短的語言說明“建立一個問題復(fù)雜性的下界要比確定它的 上界困難得多！”其復(fù)雜性上界是已知求解該問題的最快算法的費用，而復(fù)雜性下界只能

10、通過理論 證明來建立。尋求某個問題的計算復(fù)雜性上界，只要研究一個算法的復(fù)雜性即可。但是要尋求同一 問題的計算復(fù)雜性下界，則必須考察所有的解決該問題的算法，證明一個問題的復(fù)雜性下界就需要第i個頂點，假設(shè)推銷員從第0號點出發(fā)，調(diào)用s時就要傳入F -v：從；.出發(fā)，要到達的頂點的集合匸:1 ，：從出發(fā)，經(jīng)過v中各點，并僅經(jīng)過一次后，回到G：所需的最1.最大值和最小值問題的最優(yōu)算法：1.最大值和最小值問題的最優(yōu)算法：給定n個實數(shù)存放于一維數(shù)組A中，試設(shè)計一個算法在最壞證明不存在任何復(fù)雜性低于下界的算法。顯然，建立下界要比確定上界困難得多短路徑長度(：與目標點不直接連通，則記其路程為無窮大)情況下用3n

11、/2-2次的比較找出A中的最大值和最小值else smallj = ai; big j else smallj = ai; big j = ai十 1; ” Max = big0;Min = smalllO;!=1:i電g血g世計+) #找到最大值，比較 length1!次”Maxbigi) Max = bigi;pfor(int i=l;ismallj) Min =6.試設(shè)計在O(n)時間內(nèi)求得數(shù)組A1.n的中位數(shù)的算法。將n個輸入元素劃分成n/5(上取整)個組，每組5個元素，只可能有一個組不是5個元素。用任意 一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5(上取整)個。找出這n/5(上 取整)個元素的中位數(shù)。如果n/5(上取整)是偶數(shù)，就找它的2個中位數(shù)中較大的一個。第 i 種物品的重量第 i 種物品的價值理回(辿 length) “辿int bigaU:*-1big = new mtlength2: 用來存放較大的數(shù)心 small = new jntlength 2: 用來存放較小的數(shù)心 fbr(int 1=0 J=O:i=ai4-l)big|j = ai:smallj = ai+l:-：點i到j(luò)的距離廣義背包問題(從最大遞歸，決定每個放不放，價值增不增