Branching constraint satisfaction problems and Markov decision problems compared

被引：7
作者：
Fowler, DW [1 ]
Brown, KN [1 ]
机构：
[1] Univ Aberdeen, Dept Comp Sci, Aberdeen, Scotland
来源：
ANNALS OF OPERATIONS RESEARCH | 2003年 / 118卷 / 1-4期
关键词：
constraint satisfaction; uncertainty; Markov decision problems;
D O I：
10.1023/A:1021853506616
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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
页数：16
相关论文
共 50 条
  • [21] Recognizing frozen variables in constraint satisfaction problems
    Jonsson, P
    Krokhin, A
    THEORETICAL COMPUTER SCIENCE, 2004, 329 (1-3) : 93 - 113
  • [22] Automatic Generation of Heuristics for Constraint Satisfaction Problems
    Ortiz-Bayliss, Jose Carlos
    Humberto Moreno-Scott, Jorge
    Terashima-Marin, Hugo
    NATURE INSPIRED COOPERATIVE STRATEGIES FOR OPTIMIZATION (NICSO 2013), 2014, 512 : 315 - +
  • [23] Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems
    Javier Larrosa
    Rina Dechter
    Constraints, 2003, 8 : 303 - 326
  • [24] Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
    Larrosa, J
    Dechter, R
    CONSTRAINTS, 2003, 8 (03) : 303 - 326
  • [25] Qualitative constraint satisfaction problems: An extended framework with landmarks
    Li, Sanjiang
    Liu, Weiming
    Wang, Shengsheng
    ARTIFICIAL INTELLIGENCE, 2013, 201 : 32 - 58
  • [26] Application driven inverse type constraint satisfaction problems
    Zhuravlev Y.I.
    Aslanyan L.
    Ryazanov V.V.
    Sahakyan H.
    Aslanyan, L. (lasl@sci.am), 1600, Izdatel'stvo Nauka (27): : 418 - 425
  • [27] Musical constraint satisfaction problems solved with adaptive search
    Truchet, C
    Codognet, P
    SOFT COMPUTING, 2004, 8 (09) : 633 - 640
  • [28] Robust optimal strategies in Markov decision problems
    Oren, Gal
    Solan, Eilon
    OPERATIONS RESEARCH LETTERS, 2014, 42 (02) : 109 - 112
  • [29] Solving set-valued constraint satisfaction problems
    Jaulin, Luc
    COMPUTING, 2012, 94 (2-4) : 297 - 311
  • [30] Locating the phase transition in binary constraint satisfaction problems
    Smith, BM
    Dyer, ME
    ARTIFICIAL INTELLIGENCE, 1996, 81 (1-2) : 155 - 181
12345