Network-based heuristics for constraint-satisfaction problems.

*(English)*Zbl 0643.68156Many AI tasks can be formulated as constraint-satisfaction problems (CSP), i.e., the assignment of values to variables subject to a set of constraints. While some CSPs are hard, those that are easy can often be mapped into sparse networks of constraints which, in the extreme case, are trees. This paper identifies classes of problems that lend themselves to easy solutions, and develops algorithms that solve these problems optimally. The paper then presents a method of generating heuristic advice to guide the order of value assignments based on both the sparseness found in the constraint network and the simplicity of tree- structured CSPs. The advice is generated by simplifying the pending subproblems into trees, counting the number of consistent solutions in each simplified subproblem, and comparing these counts to decide among the choices pending in the original problem.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

PDF
BibTeX
XML
Cite

\textit{R. Dechter} and \textit{J. Pearl}, Artif. Intell. 34, No. 1, 1--38 (1988; Zbl 0643.68156)

Full Text:
DOI

##### References:

[1] | Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposabilityâ€”a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018 |

[2] | Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algebraic discrete methods, 8, 2, 177-184, (1987) |

[3] | Bertele, U.; Brioschi, F., () |

[4] | Bruynooghe, M.; Pereira, L.M., Deduction revision by intelligent backtracking, (), 194-215 |

[5] | Carbonell, J.G., Learning by analogy: formulation and generating plan from past experience, () |

[6] | Cox, P.T., Finding backtrack points for intelligent backtracking, (), 216-233 |

[7] | Dechter, A.; Dechter, R., Removing redundancies in constraint networks, () |

[8] | Dechter, R.; Pearl, J., A problem simplification approach that generates heuristics for constraint satisfaction problems, (), also · Zbl 0678.68100 |

[9] | Dechter, R.; Pearl, J., The anatomy of easy problems: A constraint-satisfaction formulation, (), 1066-1072 |

[10] | Dechter, R., Learning while searching in constraint-satisfaction problems, () |

[11] | Dechter, R.; Pearl, J., A tree-clustering scheme for csps, () · Zbl 0678.68100 |

[12] | Dechter, R.; Pearl, J., The cycle-cutset method for improving search performance in AI applications, (), 224-230 |

[13] | Doyle, J., A truth maintenance system, Artificial intelligence, 12, 231-272, (1979) |

[14] | Even, S., Graph algorithms, (1979), Computer Science Press Rockville, MD · Zbl 0441.68072 |

[15] | Freuder, E.C., A sufficient condition of backtrack-free search, J. ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063 |

[16] | Freuder, E.C., A sufficient condition for backtrack-bounded search, J. ACM, 32, 4, 755-761, (1985) · Zbl 0633.68096 |

[17] | Gashnig, J., Performance measurement and analysis of certain search algorithms, () |

[18] | Gaschnig, J., A problem similarity approach to devising heuristics: first results, (), 301-307 |

[19] | Guida, G.; Somalvico, M., A method for computing heuristics in problem solving, Inf. sci., 19, 251-259, (1979) · Zbl 0442.68097 |

[20] | Haralick, R.M.; Elliott, G.L., Increasing tree search efficiency for constraint satisfaction problems, Artificial intelligence, 14, 263-313, (1980) |

[21] | Knuth, D.E., Estimating the efficiency of backtrack programs, Math. comput., 29, 121-136, (1975) · Zbl 0297.68037 |

[22] | Mackworth, A.K., Consistency in networks of relations, Artificial intelligence, 8, 1, 99-118, (1977) · Zbl 0341.68061 |

[23] | Mackworth, A.K.; Freuder, E.C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial intelligence, 25, 1, 65-74, (1984) |

[24] | Martins, J.P.; Shapiro, S.C., Theoretical foundations for belief revision, (), 383-398 |

[25] | Matwin, S.; Pietrzykowski, T., Intelligent backtracking in plan-based deduction, IEEE trans. pattern anal. machine intell., 7, 6, 682-692, (1985) · Zbl 0595.68082 |

[26] | Minsky, M., Steps towards artificial intelligence, (), 442 |

[27] | Mohr, R.; Henderson, T.C., Arc and path consistency revisited, Artificial intelligence, 28, 2, 225-233, (1986) |

[28] | Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inf. sci., 7, 95-132, (1974) · Zbl 0284.68074 |

[29] | Nudel, B., Consistent-labeling problems and their algorithms: expected-complexities and theory-based heuristics, Artificial intelligence, 21, 135-178, (1983) |

[30] | Pearl, J., On the discovery and generation of certain heuristics, (), 22-23, 113-124, (1983), also in |

[31] | Purdom, P., Search rearrangement backtracking and polynomial average time, Artificial intelligence, 21, 117-133, (1983) |

[32] | Purdom, P.W.; Brown, C.A., () |

[33] | Sacerdoti, E.D., Planning in a hierarchy of abstraction spaces, Artificial intelligence, 5, 2, 115-135, (1974) · Zbl 0288.68052 |

[34] | Stallman, R.M.; Sussman, G.J., Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artificial intelligence, 9, 2, 135-196, (1977) · Zbl 0372.94024 |

[35] | Stone, H.S.; Stone, J.M., Efficient search techniques: an empirical study of the N-queens problem, () |

[36] | Stone, H.S.; Sipala, P., The average complexity of depth-first search with backtracking and cut-off, IBM J. res. dev., 30, 3, 242-258, (1986) · Zbl 0636.68041 |

[37] | Tarjan, R.E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 3, 566-579, (1984) · Zbl 0545.68062 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.