[理工] 台科資概103 最小生成樹、MTTF、SJF

看板Grad-ProbAsk作者 (還很新)時間9年前 (2017/01/25 03:05), 9年前編輯推噓4(4推 0噓 57→)
留言61則, 3人參與, 最新討論串1/1
http://i.imgur.com/4zCcxjd.jpg
題目給這樣子，這應該是kruskal無誤吧 如果要改的更efficiency 要把整個程式碼改成prim嗎？ http://i.imgur.com/itZfpg5.jpg
這題的MTTF完全看不出來要從哪邊得來，FIT是一個時間單位嗎？ http://i.imgur.com/3qwbp28.jpg
這題完全沒給α定義 我是default成 π2=αt1+(1-α)π1 5=αx6+(1-α)x1 解得一個α 但是代π3好像又會得到不同α？ 感謝看完 先謝謝大家了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.200.66 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485284734.A.5EF.html
推
01/25 07:18, , 1F
應該是kruskal無誤，要改efficency我只寫得出用heap排
01/25 07:18, 1F
→
01/25 07:18, , 2F
序edge，然後detect cycle的find用path compression，
01/25 07:18, 2F
→
01/25 07:18, , 3F
可是這些好像本來就是這樣做...
01/25 07:18, 3F
→
01/25 07:20, , 4F
MTTF of the system as whole是說一個component壞掉
01/25 07:20, 4F
→
01/25 07:21, , 5F
，整個system就算fail嗎？如果是的話我會寫1000/12 FIT
01/25 07:21, 5F
→
01/25 07:22, , 6F
我也不知道那個FIT是什麼...也不知道該怎麼辦只能這樣
01/25 07:22, 6F
→
01/25 08:16, , 7F
這不是kruskal呀
01/25 08:16, 7F
→
01/25 08:19, , 8F
這是kruskal的前身觀念 找safe邊
01/25 08:19, 8F
→
01/25 08:24, , 9F
New大真的火力全開 三點po文0.0....
01/25 08:24, 9F
其實是白天在睡
推
01/25 08:26, , 10F
已震懾我方軍心...
01/25 08:26, 10F
別這樣 我問得問題都很蠢=_=
→
01/25 09:47, , 11F
講一下差別好了，這個code 與kruskal 和prim最大的差
01/25 09:47, 11F
→
01/25 09:47, , 12F
別是效率問題
01/25 09:47, 12F
→
01/25 09:49, , 13F
這個前置MST Code 並沒有有效尋找為safe邊的code
01/25 09:49, 13F
→
01/25 09:50, , 14F
而kruskal 運用的是union的概念（find set , make se
01/25 09:50, 14F
→
01/25 09:50, , 15F
t ,union)
01/25 09:50, 15F
→
01/25 09:51, , 16F
Prim則是 使用 heap的概念（ extract min, build hea
01/25 09:51, 16F
→
01/25 09:51, , 17F
p , decrease key)
01/25 09:51, 17F
→
01/25 09:52, , 18F
來尋找最小cost的 safe edge
01/25 09:52, 18F
→
01/25 10:04, , 19F
那如果第4行，也就是：if ((v,w) does not create a
01/25 10:04, 19F
→
01/25 10:05, , 20F
cycle in T)使用Find-Set下去判斷，而T=T∪(v,w)使用
01/25 10:05, 20F
→
01/25 10:05, , 21F
union的話，這樣可以說這個algo是kruskal嗎？
01/25 10:05, 21F
→
01/25 10:09, , 22F
也就是說這個code找MST的邏輯跟kruskal很像，但他沒有
01/25 10:09, 22F
→
01/25 10:09, , 23F
採用kruskal所採用之有效率的方法，所以不算kruskal?
01/25 10:09, 23F
→
01/25 10:10, , 24F
我記得沒錯了話kruskal 還需要排序邊的大小 這樣才
01/25 10:10, 24F
→
01/25 10:10, , 25F
能更為凸現與這題的差異
01/25 10:10, 25F
推
01/25 10:12, , 26F
01/25 10:12, 26F
→
01/25 10:12, , 27F
oh對，他的寫法是每次找最小，kruskal是已經排序好，每
01/25 10:12, 27F
→
01/25 10:12, , 28F
這是我從horowitz上面抄下來的
01/25 10:12, 28F
→
01/25 10:12, , 29F
次pop出最小的，那這樣這題感覺把kruskal的一些精神代
01/25 10:12, 29F
→
01/25 10:13, , 30F
否則原題意 尋找min cost edge 每次刪去後需要重新
01/25 10:13, 30F
→
01/25 10:13, , 31F
排列 O(n^2*n次）的時間
01/25 10:13, 31F
→
01/25 10:13, , 32F
進去應該就算是增加efficiency的方法了
01/25 10:13, 32F
→
01/25 10:14, , 33F
史努比大的幾乎一模一樣耶..我觀念要崩潰了嗎Orz
01/25 10:14, 33F
推
01/25 10:14, , 34F
加速應該是指while只要MST有n-1條邊就可以停止
01/25 10:14, 34F
→
01/25 10:15, , 35F
你的disjoint set是在if(v,w)不含cycle那邊實做的
01/25 10:15, 35F
→
01/25 10:15, , 36F
kruskal史努比大
01/25 10:15, 36F
→
01/25 10:15, , 37F
所以有用到disjoint set
01/25 10:15, 37F
→
01/25 10:18, , 38F
都沒想到還有|E|=|V|-1這個判斷式可以幫助我們
01/25 10:18, 38F
→
01/25 10:19, , 39F
等等
01/25 10:19, 39F
→
01/25 10:20, , 40F
01/25 10:20, 40F
→
01/25 10:20, , 41F
順便貼個prim
01/25 10:20, 41F
→
01/25 10:20, , 42F
我立馬上網查了horowitz 的確有這個演算法
01/25 10:20, 42F
→
01/25 10:21, , 43F
01/25 10:21, 43F
→
01/25 10:22, , 44F
但這跟我說的一模一樣，並沒有衝突 這個CODE是它的
01/25 10:22, 44F
→
01/25 10:23, , 45F
前身，而不是 kruskal 現行的概念
01/25 10:23, 45F
→
01/25 10:23, , 46F
我在C語言版本沒看到他有實做出來,這是C++的嗎？
01/25 10:23, 46F
→
01/25 10:25, , 47F
看那個語法有點像pascal?
01/25 10:25, 47F
→
01/25 10:26, , 48F
感覺如果真的是這樣那就考好細，|V|-1就停一定可以是答
01/25 10:26, 48F
→
01/25 10:27, , 49F
案就是了，再寫出find-set跟union應該也是對的
01/25 10:27, 49F
→
01/25 10:32, , 50F
我大概理解史努比大所表達的，這好像是不同的聖經本
01/25 10:32, 50F
→
01/25 10:32, , 51F
所各自表達的解法不同（？
01/25 10:32, 51F
→
01/25 10:33, , 52F
因為我有看到horowitz該章節內有提到snoopy大所說的
01/25 10:33, 52F
→
01/25 10:33, , 53F
點
01/25 10:33, 53F
→
01/25 10:36, , 54F
順便說我找的是第二版 雖然我沒有在看這本的習慣@@
01/25 10:36, 54F
→
01/25 10:36, , 55F
但應該不會分c or c++吧
01/25 10:36, 55F
→
01/25 10:38, , 56F
有分c和c++喔！我的也是c，當工具書
01/25 10:38, 56F
→
01/25 10:40, , 57F
作者說那是虛擬碼,所以實做不一樣還是kruskal
01/25 10:40, 57F
→
01/25 10:43, , 58F
了解，我覺得這題應該會跟 horowitz 的 kruskal 的
01/25 10:43, 58F
→
01/25 10:44, , 59F
念相像，這題還是依horowitz的原文為主比較好
01/25 10:44, 59F
→
01/25 10:45, , 60F
請無視我上面的回覆，依循horowitz 的CODE為主
01/25 10:45, 60F
→
01/25 10:45, , 61F
感謝 史奴比大大 ~
01/25 10:45, 61F
※ 編輯: newpuma (223.137.200.66), 01/25/2017 12:33:11
‣ 更多 newpuma 的文章
文章代碼(AID): #1OXwL-Nl (Grad-ProbAsk)