Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The complexity of some polynomial network consistency algorithms for constraint satisfaction problems
Mackworth A., Freuder E. (ed) Artificial Intelligence25 (1):65-74,1985.Type:Article
Date Reviewed: Oct 1 1985

This paper is concerned with properties of filtering algorithms for Constraint Satisfaction Problems (CSP). Problems in this class have the following form: Given a finite set of variables, each with an associated finite domain of values, and a set of constraining relations, each involving a subset of the variables, find all possible assignments of values to variables that satisfy the given constraints. There are variants of this formulation where the goal is to find a single assignment.

The problem of assigning interpretations to features of visual images (e.g., the edge labeling problem) was recognized in the early 1970s as being a CSP, and so were various types of cryptoarithmetic problems. By now, there is a wide range of other AI tasks that can be seen as CSPs; for example, problems of circuit design and of truth maintenance. As pointed out by Simon and Lea [1] in their analysis of CSPs, these processes involve simultaneous work in two spaces--the space of solution structures (sets of unique assignments of values to variables), and the space of problem conditions (specified by the relational constraints between variables). The key design problem is how to coordinate the work in these two spaces.

Working on vision tasks, Waltz [2] developed a filtering algorithm for reducing the space of possible solutions of a CSP via an analysis of its problem conditions. The algorithm focuses on the binary constraints between variables, and it eliminates all values in the domains of variables that are inconsistent with the binary constraints. Montanari [3] developed another filtering algorithm which is based on the elimination of value pairs from domains of variables that are inconsistent with the structure of binary constraints of a problem. Mackworth [4] further generalized and clarified the nature of filtering algorithms for CSPs.

This paper takes additional steps towards the clarification and analysis of filtering algorithms for CSPs, which are also called Network Consistency Algorithms. Four algorithms are presented and analyzed; two of them are general versions of Waltz’s and Montanari’s algorithms.

A significant result obtained in the paper is that the time complexity of a Waltz-like filtering algorithm is at most O(a3e) where a is the domain size of a variable and e is the number of binary constraints in a problem; i.e., it is linear in the number of binary constraints. For highly connected constraint graphs, this leads to a time complexity of O(a3n2), where n is the number of variables in the problem. For sparse constraint graphs, the time complexity is O(a3n); since planar graphs are sparse, then their associated time complexity is linear in the number of variables. This analysis provides a clear illustration of how the complexity of problem solving depends on the degree of interaction between problem conditions (the constraints).

The authors argue that since the constraint graphs of edge labeling problems in vision are planar, then application of the Waltz filtering algorithm to these problems produces behavior which has linear time complexity. This is a significant theoretical result because it shows that the (empirically observed) linear behavior of this algorithm is not due to special peculiarities of the vision problem, but derives from more general characteristics of the problem, i.e., the structure of its constraint graph. Another interesting result is that when the constraint graph of a problem is a strict tree, a solution to the CSP can be found in linear time. It is unfortunate that this result cannot be extended to produce better complexity bounds for the Waltz algorithm for edge labeling, as the constraint graphs in this domain are not strict trees in general. In any event, the result for trees is interesting, and it may be used in a variety of special applications (including vision), either directly or as a heuristic guide for the solution of “similar” problems.

The paper presents an analysis of Montanari-like filtering algorithms for which an upper bound time complexity of O(a5n5) is obtained, and an analysis of a second algorithm that eliminates value pairs from domains of variables in a manner analogous to Waltz-like filtering algorithms, which results in a time complexity of O(a5n3). These are interesting results that show the growth in polynomial complexity of filtering algorithms as they proceed to narrow down the space of solutions by analyzing interactions between problem conditions that are increasingly global.

The paper does not deal directly with ways of using filtering algorithms in systems for obtaining complete solutions to CSPs; it offers, however, several suggestions. This is a fertile area for further work. There is much more to be done in understanding the appropriate balance between the polynomial complexity of processes for eliminating solution options and the exponential complexity of processes for generating and testing solution candidates. This well-written paper should be of interest to workers in vision, to researchers having a more general interest in the design of algorithms for CSPs, and to those who are concerned with the development of a theory of problem solving in AI.

Reviewer:  S. Amarel Review #: CR109331
1) Simon, H. A.; and Lea, G.Problem solving and rule induction: a unified view, in Knowledge and cognition, L. Gregg (Ed.), Halstead Press, New York, 1974, 105–127. See <CR> 16, 3 (March 1975), Rev. 27,945.
2) Waltz, D.Understanding line drawings of scenes with shadows, in The psychology of computer vision, Winston (Ed.), McGraw-Hill, New York, 1975.
3) Montanari, U.Networks of constraints: fundamental properties, and applications to picture processing, Inf. Sci. 7 (1974).
4) Mackworth, A. K.Consistency of networks of relations, Artif. Intell. 8 (1977), 99–118. See <CR> 20, 4 (April 1979), Rev. 34,360.
Bookmark and Share
 
Graph And Tree Search Strategies (I.2.8 ... )
 
 
Computations On Discrete Structures (F.2.2 ... )
 
 
Modeling And Recovery Of Physical Attributes (I.2.10 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Graph And Tree Search Strategies": Date
How evenly should one divide to conquer quickly?
Walsh T. Information Processing Letters 19(4): 203-208, 1984. Type: Article
Oct 1 1985
Three approaches to heuristic search in networks
Bagchi A., Mahanti A. Journal of the ACM 32(1): 1-27, 1985. Type: Article
Sep 1 1986
AND/OR graph heuristic search methods
Mahanti A., Bagchi A. Journal of the ACM 32(1): 28-51, 1985. Type: Article
Feb 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy