Title: The consistent labeling problem and its algorithm: toward exact-case complexities and theory-based heuristics
Abstract: This work is a study of the Consistent Labeling Problem (CLP)--also known as the Constraint Satisfaction Problem--which is of central interest in Artificial Intelligence and Operations Research. The problem is formulated far more generally than is usual, so that the wide variety of CLP instances that arise in practice may be subsumed, and so that certain important search-ordering effects characteristic of the more general case, may be studied.
Several CLP algorithms--Backtracking, Forward Checking and word-wise Forward Checking--are described, with explicit treatment of the various search ordering parameters that apply. The expected complexity of using these algorithms is derived under several probability models. These results provide the first analytic expressions capturing CLP problem-solving complexity as a function of instantiation order and constraint-check order. As such, they provide a long-sought basis for the a priori selection of good search orderings.
We show how the theory can be used for the formal derivation of good search-order heuristics, as well as how it may be used to select between algorithms and even between alternative CLP problem representations. These may be viewed as case studies of what we propose to be a generally useful, new approach for the formal derivation of problem-solving heuristics via the minimization of analytic complexity expressions.
A second general theme represented here is the importance of performing complexity analyses with respect to what we call homogeneous classes. The resulting expressions are useful in predicting the exact-case complexity of individual instances rather than only for predicting for some artificial class of instances, the best-case, worst-case or expected-case complexity--the latter, under some usually irrelevant, assumed probability distribution. Moreover, complexity expressions based on homogeneous classes are to be preferred also in that the theory-based heuristics obtained from them are good on an instance-by-instance basis, rather than only being good with respect to a given class and its assumed distribution. Many examples are given of the instance-specificity of our complexity expressions and their derived heuristics, as well as of the significant savings in problem-solving complexity that these make possible.
Publication Year: 1986
Publication Date: 1986-06-01
Language: en
Type: book
Access and Citation
Cited By Count: 8
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot