We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n+n9;) plus the time required to sort the assignment variables by range endpoints, where n is the number of assignm...
详细信息
ISBN:
(纸本)3540202021
We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n+n') plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n' is the number of values in the union of their ranges. We thus offer a fast alternative to Regin's arc consistency algorithm [6] which runs in time O(n(3/2) n') and space O(n . n'). Our algorithm can also narrow the bounds for the number of occurrences of each value, which has not been done before.
We propose a new method for solving Valued constraint Satisfaction Problems based both on backtracking techniques-branch and bound- and the notion of tree-decomposition of valued constraint networks. this mixed method...
详细信息
ISBN:
(纸本)3540202021
We propose a new method for solving Valued constraint Satisfaction Problems based both on backtracking techniques-branch and bound- and the notion of tree-decomposition of valued constraint networks. this mixed method aims to benefit from the practical efficiency of enumerative algorithms while providing a warranty of a bounded time complexity. Indeed the time complexity of our method is O(d(w+)+ (1)) with w(+) an approximation of the tree-width of the constraint network and d the maximum size of domains. Such a complexity is obtained by exploiting optimal bounds on the sub-problems defined from the tree-decomposition. these bounds associated to some partial assignments are called "structural valued goods". Recording and exploiting these goods may allow our method to save some time and space with respect to ones required by classical dynamic programming methods. Finally, this method is a natural extension of the BTD algorithm [1] proposed in the classical CSP framework.
System dynamics is often modeled by means of parametric differential equations. Despite their expressive power, they are difficult to reason about and make safe decisions, given their non-linearity and the important e...
详细信息
ISBN:
(纸本)3540202021
System dynamics is often modeled by means of parametric differential equations. Despite their expressive power, they are difficult to reason about and make safe decisions, given their non-linearity and the important effects that the uncertainty on data may cause. Either by traditional numerical simulation or relying on constraint based methods, it is difficult to express a number of constraints on the solution functions (for which there are usually no analytical solutions) and these constraints may only be handled passively, with generate and test techniques. In contrast, the framework we propose not only extends the declarativeness of the constraint based approach but also makes an active use of constraints on the solution functions, which makes it particularly suited for a number of decision making problems, such as those arising in the biomedical applications presented in the paper.
暂无评论