The Eigen Distribution of an AND-OR Tree under Directional Algorithms
The Eigen Distribution of an AND-OR Tree under Directional Algorithms
复制标题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Toshio Suzuki;Ryota Nakamura
中科院分区：
文献类型：
--
作者：
Toshio Suzuki;Ryota Nakamura
Consider a probability distribution d on the truth assignments to a perfect binary AND-OR tree. Liu and Tanaka (2007) extends the work of Saks and Wigderson (1986), and they characterize the eigen-distribution, the distribution achieving the equilibrium, as the uniform distribution on the 1-set (the set of all reluctant assignments for which the root has the value 1). We show that the uniqueness of the eigen-distribution fails provided that we restrict ourselves to directional algorithms. An alpha-beta pruning algorithm is said to be directional (Pearl, 1980) if for some linear ordering of the leaves (Boolean variables) it never selects for examination a leaf situated to the left of a previously examined leaf. We also show that the following weak version of the Liu-Tanaka result holds for the situation where only directional algorithms are considered; a distribution is eigen if and only if it is a distribution on the 1-set such that the cost does not depend on an associated deterministic algorithm.
