Communication interruption between a game tree and its leaves
Communication interruption between a game tree and its leaves
复制标题
游戏树与其叶子之间的通信中断
DOI：
10.1007/978-981-32-9808-8_15
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Toshio Suzuki
中科院分区：
文献类型：
--
作者：
Toshio Suzuki
我们介绍了一个继承模型的AND-OR树。叶通过可能具有高中断概率的通信信道连接到内部节点。深度优先通信是指以下协议：如果给定算法探测叶子，则它继续对该叶子进行查询，直到返回答案。对于每个这样的树，我们给出了一个具体的例子，中断概率设置具有以下性质。对于真值分配上的任何独立且相同的分布（假设概率既不是0也不是1），任何执行深度优先通信的深度优先搜索算法都不是最优的。这一结果与通常的与或树（Tarsi）上存在最优和深度优先算法的结果形成了鲜明的对比。我们的具体例子是基于黎曼zeta函数。我们还提出了一个通用的框架。
We introduce a successor model of an AND-OR tree. Leaves are connected to internal nodes via communication channels that possibly have high probability of interruption. By depth-first communication we mean the following protocol: if a given algorithm probes a leaf then it continues to make queries to that leaf until return of an answer. For each such tree, we give a concrete example of interruption probability setting with the following property. For any independent and identical distribution on the truth assignments (probability is assumed to be neither 0 nor 1), any depth-first search algorithm that performs depth-first communication is not optimal. This result makes sharp contrast with the counterpart on the usual AND-OR tree (Tarsi) that optimal and depth-first algorithm exists. Our concrete example is based on Riemann zeta function. We also present a generalized framework.