Branching Constraint Satisfaction Problems and Markov Decision Problems Compared

被引：0
作者：
David W. Fowler
Kenneth N. Brown
机构：
[1] University of Aberdeen,Department of Computing Science
来源：
Annals of Operations Research | 2003年 / 118卷
关键词：
constraint satisfaction; uncertainty; Markov decision problems;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Branching Constraint Satisfaction Problems (BCSPs) model a class of uncertain dynamic resource allocation problems. We describe the features of BCSPs, and show that the associated decision problem is NP-complete. Markov Decision Problems could be used in place of BCSPs, but we show analytically and empirically that, for the class of problems in question, the BCSP algorithms are more efficient than the related MDP algorithms.
引用
收藏
页码：85 / 100
页数：15
相关论文
共 50 条
  • [41] Musical constraint satisfaction problems solved with adaptive search
    C. Truchet
    P. Codognet
    Soft Computing, 2004, 8 : 633 - 640
  • [42] Sensitivity Analysis in Quantified Interval Constraint Satisfaction Problems
    Hu, Jie
    Wang, Yan
    Cheng, Aiguo
    Zhong, Zhihua
    JOURNAL OF MECHANICAL DESIGN, 2015, 137 (04)
  • [43] A Connectionist Approach for Solving Large Constraint Satisfaction Problems
    A. Likas
    G. Papageorgiou
    A. Stafylopatis
    Applied Intelligence, 1997, 7 : 215 - 225
  • [44] Iterative projection algorithms for solving constraint satisfaction problems: Effect of constraint convexity
    Millane, Rick P.
    Taylor, Joshua T.
    Arnal, Romain D.
    Wojtas, David H.
    Clare, Richard M.
    2019 INTERNATIONAL CONFERENCE ON IMAGE AND VISION COMPUTING NEW ZEALAND (IVCNZ), 2019,
  • [45] An approach based on constraint satisfaction problems to disruptive event management in supply chains
    Guarnaschelli, Armando
    Chiotti, Omar
    Salomone, Hector E.
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2013, 144 (01) : 223 - 242
  • [46] Prioritised fuzzy constraint satisfaction problems: axioms, instantiation and validation
    Luo, XD
    Lee, JHM
    Leung, HF
    Jennings, NR
    FUZZY SETS AND SYSTEMS, 2003, 136 (02) : 151 - 188
  • [47] Learning vector quantization for variable ordering in constraint satisfaction problems
    Carlos Ortiz-Bayliss, Jose
    Terashima-Marin, Hugo
    Enrique Conant-Pablos, Santiago
    PATTERN RECOGNITION LETTERS, 2013, 34 (04) : 423 - 432
  • [48] The SAT-UNSAT transition for random constraint satisfaction problems
    Creignou, Nadia
    Daude, Herve
    DISCRETE MATHEMATICS, 2009, 309 (08) : 2085 - 2099
  • [49] Binary constraint satisfaction problems defined by excluded topological minors
    Cohen, David A.
    Cooper, Martin C.
    Jeavons, Peter G.
    Zivny, Stanislav
    INFORMATION AND COMPUTATION, 2019, 264 : 12 - 31
  • [50] Successive search method for valued constraint satisfaction and optimization problems
    Tounsi, M
    David, P
    ICTAI 2001: 13TH IEEE INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2001, : 341 - 347
12345