PTT遊戲區 / puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)

[益智遊戲] 親緣樹

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 ( 在他方 )時間16年前 (2009/05/31 11:21), 編輯推噓11(11推 0噓 13→)
留言24則, 4人參與, 最新討論串1/4 (看更多)
[簡介] 在生物資訊中，其中一個關心的問題就是如何還原重建出物種的演化樹(如下圖)。 從此演化樹中，任取三個我們可以看出哪兩個有比較近的親緣關係。 例如： 取 A,B,C 來看，知 A,C 的親緣較近，B 和另兩個較遠，將之記作 [(A,C),B]。 取 C,D,E 來看，知 C,D 的親緣較近，E 和另兩個較遠，將之記作 [(C,D),E]。 ╱╲ ╱╲ ╲ ╱ ╲ ╲ ╱ ╱╲ ╲ ╱╲ ╱ ╱╲ ╲ A C B D F E 當然，有了演化樹，我們要得出親緣關係，是很容易。 但反之，若我們只有親緣關係，要如何重建演化樹呢？ (在實際問題中，因實驗會有誤差，有時有一小部分的關係是錯誤的， 如何在允許部分錯誤下去還原整個樹更是複雜的問題) [遊戲規則] (基本版) 1. 兩人先各自劃一個演化樹(可依難易度調整遊戲的物種數目)， 2. 每回合兩人輪流詢問對方一個[三物種的親緣關係]， 3. 被詢問者要回答哪兩個物種關係較近。 4. 重複 2.3 的情況，直到有一方宣稱他已經重建整個演化樹。 若公布結果時，其答案為正確，則為勝，否者為輸。 [遊戲規則] (進階版) 在 3. 中，允許至多一次說謊的機會。 [暖身練習] 已知 6 物種的親緣關係如下： [(A,B),C], [(C,D),B)] , [(C,D),E], [(D,E),F], [(A,E),F] 你有辦法重建，唯一的演化樹嗎? 若還不為一，你會想要再詢問哪三個物種關係呢? [益智問題] 若在6個物種下，有辦法確定幾次內衣定可以得出答案呢? (有Error, 和沒 Error 的情況各為何?) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.231.45
→
05/31 11:21, , 1F
想找人試玩的可以丟我水球
05/31 11:21, 1F
推
05/31 23:57, , 2F
請問原PO的舉例中
05/31 23:57, 2F
→
05/31 23:57, , 3F
BDF誰比較近?一樣嗎?
05/31 23:57, 3F
→
05/31 23:58, , 4F
咦等等－　－ａ
05/31 23:58, 4F
→
06/01 00:00, , 5F
沒事我瞭了XD(請無視我XD)
06/01 00:00, 5F
推
06/01 00:10, , 6F
呃好像還是有疑問XD
06/01 00:10, 6F
→
06/01 00:11, , 7F
呃我又沒問題了.................呃我糊塗了XD
06/01 00:11, 7F
推
06/01 00:13, , 8F
(無限鬼打牆ing....XD)
06/01 00:13, 8F
推
06/01 00:32, , 9F
暖身我無法推出.......問ABE親源?
06/01 00:32, 9F
推
06/01 18:05, , 10F
暖身題跟樓上一樣之問ABE親緣?
06/01 18:05, 10F
推
06/01 18:10, , 11F
第一個例子的C,D,E我沒有弄懂...他們都是五等親不是嗎?
06/01 18:10, 11F
推
06/01 18:11, , 12F
好像應該是[(C,E),D]才對......
06/01 18:11, 12F
推
06/01 18:23, , 13F
延伸交點
06/01 18:23, 13F
→
06/01 21:59, , 14F
CD 的親緣比較近， CE 的親緣比較遠 是 [(C,D),E] 沒錯
06/01 21:59, 14F
→
06/01 22:00, , 15F
E 在一開始就和 {A,B,C,D,F} 分化了，所以E 距大家都很遠
06/01 22:00, 15F
→
06/01 22:01, , 16F
接著 {A,B,C,D,F} 又分化為 {A,C} {B,D,F} 兩堆
06/01 22:01, 16F
→
06/01 22:13, , 17F
暖身題加 [(A,E),B]則解為 ((((A,E),B),(C,D)),F)
06/01 22:13, 17F
→
06/01 22:14, , 18F
若再加 [(A,B),E] 則解還不唯一
06/01 22:14, 18F
※ 編輯: arist 來自: 140.112.231.45 (06/01 22:15) ※ 編輯: arist 來自: 140.112.231.45 (06/01 22:21)
推
06/01 22:42, , 19F
暖身再問BCE
06/01 22:42, 19F
→
06/01 22:43, , 20F
呃我是指如果是[(A,B),E]
06/01 22:43, 20F
推
06/01 22:44, , 21F
想很久還是無法理解@@" 我先留給其他人做，自己以後再說吧
06/01 22:44, 21F
推
06/02 22:32, , 22F
好像只差[A或B 與 C或D 與 E]了........
06/02 22:32, 22F
→
06/02 23:06, , 23F
那暖身題只是熟悉一下規則
06/02 23:06, 23F
→
06/02 23:07, , 24F
實際雙人玩時，要怎樣來問親緣關係是個比較有趣的問題
06/02 23:07, 24F
‣ 更多 arist 的文章
文章代碼(AID): #1A8VUiAg (puzzle)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 4 篇)：
排序： 最新先 | 最舊先 | 留言數
11
24
[益智遊戲] 親緣樹
arist
16年前, 05/31
在新視窗開啟完整討論串 (共4篇)
puzzle 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 arist 的文章
文章代碼(AID): #1A8VUiAg (puzzle)