The Eigen-Distribution of Weighted Game Trees
The Eigen-Distribution of Weighted Game Trees
复制标题
DOI：
10.1007/978-3-319-71150-8_25
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
Shohei Okisaka;Weiguang Peng;Wenjuan Li;Kazuyuki Tanaka
中科院分区：
文献类型：
--
作者：
Shohei Okisaka;Weiguang Peng;Wenjuan Li;Kazuyuki Tanaka
本文致力于对AND-OR树平衡点的研究。Liu和Tanaka （2007,2007a）描述了实现分布复杂度的特征分布，并证明了一致二叉树特征分布的唯一性。后来，Suzuki和Nakamura（2012）表明，如果只允许定向算法，唯一性就会失效。Penget al.（2016）将特征分布的研究扩展到高度为2的平衡多分支树。但是，对于一般的多分支树来说，这种唯一性是否仍然成立仍然是一个开放的问题。为此，我们引入了加权树，即基于叶子值的加权代价的树。利用这些模型，我们证明了平衡多分支树的特征分布唯一性适用于所有确定性算法，而不适用于定向算法。
This paper is devoted to the ongoing study on the equilibrium points of AND-OR trees. Liu and Tanaka (2007, 2007a) characterized the eigen-distributions that achieve the distributional complexity, and among others, they proved the uniqueness of eigen-distribution for a uniform binary tree. Later, Suzuki and Nakamura (2012) showed that the uniqueness fails if only directional algorithms are allowed. Penget al.(2016) extended the studies on eigen-distributions to balanced multi-branching trees of height 2. But, it remains open whether the uniqueness still holds or not for general multi-branching trees. To this end, we introduce the weighted trees, namely, trees with weighted cost depending on the value of a leaf. Using such models, we prove that for balanced multi-branching trees, the uniqueness of eigen-distribution holdsw.r.t.all deterministic algorithms, but failsw.r.t.only directional algorithms.