论文标题
用于TCSP的二进制构想弧线算法：其计算分析及其用作解决方案搜索算法中的过滤过程
A binarized-domains arc-consistency algorithm for TCSPs: its computational analysis and its use as a filtering procedure in solution search algorithms
论文作者
论文摘要
[Dechter等，1991]中定义的TCSP（时间约束满意度问题）在添加了“世界来源”变量后通过对它们进行二进制，从而摆脱了一般的约束。在这项工作中，我们将视为“世界的起源”变量与其他变量之间的约束，作为这些其他变量的（二元）域。考虑到这一点，我们定义了TCSP的弧线一致性的概念，我们将其称为二进制构建弧矛盾，或简称BDARC的一致性。我们为TCSP提供了一种实现BDARC一致性的算法，我们将其称为BDAC-3，因为它是Mackworth的[1977]众所周知的ARC一致性算法AC-3的适应。我们表明，如果在[Dechter等，1991]中称为STP（简单的时间问题）中的凸TCSP是BDARC的一致性，并且其“世界的起源”变量与其他任何变量都没有断开，则其二进制域是最小的。我们提供了两个多项式的无回程程序：一个是从BDARC一致的STP中获得的任务，要么是不一致的，要么在一致性的情况下，是BDARC一致的STP改进，其“起源于世界的起源”变量与其他变量无关。另一个是从BDARC一致的STP中获得解决方案的任务，其“世界的起源”变量与其他变量都没有断开。然后，我们展示了如何在一般的TCSP求解器和基于TCSP的工作室调度程序中使用我们的结果。从我们的工作中可以提取IR标记的有向图的一对一的最短路径算法。最后，我们表明，对Mackworth [1977]路径矛盾算法PC-2的现有改编不保证始终终止并纠正它。
TCSPs (Temporal Constraint Satisfaction Problems), as defined in [Dechter et al., 1991], get rid of unary constraints by binarizing them after having added an "origin of the world" variable. In this work, we look at the constraints between the "origin of the world" variable and the other variables, as the (binarized) domains of these other variables. With this in mind, we define a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains Arc-Consistency, or bdArc-Consistency for short. We provide an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as bdAC-3, for it is an adaptation of Mackworth's [1977] well-known arc-consistency algorithm AC-3. We show that if a convex TCSP, referred to in [Dechter et al., 1991] as an STP (Simple Temporal Problem), is bdArc-Consistent, and its "origin of the world" variable disconnected from none of the other variables, its binarized domains are minimal. We provide two polynomial backtrack-free procedures: one for the task of getting, from a bdArc-Consistent STP, either that it is inconsistent or, in case of consistency, a bdArc-Consistent STP refinement whose "origin of the world" variable is disconnected from none of the other variables; the other for the task of getting a solution from a bdArc-Consistent STP whose "origin of the world" variable is disconnected from none of the other variables. We then show how to use our results both in a general TCSP solver and in a TCSP-based job shop scheduler. From our work can be extracted a one-to-all all-to-one shortest paths algorithm of an IR-labelled directed graph. Finally, we show that an existing adaptation to TCSPs of Mackworth's [1977] path-consistency algorithm PC-2 is not guaranteed to always terminate, and correct it.
