演算法作業09
第1題: 最短路徑
請使用Branch-and-Bound找出下圖中,S到T的最短路徑。請畫出Branch-and-Bound圖,並標示各點的cost,以及被bound住的地方。(可參考ppt20頁)
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
hill climbing
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
如果Bound會更新的話
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
如果Bound不會更新的話
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
GIF太大傳不上來QQ
第2題: Personnel Assignment Problem
- 已知5個工作(\(j_1,…,j_5\)),其先後關係為:\(j_1\to j_3 , j_3 \to j_4 , j_2 \to j_5\),分配給5個人員(\(p_1,…,p_5\))
- 每人分配一個工作,且當\(j_a < j_b\) ,須要 \(p_a < p_b\)。
- 請使用Branch-and-Bound找出最少費用的人員工作分配。
提煉cost matrix
原始矩陣
\(\begin{bmatrix}
17 & 13 & 4 & 23 & 12\\
32 & 30 & 45 & 19 & 31\\
7 & 11 & 12 & 3 & 15 \\
10 & 17 & 13 & 9 & 11\\
8 & 19 & 9 & 6 & 7
\end{bmatrix}\)
橫排提煉後
\(\begin{bmatrix}
13 & 9 & 0 & 19 & 8\\
13 & 11 & 26 & 0 & 12\\
4 & 8 & 9 & 0 & 12 \\
1 & 8 & 4 & 0 & 2\\
2 & 13 & 3 & 0 & 1
\end{bmatrix}\)
4+19+3+9+6 = 41
直排提煉後
\(\begin{bmatrix}
12 & 1 & 0 & 19 & 7\\
12 & 3 & 26 & 0 & 11\\
3 & 0 & 9 & 0 & 11 \\
0 & 0 & 4 & 0 & 1\\
1 & 5 & 3 & 0 & 0
\end{bmatrix}\)
41 + (1+8+1) = 51
基本成本就是51
稍微畫個拓樸排序 等等可以對照
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
B&B結果
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
第3題: Traveling Salesperson Optimization Problem
- 在ppt34頁中,該例首先以4-6將所有feasible solution分為兩集合。
- 現在,將原例的4-6改以6-7來作區分,接著再以3-5作區分,如下圖所示:
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
- 請計算出圖中每個紅框的lower bound,並列出reduced matrix。
原始reduced matrix
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
lower bound = 96
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
lower bound = 96 + 0 = 96
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
把7-6改成無限、把第7欄刪掉
因為第6列有一個0了,所以不用縮減
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
lower bound = 96 + 0 + 5 = 101
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
lower bound = 96 + 0 = 96
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
把5-3改成無限、把第5欄刪掉
因為第5列有一個0了,所以不用縮減
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
lower bound = 96 + 1 + 17 = 114
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
每個的lower bound
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
第4題: 左右反轉二元樹
解題思路
左右子樹的結點都翻一次
整棵樹就翻過來了
寫個遞迴給他左右翻轉
蠻簡單的
程式碼
測試輸出輸入的畫面截圖
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
花費時間
9分鐘
完成程度
完全自己解出
第5題:
解題思路
因為二元搜尋樹的中序就是從小排到大
中序跑一次就好,全域變數紀錄跑到第幾個這樣
程式碼
測試輸出輸入的畫面截圖

花費時間
5分鐘
完成程度
完全自己解出
第6題:
解題思路
紀錄目前遇到的最深的節點
如果遇到更深的,就把LD
更新、把sum歸零,並把點的數值加到sum
如果遇到跟最深的一樣深,就把點的數值加到sum
程式碼
測試輸出輸入的畫面截圖

花費時間
10分鐘
完成程度
完全自己解出
心得:
已填