Re: [問題] 最強最弱的比賽場數
※ 引述《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
→
05/26 21:47, , 1F
05/26 21:47, 1F
→
05/26 21:48, , 2F
05/26 21:48, 2F
→
05/26 21:50, , 3F
05/26 21:50, 3F
→
05/26 21:50, , 4F
05/26 21:50, 4F
→
05/26 21:51, , 5F
05/26 21:51, 5F
推
05/26 22:41, , 6F
05/26 22:41, 6F
→
05/26 22:42, , 7F
05/26 22:42, 7F
→
05/26 22:42, , 8F
05/26 22:42, 8F
→
05/26 22:43, , 9F
05/26 22:43, 9F
→
05/26 23:59, , 10F
05/26 23:59, 10F
→
05/27 00:00, , 11F
05/27 00:00, 11F
→
05/27 00:01, , 12F
05/27 00:01, 12F
討論串 (同標題文章)