下圖為甲市之街道圖，其中點A, B, ..., Y 等路口，線段 AB, AC, ..., TY等為街道，其旁邊之數字為相鄰路口之距離(m)，所有街道都是雙向道
每天晚上9點鐘起，警車乙由路口B出發，沿著cycle B-D-H-N-X-M-L-K-J-E-B 以30km/hr前進，每到一路口便停留10分鐘對所有經過該路口之車輛進行酒測臨檢，直到次日早上6點鐘。每天晚上10點鐘起，警車丙由路口S出發，沿著cycle S-M-X-V-W-O-G-C-D-I-L-R-S 以36km/hr前進，每到一路口便停留15分鐘對所有經過該路口之車輛進行酒測臨檢，直到次日早上7點鐘。
今有丁君於某日晚上10點鐘要由路口A開車以時速48公里到路口Y，當時酒精濃度為1.0單位，若酒精濃度在人體內以每分鐘0.01單位速率降低，甲市規定凡被酒測臨檢發現酒精濃度大於等於0.25單位皆會被立即扣留24小時
(a)(10%) 請算出丁君最快何時到達路口Y
(b)(15%) 請提出適當的演算法來解決問題
//內心的OS: 叫計程車應該最快，可是出題教授硬要別人酒駕。
二、(91成大) 有限狀態機苦手..
三、Kruskal’s proof of correctness (紅色處不能理解..)
Let T’ be a minimum spanning tree
Let T be a tree formed by Kruskal’s algorithm that utilizes edges in T’
whenever a tie needs to be broken
Assumption: T has weight greater than T’
(otherwise Kruskal’s algorithm has produced an optimal solution)
Let e be the smallest weight edge in T that is not in T’
Add e to T’ and consider the cycle CY that is formed
There must be some edge e’ on cycle CY that has weight greater than e (Why?)
Replace e’ by e in T’
We have a new spanning tree T’’ and this new spanning tree has smaller weight
This contradicts the fact that T’ was a minimum spanning tree
四、
五、
六、
5 則留言:
1. 你可以觀察一下, 其實在路上的時間很短, 警車大部分的時間都會停留在檢查哨, 所以其實你用最 greedy 的方法走, 再稍微調整一下, 就不難算出他的最短路徑
因為乙車9:00就出發了, 等到10:00時他才剛過 M, 要繞回市中心還要很久, 所以基本上可以不用理它, 至於丙車就要比較留意了, 因為他在10:00由 S 出發後不到 1 分鐘就會停在 M 路口 15 分鐘, 所以如果丁君用最貪心的方式走 ABDIM 這樣的路線那麼他在 10:05 左右就會在 M 被堵到, 而如果我們選擇在 I 時就右轉, 之後就都不會被抓包了, 那麼最短路徑應該就是 ABDIXUTY, 總共花 7.375 分鐘就可以抵達
這種heuristic的演算法想法上應該可以有很多種, 所以演算法怎麼設計留給你了, 你也可以用類似上面的策略來處理
2. 我用 Mealy model 畫出來有 9 個 states, 大概就是先用 3 個 states 來處理一開始的 000, 然後後面有 6 個 states 主要是因為要用來分別出 consecutive 的 111 和奇數偶數不同 output 的這些可能, 你若仔細分析一下要記錄的東西, 就應該可以畫得出來了
3. 因為 Kruskal's algorithm 在每一輪都會先從最小的邊開始取, 除非有出現cycle, 所以在 CY 中因為一定還有沒被 T 取到的邊, 則那個邊的 weight 就一定會比 e 大
至於 4, 5, 6 最後這三個同年交大的考古題, 之前也有同學問過, 請你參考下面的link:
http://zjhwang.blogspot.com/2010/01/blog-post_10.html
請問助教:
關於問題三，這個這個..
如果考慮一個正五邊形(V,E),E={1,2,3,4,5}
依它所說，因為T'是MST，E'應該為{1,2,3,4}
又T''be a tree formed by Kruskal’s algorithm，E''也應該為{1,2,3,4}
那麼證明中 " Let e be the smallest weight edge in T'' that is not in T' " 的e在這邊好像找不到..?
關於問題三,我想一開始是假設
若找出的MST不等於Kruskal's所找出
的MST才有以下那些證明,因為也可能
找出和Kruskal's演算法找出相同的MST
我的意思比較像這樣
MST沒挑的邊特質應該為
1.會造成cycle
2.weight太大
執行Kruskal's Algo時
也不會抓到上面那兩種邊
它的假設＂T has weight greater than T’(MST)＂沒意見
可是＂There must be some edge e’(MST) on cycle CY that has weight greater than e＂
不在T’的邊不是應該都至少大於等於MST上的邊嗎?
因此有點confuse有e可以替換e’然後產生＂new spanning tree has smaller weight＂
i.e G(V,E),V={a,b,c,d,e}
ab=1, bc=3, cd=4, de=5, ea=1, be=2, bd=6共七個邊
那麼MST的邊就為{1,1,3,4}
Kruskal應該也是會挑{1,1,3,4}
否則根據假設挑了{1,1,3,5}
這時候5不在MST中..
你可以再想一下這些概念: mst 不一定唯一, 具最小 weight 的邊不一定要在一個 mst 裡; 或者我們換個角度看 Kruskal's algorithm, 他會取到的在cycle中的邊都是該cycle中weight最小的那幾個邊, 這就是為什麼他會說 T' 中一定會有 weight 較大的邊 e' 可以被 e 替換
當你的例子和他的假設不符時, 在這邊就不適用, 你可能會覺得怪怪的是因為理論上這件事本來就不可能發生, 也就是說你其實不可能找到一個反例來想這件事情時, 因為利用 Kruskal 演算法找出來的不會不是 mst, 然而一旦你舉的例子中 T 和 T' 的 weight 總和相同, 就不能用這個例子來討論他後面寫的那些事情
張貼留言