※ 引述《walkwall (會走路的牆)》之銘言： : ※ 引述《Arton0306 (Ar藤)》之銘言： : : 現在有16個隊伍 要參加比賽 : : 這比賽是強弱分明的 強者必勝(有遞移律) : : 現在16隊強弱都不一樣 : : 那麼最少要比幾場才能「找出最強隊和最弱隊」 : : 先列個比法 : : 1.先兩兩分組比，贏的為勝部，輸的敗部，需8場 : : 2.勝部有8隊找出最強的，需7場 : : 3.敗部有8隊找出最弱的，需7場 : : 共22場， : : 請問有沒有辦法以更少的場數找出來？ : : 沒有的話可否證明？ : 首先, 定義隊伍狀態四種 : N-未比較 W-勝候選 L-敗候選 X-非第一也非最後 : 一開始當然所有隊伍都是處於N狀態, 而結束狀態則必須只有一W一L且其他為X : 然而N狀態的隊伍經過一次比較後, 只可能轉換成W或L, : W或L至少也要比一次後才可能轉為X : 因此我們可以把四狀態的資訊量分別定義為 N:0 W:1 L:1 X:2 : 從開始的狀態(N*16,資訊量0), 到結束的狀態(W*1+L*1+X*14, 資訊量30) : 要求出解共需30資訊量 : 接下來, 不管是什麼演算法, 如果資訊量無法到30, 就無法確定只剩一解 : 反過來說, 如果資訊量到30, 由於比較一次以後必然至少有一W, 所以就能確定只剩一解 : 所以現在的問題轉換成 "最少需幾次比較, 資訊量能到30?" : 假定有個最佳的演算法, 考慮每次比較能獲得的資訊量, : 演算法能控制的是選用哪兩個隊伍對戰, 但選定後用該組合的最低的資訊量考慮 : 這是因為所有演算法都應考慮其最差表現, 才知道最少可以幾次判斷出來 : 以你推文為例, 一次(W,N)的對戰組合, 有可能獲得1or2的資訊量, 最低為1 : 考量N,W,L,X四種狀態的對戰組合, 我們知道只有(N,N)的最低資訊量為2, : (W,L) (W,X) (L,X) (X,X)的最低資訊量為0, 其他最低為1 : 因此要達到最小次數, 就要盡量選(N,N), : 但是(N,N)每次配完後會少掉兩個N (一定一個變W一個變L), 所以(N,N)只能用8次 : 這樣資訊量達到16, 剩下的不管什麼猜法資訊量最多為1, 所以至少要14次 : 故8+14=22為最少對戰次數得證 感謝 但我還有個問題 NWLX四個狀態沒有誰比誰大的資訊 也就是如果用這4個狀態來表示某一連續的比較結果 會失去某些資訊 如現在只有abcd四隊 a比b後知a>b c比d後知c>d 若只用狀態來看 只知a,c為勝候勝 b,d為敗候選 失去了a>b c>d的資訊 也許有的演算法可以利用這樣的資訊 使得比較次數更少 這樣是不是還要再證明 這樣的資訊對任何算法都沒有幫助呢？ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.36.36.150