算法設(shè)計(jì)與分析答案參考

1、1、用Floyd算法求下圖每一對頂點(diǎn)之間的最短路徑長度，計(jì)算矩陣D0，D1，D2和D3，其中Dki, j表示從頂點(diǎn)i到頂點(diǎn)j的不經(jīng)過編號大于k的頂點(diǎn)的最短路徑長度。解在每條邊的矩陣行中依次加入頂點(diǎn)1,2,3，判斷有無最短路徑2、設(shè)有n=2k個運(yùn)動員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個滿足以下要求的比賽日程表：每個選手必須與其他n-1名選手比賽各一次；每個選手一天至多只能賽一次；循環(huán)賽要在最短時間內(nèi)完成。（1）如果n=2k，循環(huán)賽最少需要進(jìn)行幾天；1 2 3 4 5 6 7 82 1 4 3 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 8

2、7 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1（2）當(dāng)n=23=8時，請畫出循環(huán)賽日程表。解：（1）至少要進(jìn)行n天（2）如右圖：3、對于下圖使用Dijkstra算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑。 解：用V1表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與V1中某個頂點(diǎn)相鄰接且不在V1中的頂點(diǎn)；E1表示加入到最短路徑中的邊，E2為與V1中的頂點(diǎn)相鄰接且距離最短的路徑。步驟 V1 V2 E1 E21. a b ab2. a,b d ab bd3. a,b,d c,f ab,bd dc,df4. a,b,d,c f ab,bd df5. a,b,c,d,f e ab,bd,dc

3、,df fe6. a,b,c,d,e,f g ab,bd,dc,df,fe eg7. a,b,c,d,e,f,g h ab,bd,dc,df,fe,eg gh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 結(jié)果：從a到h的最短路徑為，權(quán)值為18。求所有頂點(diǎn)對之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點(diǎn)從a循環(huán)到h，每次求起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對之間的最短路徑。補(bǔ)充例題：求A到各個頂點(diǎn)的最短路徑：解：4、用動態(tài)規(guī)劃策略求解最長公共子序列問題： （1）給出計(jì)算最優(yōu)值的遞歸方程。 （2）給定兩個序列X=B,C,D,A，Y=A,B

4、,C,B，請采用動態(tài)規(guī)劃策略求出其最長公共子序列，要求給出過程。解：(1) （2）0 0 0 00 0 1 1 10 0 1 2 20 0 1 2 20 1 1 2 2 最長公共子序列：5、對下圖所示的連通網(wǎng)絡(luò)G，用克魯斯卡爾(Kruskal)算法求G的最小生成樹T,請寫出在算法執(zhí)行過程中，依次加入T的邊集TE中的邊。說明該算法的貪心策略和算法的基本思想，并簡要分析算法的12345618111715192126679時間復(fù)雜度。答：TE=(3,4), (2,3),(1,5),（4,6）（4,5） 貪心策略是每次都在連接兩個不同連通分量的邊中選權(quán)值最小的邊?；舅枷耄菏紫葘D中所有頂點(diǎn)都放到生成

5、樹中，然后每次都在連接兩個不同連通分量的邊中選權(quán)值最小的邊，將其放入生成樹中，直到生成樹中有n-1條邊。時間復(fù)雜度為：O(eloge) 6、快速排序算法對下列實(shí)例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。 A=(65,70,75,80,85,55,50,2)解：第一個分割元素為65(1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 665 2 50 55 85 80 75 70 4 655 70 75 80 85

6、65 50 27、對于下圖，寫出圖著色算法得出一種著色方案的過程。1342解： K1X1 1 , 返回 trueX21,返回false; X2X2+1=2, 返回 trueX31 ,返回false; X3X3+1=2, 返回false;X3X3+1=3, 返回 true X41, 返回false; X4X4+1=2, 返回false;X4X4+1=3, 返回 true找到一個解 （1，2，3，3）8、有n個物品，已知n=7, 利潤為P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容積M=15,物品只能選擇全部裝入背包或不裝入背包，設(shè)計(jì)貪心算法，并討論是否可

7、獲最優(yōu)解。解：定義結(jié)構(gòu)體數(shù)組G將物品編號、利潤、重量作為一個結(jié)構(gòu)體例如Gk=1,10,2 求最優(yōu)解按利潤/重量的遞減序有：5,6,1,6、1,10,2,56,18,4,9/2 、3,15,5,3 、7,3,1,3、2,5,3,5/3 、4,7,7,1 算法： procedure KNAPSACK(P W M X n) /P(1 n)和W(1 n)分別含有按P(i)/W(i)P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小而x(1n)是解向量/ real P(1 n) W(1 n) X(1 n) M cu integer i n X0 /將解向量初始化為零/ cuM /

8、cu是背包剩余容量/ for i1 to n do if W(i)>cu then exit endif X(i) 1 cucu-W(i) repeat end GREEDY-KNAPSACK 根據(jù)算法得出的解：X=1,1,1,1,1,0,0獲利潤52 而解1,1,1,1, 0, 1,0可獲利潤54 ，因此貪心法不一定獲得最優(yōu)解。9、排序和查找是經(jīng)常遇到的問題。按照要求完成以下各題： （1） 對數(shù)組A=15，29，135，18，32，1，27，25，5，用快速排序方法將其排成遞減序。（2） 給出上述算法的遞歸算法。（3） 使用上述算法對（1）所得到的結(jié)果搜索如下元素，并給出搜索過程：18

9、，31，135。解：（1）第一步：15 29 135 18 32 1 27 25 5 第二步：29 135 18 32 27 25 15 1 5第三步：135 32 29 18 27 25 15 5 1第四步：135 32 29 27 25 18 15 5 1（2）輸入：遞減數(shù)組Aleft:right，待搜索元素v。輸出：v在A中的位置pos，或者不在A中的消息（-1）。步驟：int BinarySearch(int A,int left,int right,int v)int mid;if (left<=right)mid=int(left+right)/2);if (v=Amid)

10、return mid;else if (v>Amid) return BinarySearch(A,left,mid-1,v);else return BinarySearch(A,mid+1,right,v);elsereturn -1;（3）搜索18：首先與27比較，18<27，在后半部分搜索；再次與18比較，搜索到，返回5。 搜索31：首先與27比較，31>27，在前半部分搜索；再次32比較，31<32，在后半部分搜索，與29比較，31>29，此時只有一個元素，未找到，返回-1。 搜索135：首先與27比較，135>27，在前半部分搜索；再次32比較，135>32，在前半部分搜索；與135比較，相同，返回0。10、假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹。物品ABCDEFG重量35306050401025價值10403050354030解：（1）求所有頂點(diǎn)對之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點(diǎn)從a循環(huán)到h，每次求起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對之間的最短路徑。（2