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 条

[31] Solving set-valued constraint satisfaction problems
Luc Jaulin
Computing, 2012, 94 : 297 - 311
[32] Solving Constraint Satisfaction Problems by ACO with Cunning Ants
Mizuno, Kazunori
Hayakawa, Daiki
Sasaki, Hitoshi
Nishihara, Seiichi
2011 INTERNATIONAL CONFERENCE ON TECHNOLOGIES AND APPLICATIONS OF ARTIFICIAL INTELLIGENCE (TAAI 2011), 2011, : 155 - 160
[33] Challenging Heuristics: Evolving Binary Constraint Satisfaction Problems
Moreno-Scott, Jorge H.
Carlos Ortis-Bayliss, Jose
Terashima-Marin, Hugo
Enrique Conant-Pablos, Santiago
PROCEEDINGS OF THE FOURTEENTH INTERNATIONAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2012, : 409 - 416
[34] Sporadic Overtaking Optimality in Markov Decision Problems
Flesch, Janos
Predtetchinski, Arkadi
Solan, Eilon
DYNAMIC GAMES AND APPLICATIONS, 2017, 7 (02) : 212 - 228
[35] Sporadic Overtaking Optimality in Markov Decision Problems
János Flesch
Arkadi Predtetchinski
Eilon Solan
Dynamic Games and Applications, 2017, 7 : 212 - 228
[36] ALIFE: A multiagent computing paradigm for constraint satisfaction problems
Liu, JM
Jing, H
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2001, 15 (03) : 475 - 491
[37] A connectionist approach for solving large constraint satisfaction problems
Likas, A
Papageorgiou, G
Stafylopatis, A
APPLIED INTELLIGENCE, 1997, 7 (03) : 215 - 225
[38] Universal algebra and hardness results for constraint satisfaction problems
Larose, Benoit
Tesson, Pascal
THEORETICAL COMPUTER SCIENCE, 2009, 410 (18) : 1629 - 1647
[39] Backjump-based backtracking for constraint satisfaction problems
Dechter, R
Frost, D
ARTIFICIAL INTELLIGENCE, 2002, 136 (02) : 147 - 188
[40] OPTIMIZATION APPROACHES TO CONSTRAINT SATISFACTION PROBLEMS IN COMPUTER VISION
YAMAMOTO, K
IMAGE AND VISION COMPUTING, 1995, 13 (05) : 335 - 340

← 1 2 3 4 5 →