計(jì)算機(jī)算法基礎(chǔ)課后答案-文庫(kù)吧資料
2025-06-29 17:33本頁(yè)面
【正文】 eatrepeatrepeatfor i←1 to n do//輸出最優(yōu)路徑for j←1 to n doprint(“thepath of i to j is ”i )k←path(i, j)while k≠0 doprint(k)k←path(k, j)repeatrepeatrepeatend ShortestPath分析??時(shí)間復(fù)雜度第一個(gè)循環(huán)：O(n2)第一個(gè)循環(huán)：O(n3)第一個(gè)循環(huán)：O(n2)??空間復(fù)雜度Cost(n,n) A(n,n) Path(n,n)O(n2)P1513??對(duì)于標(biāo)識(shí)符集（a1,a2,a3,a4）=（end, goto, print, stop），已知成功檢索概率為P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20，不成功檢索概率為Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20，用算法OBST對(duì)其計(jì)算W(i,j)，R(i, j)和C(i, j)（0≤i, j≤4）。P1512??修改過程ALL_PATHS，使其輸出每對(duì)結(jié)點(diǎn)（i,j）間的最短路徑，這個(gè)新算法的時(shí)間和空間復(fù)雜度是多少？??回憶算法：P127 P131 P127 ??D(i,j)/D(j) :從節(jié)點(diǎn)j到匯點(diǎn)t的最優(yōu)路徑中下一個(gè)節(jié)點(diǎn)，即最優(yōu)路徑中j的后繼節(jié)點(diǎn)。因此TREE生成一棵關(guān)于(q1,q2,…,qn)的最優(yōu)歸并樹。于是在T’中如果用其權(quán)為q1+q2+…+qk的一個(gè)外部結(jié)點(diǎn)來代換T，則所生成的樹T’’是關(guān)于(T,qk+1,…,qn)的一棵最優(yōu)歸并樹。如果P的k個(gè)兒子不是q1,q2,…,qk，則可以用q1,q2,…,qk和P現(xiàn)在的兒子進(jìn)行交換，這樣不增加T’的帶權(quán)外部路徑長(zhǎng)度。于是q1,q2,…,qk可生成子樹T，設(shè)T’是一棵對(duì)于（q1,q2,…,qn）的最優(yōu)k元?dú)w并樹。??假定該算法對(duì)于（q1,q2,…,qm），其中m=(k1)s+1 (s≥0)，都生成一棵最優(yōu)樹，??則只需證明對(duì)于(q1,q2,…,qn)，其中n=(k1)(s+1)+1，也能生成最優(yōu)樹即可。(P111)??②當(dāng)（q1,q2,…,q11）=（3,7,8,9,15,16,18,20,23,25,28）時(shí)，畫出使用這一規(guī)則所得到的最優(yōu)3元?dú)w并樹。??n=7(p1,…, p7)=(3,5,20,18,1,6,30)(d1,…,d7)=(1,3,4,3,2,1,2)(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)，對(duì)應(yīng)的期限為(2,4,3,1,3,1,2)b=min{ n,max{d(i)} }=min{7,4 }=4P12311??①證明如果一棵樹的所有內(nèi)部節(jié)點(diǎn)的度都為k，則外部節(jié)點(diǎn)數(shù)n滿足n mod (k1)=1.??②證明對(duì)于滿足n mod (k1)=1的正整數(shù)n，存在一棵具有n個(gè)外部節(jié)點(diǎn)的k元樹T(在一棵k元樹中，每個(gè)節(jié)點(diǎn)的度至多為k)。??易證如果J中的作業(yè)能按上述規(guī)則處理，顯然J是可行解；??如果J是可行解，J中的作業(yè)根據(jù)時(shí)間期限的非降次序排列，得到i1i2…ik…in，并且按照這個(gè)順序，可以處理J中所有作業(yè)，而對(duì)這一序列中的任意作業(yè)ik，如果它的時(shí)間期限是dk，且時(shí)間片[dk1,dk]是空的，則分配之；若時(shí)間片[dk1，dk]非空，則向前找最大的非空[r1,r]時(shí)間片，1≤r≤dk因?yàn)镴是可行解，所以一定可以找到如此時(shí)間片。 P1239??①：當(dāng)且僅當(dāng)子集合J中的作業(yè)可以按下述規(guī)則處理時(shí)它表示一個(gè)可行解；如果J中的作業(yè)I還沒分配處理時(shí)間，則將它分配在時(shí)間片[a1，a]處理，其中a是使得1≤r≤di的最大整數(shù)r，且時(shí)間片[a1，a]是空的。假設(shè)σ’≠σ，那么令a是使ra≠ia的最小下標(biāo)，設(shè)rb=ia，顯然ba，在σ’中將ra與rb相交換，因?yàn)閐rb≤dra，顯然ra和rb可以按期完成作業(yè)，我們還要證明ra和rb之間的作業(yè)也能按期完成。下面證明如果J是可行解，σ =i1i2…ik使得J中的作業(yè)可以按照di1≤di2≤…≤din 序列排列而又不違反任何一個(gè)期限。這里，假定作業(yè)i的效益pi0，要用的處理時(shí)間ti0，限期di≥ti.??解：①根據(jù)pi的非增排序得到（p7, p3, p4, p6, p2, p1, p5）=(30,20,18,6,5,3,1)，對(duì)應(yīng)的期限為(2,4,3,1,3,1,2)，：(1)=7(2),(1)=7(2), J(2)=3(4)；(1)=7(2), J(2)=4(3),J(3)=3(4)；(1)=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)；??②。命題得證。①l:(4,1,2) f:(,)按li的非降序存放程序ERT=*1+*3+*7=6*4+*5+*7=②l:(16,1,2) f:(,)按fi的非增序存放程序ERT=*16+*17+*19=*1+*17+*19=證明結(jié)論③是正確的,證明如下：假設(shè)li1,li2,…,lin按照fi/li的非增次序存放，即fi1/li1≥fi2/li2≥…≥fin/lin，則得到ERT=[fi1li1+fi2(li1+li2)+…+fik(li1+li2+…+lik)+…+fin(li1+li2+…+lin)]/ 假設(shè)該問題的一個(gè)最優(yōu)解是按照j1,j2,…,jn的順序存放，并且其期望檢索式是ERT’，我們只需證明ERT≤ERT’，即可證明按照fi/li的非增次序存放得到的是最優(yōu)解。??②證明按fi的非增次序存放程序不一定得到最小的ERT。P1226．??假定要將長(zhǎng)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1