查看“穷举法”的源代码

=矩阵=

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

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

<pre>
A 00
B 11
C 10
D 02
</pre>


= 内部节点穷举 =


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

<div style="display: inline-block; margin-right: 20px;">
{{Clade |style = font-size:100%; line-height:50%
|label1=0 
|1={{Clade
   |1=A(0)
   |label2=0
   |2={{Clade 
      |1=B(1)
      |label2=0
      |2={{Clade
         |1=C(1)
         |2=D(0)
      }}
   }}
}}
}}
</div>
<div style="display: inline-block; margin-right: 20px;">
{{Clade |style = font-size:100%; line-height:50%
|label1=0 
|1={{Clade
   |1=A(0)
   |label2=0
   |2={{Clade 
      |1=B(1)
      |label2=1
      |2={{Clade
         |1=C(1)
         |2=D(0)
      }}
   }}
}}
}}
</div>
<div style="display: inline-block; margin-right: 20px;">
{{Clade |style = font-size:100%; line-height:50%
|label1=0 
|1={{Clade
   |1=A(0)
   |label2=1
   |2={{Clade 
      |1=B(1)
      |label2=0
      |2={{Clade
         |1=C(1)
         |2=D(0)
      }}
   }}
}}
}}
</div>
<div style="display: inline-block; margin-right: 20px;">
{{Clade |style = font-size:100%; line-height:50%
|label1=1 
|1={{Clade
   |1=A(0)
   |label2=0
   |2={{Clade 
      |1=B(1)
      |label2=0
      |2={{Clade
         |1=C(1)
         |2=D(0)
      }}
   }}
}}
}}
</div>
<div style="display: inline-block; margin-right: 20px;">
{{Clade |style = font-size:100%; line-height:50%
|label1=0 
|1={{Clade
   |1=A(0)
   |label2=1
   |2={{Clade 
      |1=B(1)
      |label2=1
      |2={{Clade
         |1=C(1)
         |2=D(0)
      }}
   }}
}}
}}
</div>
<div style="display: inline-block; margin-right: 20px;">
{{Clade |style = font-size:100%; line-height:50%
|label1=1 
|1={{Clade
   |1=A(0)
   |label2=0
   |2={{Clade 
      |1=B(1)
      |label2=1
      |2={{Clade
         |1=C(1)
         |2=D(0)
      }}
   }}
}}
}}
</div>
<div style="display: inline-block; margin-right: 20px;">
{{Clade |style = font-size:100%; line-height:50%
|label1=1 
|1={{Clade
   |1=A(0)
   |label2=1
   |2={{Clade 
      |1=B(1)
      |label2=0
      |2={{Clade
         |1=C(1)
         |2=D(0)
      }}
   }}
}}
}}
</div>
<div style="display: inline-block; margin-right: 20px;">
{{Clade |style = font-size:100%; line-height:50%
|label1=1 
|1={{Clade
   |1=A(0)
   |label2=1
   |2={{Clade 
      |1=B(1)
      |label2=1
      |2={{Clade
         |1=C(1)
         |2=D(0)
      }}
   }}
}}
}}
</div>

上面一共8种可能性，即 <math>s^{T-1}</math> ，其中 s 为状态为一共 2 种，T 为阶元 (taxa) 数量，这里就为 <math>2^{4-1}=8</math> 。

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

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