穷举法

来自MalacoKnowledge
Malacology留言 | 贡献2024年1月19日 (五) 09:53的版本

矩阵

在 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 到父节点的消耗/步数 (cost/steps)是 1 (1->0) ,B 到父节点的消耗/步数是 1 (1->0) ,所以第一种可能性在 character1 的总 steps 是 2。

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

树拓扑结构穷举

树的拓扑结构可能行如下

A

B

C

D

A

C

B

D

A

D

B

C