New algorithms for max restricted path consistency |
| |
Authors: | Thanasis Balafoutis Anastasia Paparrizou Kostas Stergiou Toby Walsh |
| |
Affiliation: | 1.Department of Information and Communication Systems Engineering,University of the Aegean,Mytilene,Greece;2.Department of Informatics and Telecommunications Engineering,University of Western Macedonia,Kozani,Greece;3.NICTA,University of New South Wales,Sydney,Australia |
| |
Abstract: | Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that enforces a higher order of consistency
than arc consistency. Despite the strong pruning that can be achieved, maxRPC is rarely used because existing maxRPC algorithms
suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value
deletions. In this paper we propose and evaluate techniques that can boost the performance of maxRPC algorithms by eliminating
many of these overheads and redundancies. These include the combined use of two data structures to avoid many redundant constraint
checks, and the exploitation of residues to quickly verify the existence of supports. Based on these, we propose a number
of closely related maxRPC algorithms. The first one, maxRPC3, has optimal O(end
3) time complexity, displays good performance when used stand-alone, but is expensive to apply during search. The second one,
maxRPC3
rm
, has O(en
2
d
4) time complexity, but a restricted version with O(end
4) complexity can be very efficient when used during search. The other algorithms are simple modifications of maxRPC3
rm
. All algorithms have O(ed) space complexity when used stand-alone. However, maxRPC3 has O(end) space complexity when used during search, while the others retain the O(ed) complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC,
often by large margins, and constitute a viable alternative to arc consistency on some problem classes. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|