[益智遊戲] 親緣樹

[arist ( 在他方 )]

[簡介] 

在生物資訊中，其中一個關心的問題就是如何還原重建出物種的演化樹(如下圖)。
從此演化樹中，任取三個我們可以看出哪兩個有比較近的親緣關係。

例如：
取 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
→ arist:想找人試玩的可以丟我水球
推 newacc:請問原PO的舉例中
→ newacc:BDF誰比較近?一樣嗎?
→ newacc:咦等等－　－ａ
→ newacc:沒事我瞭了XD(請無視我XD)
推 newacc:呃好像還是有疑問XD
→ newacc:呃我又沒問題了.................呃我糊塗了XD
推 newacc:(無限鬼打牆ing....XD)
推 newacc:暖身我無法推出.......問ABE親源?
推 chyrliin: 暖身題跟樓上一樣之問ABE親緣?
推 puzzlez:第一個例子的C,D,E我沒有弄懂...他們都是五等親不是嗎?
推 puzzlez:好像應該是[(C,E),D]才對......
推 chyrliin:延伸交點
→ arist:CD 的親緣比較近， CE 的親緣比較遠 是 [(C,D),E] 沒錯
→ arist:E 在一開始就和 {A,B,C,D,F} 分化了，所以E 距大家都很遠
→ arist:接著 {A,B,C,D,F} 又分化為 {A,C}  {B,D,F} 兩堆
→ arist:暖身題加 [(A,E),B]則解為  ((((A,E),B),(C,D)),F)
→ arist:若再加 [(A,B),E] 則解還不唯一
※ 編輯: arist           來自: 140.112.231.45       (06/01 22:15)
※ 編輯: arist           來自: 140.112.231.45       (06/01 22:21)
推 newacc:暖身再問BCE
→ newacc:呃我是指如果是[(A,B),E]
推 puzzlez:想很久還是無法理解@@" 我先留給其他人做，自己以後再說吧
推 puzzlez:好像只差[A或B 與 C或D 與 E]了........
→ arist:那暖身題只是熟悉一下規則
→ arist:實際雙人玩時，要怎樣來問親緣關係是個比較有趣的問題