Solving Systems of Difference Constraints Incrementally
Solving Systems of Difference Constraints Incrementally
复制标题
增量求解差分约束系统
DOI：
10.1007/pl00009261
复制
发表时间：
1999
期刊：
影响因子：
1.1
通讯作者：
Raymond E. Miller
中科院分区：
文献类型：
--
作者：
G. Ramalingam;Junehwa Song;Leo Joskowicz;Raymond E. Miller
抽象的。由xi-xj形式的不等式组成的差分约束系统
$\leq$bi，j存在于许多应用中，尤其是那些涉及时间推理的应用。通常，在添加、修改和删除约束时，有必要维护此类系统的解决方案。现有的算法通过每次重新求解结果系统来处理修改，这是低效的。用于确定差约束系统是否可行(即，它是否有解)和计算解的最知名算法运行在Θ(Mn)时间内，其中n是变量的数目，m是约束的数目。本文提出了一种新的有效的增量算法，用于维持差约束系统的解。当添加、修改或删除约束时，该算法确定新系统是否可行并更新其解。当系统变得不可行时，算法继续处理变化，直到它再次变得可行，此时将产生可行解。该算法在原系统可行的情况下，在O(m+nlogn)时间内添加约束，在固定时间内删除约束。更准确地说，加法的处理时间为O(||Δ||+|Δ|LOG|Δ|)，其中|Δ|是其值被更改以计算新的可行解的变量的数量，而||Δ||是涉及其值被更改的变量的约束的数量。当原系统不可行时，该算法在O(m+nlogn)分期时间内处理任何变化。新算法还可以用来检查动态图中是否存在负圈。
Abstract. Difference constraints systems consisting of inequalities of the form xi - xj
$ \leq $ bi,j occur in many applications, most notably those involving temporal reasoning. Often, it is necessary to maintain a solution to such a system as constraints are added, modified, and deleted. Existing algorithms handle modifications by solving the resulting system anew each time, which is inefficient. The best known algorithm to determine if a system of difference constraints is feasible (i.e., if it has a solution) and to compute a solution runs in Θ (mn) time, where n is the number of variables and m is the number of constraints. This paper presents a new efficient incremental algorithm for maintaining a solution to a system of difference constraints. As constraints are added, modified, or deleted, the algorithm determines if the new system is feasible and updates its solution. When the system becomes infeasible, the algorithm continues to process changes until it becomes feasible again, at which point a feasible solution will be produced. The algorithm processes the addition of a constraint in time O(m + n log n) and the removal of a constraint in constant time when the original system is feasible. More precisely, additions are processed in time O( || Δ || + |Δ| log|Δ| ) , where |Δ| is the number of variables whose values are changed to compute the new feasible solution, and || Δ || is the number of constraints involving the variables whose values are changed. When the original system is infeasible, the algorithm processes any change in O(m + n log n)amortized time. The new algorithm can also be used to check for the existence of negative cycles in dynamic graphs.