4.5 応用: 幅優先評価の実現

  

図 4.4: 二進木の例

ここでは論理式の評価を例にとり, 優先度を用いた幅優先評価の実現方法を述べる. 一般に, 論理式は, AND, OR, t(rue), f(alse) をノードとする二進木で表現することができる. 例を図4.4に示す. 二進木で表わした場合, 論理式の評価は二進木の評価になる.

論理式を表わした二進木の評価について, 以下では, まず,

• すべてのノードを評価する方法
• 不要なノード評価を始めない方法
• 不要なノード評価を打ち切る方法

• 幅優先に評価を行なう方法

• 4.5.1 すべてのノードを評価する方法
• 4.5.2 不要なノード評価を始めない方法
• 4.5.3 不要なノード評価を打ち切る方法
• 4.5.4 優先度を用いて幅優先に評価を行なう方法