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

共 20 条

[1]

Bellman R., 1957, DYNAMIC PROGRAMMING

[2]

Boutilier C, 1999, J ARTIF INTELL RES, V11, P1

[3]

Boyan J. A., 1996, Machine Learning. Proceedings of the Thirteenth International Conference (ICML '96), P63

[4]

Cormen T. H., 1990, INTRO ALGORITHMS

[5]

Fowler D. W., 2000, Principles and Practice of Constraint Programming - CP 2000. 6th International Conference, CP 2000. Proceedings (Lecture Notes in Computer Science Vol.1894), P500

[6] INCREASING TREE-SEARCH EFFICIENCY FOR CONSTRAINT SATISFACTION PROBLEMS [J].

HARALICK, RM ;

ELLIOTT, GL .

ARTIFICIAL INTELLIGENCE, 1980, 14 (03) :263-313

[7]

HENTENRYCK PV, 1992, ARTIF INTELL, V57, P291

[8]

Howard R. A., 1960, Dynamic Programming and Markov Processes

[9] A theoretical evaluation of selected backtracking algorithms [J].

Kondrak, G ;

vanBeek, P .

ARTIFICIAL INTELLIGENCE, 1997, 89 (1-2) :365-387

[10]

Littman ML, 1999, SIXTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-99)/ELEVENTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE (IAAI-99), P667

← 1 2 →