On the Complexity of BDDs for State Space Search: A Case Study in Connect Four
On the Complexity of BDDs for State Space Search: A Case Study in Connect Four
复制标题
关于状态空间搜索的 BDD 的复杂性：《四子棋》的案例研究
DOI：
10.1609/aaai.v25i1.7821
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Peter Kissmann
中科院分区：
文献类型：
--
作者：
S. Edelkamp;Peter Kissmann
使用BDD的符号搜索通常可以节省大量的内存，而在某些领域，它的节省最多也就是中等程度。确定BDD是否适用于某个领域是一个开放的问题。出于寻找证据的BDD增长的状态空间搜索，在本文中，我们关注的是在连接四域的符号搜索。我们证明，有一个变量排序的所有可能的状态的集合-当继续后，终端状态已经达到-可以表示由多项式大小的BDD，而终止标准导致指数数量的节点在BDD给定的任何变量排序。
Symbolic search using BDDs usually saves huge amounts of memory, while in some domains its savings are moderate at best. It is an open problem to determine if BDDs work well for a certain domain. Motivated by finding evidences for BDD growths for state space search, in this paper we are concerned with symbolic search in the domain of Connect Four. We prove that there is a variable ordering for which the set of all possible states – when continuing after a terminal state has been reached – can be represented by polynomial sized BDDs, whereas the termination criterion leads to an exponential number of nodes in the BDD given any variable ordering.