AC-5*:An Improved AC-5 and its Specializations
No Thumbnail Available
Date
1996-04-01T00:00:00Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Many general and specific arc consistency algorithms have been produced in the past for solving Constraint Satisfaction Problems (CSP). The important general algorithms are AC-3, AC-4, AC-5 and AC-6. AC-5 is also a generic algorithm. It can be reduced to AC-3, AC-4 and AC-6. Specific algorithms are efficient specializations of the general ones for specific constraints. Functional, anti-functional and monotonic constraints are three important classes of specific constraints. AC-5 has been specialized to produce an O(ed) algorithm (in time) for these classes of constraints. However, this specialization does not reduce the space requirement. In practical applications, both time and space requirements are important criteria in choosing an algorithm.
This paper makes two contributions. First, we propose an improved generic arc consistency algorithm, called AC-5*. It can be specialized to reduce both time and space complexities. Second, we present a more efficient technique for handling an important subclass of functional constraints, namely increasing functional constraints. This technique is significant because in practice almost all functional constraints are actually increasing functional constraints.