PID分布下均衡加权AND-OR树的最优算法  

The Optimal Algorithm of Balanced Weighted AND-OR Trees Under PID Distribution

作　　者：熊毅 彭宁宁 XIONG Yi;PENG Ning-ning(Wuhan University of Technology,Wuhan 430070,China)

机构地区：[1]武汉理工大学理学院数学系,湖北武汉430070

出　　处：《数学的实践与认识》2022年第8期155-163,共9页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11701438)。

摘　　要：研究了均衡加权博弈树(AND-OR树)在比例独立分布(PID)下的最优算法问题.1983年,Tarsi证明了在独立同分布(IID)下,均衡博弈树存在一个最优的深度优先算法SOLVE.为了研究更一般化的加权博弈树,Tanaka等人提出了一种更加广义的深度优先算法DIR_(d)算法以及PID分布.继续其工作,证明了对于任意的均衡博弈树,在PID分布下,DIR_(d)算法是最优的.同时还证明了特征分布满足适当独立分布(dID)时,DIR_(d)算法的存在性.研究的结果是对Tarsi和Peng定理的推广.This paper studies the optimal algorithm problem of a balanced AND-OR tree under certain distributions.In 1983,Tarsi studied the existence of an optimal depth-first algorithm for balanced AND-OR trees under independent and identical distribution(IID).In order to study a more general weighted AND-OR tree,Tanaka proposed more general distributions named by proportional independent distribution(PID).This paper continues their work and show that for any balanced weighted three,the DIR algorithm is the optimal algorithm with PID.In addition,we also show that the existence of the DIR algorithm with eigen-distribution under decent distribution(dID).This is the generalization of Tarsi and Peng’s theorem.

关 键 词：加权博弈树 比例独立分布 随机算法 AND-OR博弈树 

分 类 号：O224[理学—运筹学与控制论]