ZDD-based algorithmic framework for solving shortest reconfiguration problems
ZDD-based algorithmic framework for solving shortest reconfiguration problems
复制标题
基于ZDD的解决最短重构问题的算法框架
DOI：
10.1007/978-3-031-33271-5_12
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Junichi Teruyama and Takahisa Toda
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Jun Kawahara;Yu Nakahata;Takehide Soh;Akira Suzuki;Junichi Teruyama and Takahisa Toda
本文提出了一种算法框架，用于解决各种组合重构问题，使用零抑制二元决策图（ZDD），一种数据结构，用于表示家庭的集合。通常，重新配置问题检查在两个给定的可行解之间是否存在逐步变换（例如，输入图的独立集合），使得所有中间结果也是可行的并且每个步骤都遵守固定的重新配置规则（例如，将单个顶点添加到独立集合/从独立集合移除单个顶点）。由所有可行解形成的解空间在输入大小上可以是指数的，并且实际上，许多重构问题已知是PSPACE完备的。本文表明，在所提出的框架中的算法有效地进行广度优先搜索，通过压缩的解决方案空间，使用ZDD，它发现两个给定的可行的解决方案之间的最短的转换，如果这样的转换存在。此外，所提出的框架提供了丰富的信息的解决方案空间，如其连接性和所有可行的解决方案，可从一个指定的。最后，我们证明了所提出的框架可以应用于各种重构问题，并通过实验评估其性能。
This paper proposes an algorithmic framework for solving various combinatorial reconfiguration problems by using zero-suppressed binary decision diagrams (ZDDs), a data structure for representing families of sets. In general, a reconfiguration problem checks if there is a step-by-step transformation between two given feasible solutions (e.g., independent sets of an input graph) of a fixed search problem, such that all intermediate results are also feasible and each step obeys a fixed reconfiguration rule (e.g., adding/removing a single vertex to/from an independent set). The solution space formed by all feasible solutions can be exponential in the input size, and indeed, many reconfiguration problems are known to be PSPACE-complete. This paper shows that an algorithm in the proposed framework efficiently conducts breadth-first search by compressing the solution space using ZDDs, and that it finds a shortest transformation between two given feasible solutions if such a transformation exists. Moreover, the proposed framework provides rich information on the solution space, such as its connectivity and all feasible solutions that are reachable from a specified one. Finally, we demonstrate that the proposed framework can be applied to various reconfiguration problems, and experimentally evaluate its performance.