Re: [理工] 100中央(DS&ALGO)

看板Grad-ProbAsk作者Byzantin (拜占庭)時間14年前 (2012/01/12 20:42)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串3/4 (看更多)

純分享第五題 5.1 ETSP的cycle C*即為weight最小之hamiltonian cycle 而hamiltonian cycle去掉任一邊即為spanning tree 所以 weight of minimum spanning tree T* <= weight of minimum hamiltonian cycle C* 即w(T*) <= w(C*) 得證 5.2 先找出一MST T*，接著繞一圈(每個edge走兩遍，類似將tree包起來) A / \ B C 舉上圖為例來說就是A→B→A→C→A 這樣的weight為2w(T*) 接著轉換成hamiltonian cycle C 即若有重複走過之noded則跳過以上圖來說即為A→B→C→A 根據triangle inequality，這樣的cost一定比較小所以w(C) <= 2w(T*) , 且w(C*) <= w(C) 由5.1知w(T*) <= w(C*) 因此w(C*) <= w(C) <= 2w(C*) , 得證 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.104.205 ※ 編輯: Byzantin 來自: 118.169.104.205 (01/12 20:44)

推

RdMax

01/26 00:00, , 1^F

01/26 00:00, 1^F

推

cancj06

02/11 16:07, , 2^F

02/11 16:07, 2^F

‣ 返回看板[ Grad-ProbAsk ] 研究

‣ 更多 Byzantin 的文章

文章代碼(AID): #1F3jLIan (Grad-ProbAsk)