穷举法

Malacology留言 | 贡献2024年1月19日 (五) 09:18的版本 (init)
(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

矩阵

在 Farris 1970 之前对树结构进行穷举的方法

如果有一个矩阵,字母是阶元 (taxa) 数字是性状 (character),对于数字,每一列是一个 character

A 00
B 11
C 10
D 02


内部节点穷举

假设目前得到了一个树(A (B (C D))) 那么对于性状1来说,内部节点的可能性就如下

0

A(0)

0

B(1)

0

C(1)

D(0)

0

A(0)

0

B(1)

1

C(1)

D(0)

0

A(0)

1

B(1)

0

C(1)

D(0)

1

A(0)

0

B(1)

0

C(1)

D(0)

0

A(0)

1

B(1)

1

C(1)

D(0)

1

A(0)

0

B(1)

1

C(1)

D(0)

1

A(0)

1

B(1)

0

C(1)

D(0)

1

A(0)

1

B(1)

1

C(1)

D(0)

上面一共8种可能性,即   ,其中 s 为状态为一共 2 种,T 为阶元 (taxa) 数量,这里就为  

对于第一种可能性,C(1) 到父节点的消耗/步数 (cost/steps)是 1 (1->0) ,B 到父节点的消耗/步数是 1 (1->0) ,所以第一种可能性在 character1 的总 steps 是 2。

而一个树的总 steps 就是所有 character 的总 steps 之和。