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

[newpuma (還很新)]

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
推 yupog2003: 應該是kruskal無誤，要改efficency我只寫得出用heap排
→ yupog2003: 序edge，然後detect cycle的find用path compression，
→ yupog2003: 可是這些好像本來就是這樣做...
→ yupog2003: MTTF of the system as whole是說一個component壞掉
→ yupog2003: ，整個system就算fail嗎？如果是的話我會寫1000/12 FIT
→ yupog2003: 我也不知道那個FIT是什麼...也不知道該怎麼辦只能這樣
→ ken52011219: 這不是kruskal呀
→ ken52011219: 這是kruskal的前身觀念 找safe邊
→ ken52011219: New大真的火力全開 三點po文0.0....
其實是白天在睡
推 yupog2003: 已震懾我方軍心...
別這樣 我問得問題都很蠢=_=
→ ken52011219: 講一下差別好了，這個code 與kruskal 和prim最大的差
→ ken52011219: 別是效率問題
→ ken52011219: 這個前置MST Code 並沒有有效尋找為safe邊的code
→ ken52011219: 而kruskal 運用的是union的概念（find set , make se
→ ken52011219: t ,union)
→ ken52011219: Prim則是 使用 heap的概念（ extract min, build hea
→ ken52011219: p , decrease key)
→ ken52011219: 來尋找最小cost的 safe edge
→ yupog2003: 那如果第4行，也就是：if ((v,w) does not create a
→ yupog2003: cycle in T)使用Find-Set下去判斷，而T=T∪(v,w)使用
→ yupog2003: union的話，這樣可以說這個algo是kruskal嗎？
→ yupog2003: 也就是說這個code找MST的邏輯跟kruskal很像，但他沒有
→ yupog2003: 採用kruskal所採用之有效率的方法，所以不算kruskal?
→ ken52011219: 我記得沒錯了話kruskal 還需要排序邊的大小 這樣才
→ ken52011219: 能更為凸現與這題的差異
推 krusnoopy: http://i.imgur.com/nH0z18z.jpg
→ yupog2003: oh對，他的寫法是每次找最小，kruskal是已經排序好，每
→ krusnoopy: 這是我從horowitz上面抄下來的
→ yupog2003: 次pop出最小的，那這樣這題感覺把kruskal的一些精神代
→ ken52011219: 否則原題意 尋找min cost edge 每次刪去後需要重新
→ ken52011219: 排列 O(n^2*n次）的時間
→ yupog2003: 進去應該就算是增加efficiency的方法了
→ ken52011219: 史努比大的幾乎一模一樣耶..我觀念要崩潰了嗎Orz
推 krusnoopy: 加速應該是指while只要MST有n-1條邊就可以停止
→ krusnoopy: 你的disjoint set是在if(v,w)不含cycle那邊實做的
→ yupog2003: kruskal史努比大
→ krusnoopy: 所以有用到disjoint set
→ yupog2003: 都沒想到還有|E|=|V|-1這個判斷式可以幫助我們
→ ken52011219: 等等
→ krusnoopy: http://i.imgur.com/UyIgYgz.jpg
→ krusnoopy: 順便貼個prim
→ ken52011219: 我立馬上網查了horowitz 的確有這個演算法
→ ken52011219: http://imgur.com/a/Gn65q
→ ken52011219: 但這跟我說的一模一樣，並沒有衝突 這個CODE是它的
→ ken52011219: 前身，而不是 kruskal 現行的概念
→ krusnoopy: 我在C語言版本沒看到他有實做出來,這是C++的嗎？
→ yupog2003: 看那個語法有點像pascal?
→ yupog2003: 感覺如果真的是這樣那就考好細，|V|-1就停一定可以是答
→ yupog2003: 案就是了，再寫出find-set跟union應該也是對的
→ ken52011219: 我大概理解史努比大所表達的，這好像是不同的聖經本
→ ken52011219: 所各自表達的解法不同（？
→ ken52011219: 因為我有看到horowitz該章節內有提到snoopy大所說的
→ ken52011219: 點
→ ken52011219: 順便說我找的是第二版 雖然我沒有在看這本的習慣@@
→ ken52011219:  但應該不會分c or c++吧
→ yupog2003: 有分c和c++喔！我的也是c，當工具書
→ krusnoopy: 作者說那是虛擬碼,所以實做不一樣還是kruskal
→ ken52011219: 了解，我覺得這題應該會跟 horowitz 的 kruskal 的
→ ken52011219: 念相像，這題還是依horowitz的原文為主比較好
→ ken52011219: 請無視我上面的回覆，依循horowitz 的CODE為主
→ ken52011219: 感謝 史奴比大大 ~
※ 編輯: newpuma (223.137.200.66), 01/25/2017 12:33:11