Bucket Elimination: A Unifying Framework for Processing Hard and Soft Constraints

被引：12
作者：
Dechter R. [1 ]
机构：
[1] Dept. of Info. and Computer Science, University of California, Irvine, Irvine
来源：
Constraints | 1997年 / 2卷 / 1期
基金：
美国国家科学基金会;
关键词：
Graphs; Search; Variable elimination;
D O I：
10.1023/A:1009796922698
中图分类号：
学科分类号：
摘要：
This position paper argues that extending the CSP model to a richer set of tasks such as, constraint optimization, probabilistic inference and decision theoretic tasks can be done within a unifying framework called "bucket elimination". The framework allows uniform hybrids for combining elimination and conditioning guided by the problem's structure and for explicating the tradeoffs between space and time and between time and accuracy.
引用
收藏
页码：51 / 55
页数：4
相关论文
共 9 条
  • [1] Dechter R., Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition, Artificial Intelligence, 41, pp. 273-312, (1990)
  • [2] Dechter R., Constraint networks, Encyclopedia of Artificial Intelligence, pp. 276-285, (1992)
  • [3] Dechter R., Bucket elimination: A unifying framework for several probabilistic inference algorithms, Uncertainty in AI (UAI96), pp. 211-219, (1996)
  • [4] Dechter R., Rish I., Directional resolution: The davis-putnam procedure, revisited, Proceedings of Knowledge Representation (KR-94), pp. 134-145, (1994)
  • [5] Dechter R., Van Beek P., Local and global relational consistency, First International Conference on Principles and Practice of Constraint Programming (CP 95), pp. 240-257, (1995)
  • [6] Freuder E.C., A sufficient condition for backtrack-free search, Journal of the ACM, 29, pp. 24-32, (1982)
  • [7] Mackworth A., Constraint satisfaction, Encyclopedia of Artificial Intelligence, pp. 285-293, (1992)
  • [8] Montanari U., Networks of constraints: Fundamental properties and applications to picture processing, Information Sciences, 7, pp. 95-132, (1974)
  • [9] Pearl J., Probabilistic reasoning in intelligent systems, Constraints: An International Journal, 2, pp. 63-69, (1988)
1