Return to search

Quantified weighted constraint satisfaction problems.

Mak, Wai Keung Terrence. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 100-104). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Weighted Constraint Satisfaction Problems --- p.2 / Chapter 1.3 --- Quantified Constraint Satisfaction Problems --- p.3 / Chapter 1.4 --- Motivation and Goal --- p.4 / Chapter 1.5 --- Outline of the Thesis --- p.6 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.7 / Chapter 2.1.1 --- Backtracking Tree Search --- p.9 / Chapter 2.1.2 --- Local Consistencies for solving CSPs --- p.11 / Node Consistency (NC) --- p.13 / Arc Consistency (AC) --- p.14 / Searching by Maintaining Arc Consistency --- p.16 / Chapter 2.1.3 --- Constraint Optimization Problems --- p.17 / Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.19 / Chapter 2.2.1 --- Branch and Bound Search (B&B) --- p.23 / Chapter 2.2.2 --- Local Consistencies for WCSPs --- p.25 / Node Consistency --- p.26 / Arc Consistency --- p.28 / Chapter 2.3 --- Quantified Constraint Satisfaction Problems --- p.32 / Chapter 2.3.1 --- Backtracking Free search --- p.37 / Chapter 2.3.2 --- Consistencies for QCSPs --- p.38 / Chapter 2.3.3 --- Look Ahead for QCSPs --- p.45 / Chapter 3 --- Quantified Weighted CSPs --- p.48 / Chapter 4 --- Branch & Bound with Consistency Techniques --- p.54 / Chapter 4.1 --- Alpha-Beta Pruning --- p.54 / Chapter 4.2 --- Consistency Techniques --- p.57 / Chapter 4.2.1 --- Node Consistency --- p.62 / Overview --- p.62 / Lower Bound of A-Cost --- p.62 / Upper Bound of A-Cost --- p.66 / Projecting Unary Costs to Cθ --- p.67 / Chapter 4.2.2 --- Enforcing Algorithm for NC --- p.68 / Projection Phase --- p.69 / Pruning Phase --- p.69 / Time Complexity --- p.71 / Chapter 4.2.3 --- Arc Consistency --- p.73 / Overview --- p.73 / Lower Bound of A-Cost --- p.73 / Upper Bound of A-Cost --- p.75 / Projecting Binary Costs to Unary Constraint --- p.75 / Chapter 4.2.4 --- Enforcing Algorithm for AC --- p.76 / Projection Phase --- p.77 / Pruning Phase --- p.77 / Time complexity --- p.79 / Chapter 5 --- Performance Evaluation --- p.83 / Chapter 5.1 --- Definitions of QCOP/QCOP+ --- p.83 / Chapter 5.2 --- Transforming QWCSPs into QCOPs --- p.90 / Chapter 5.3 --- Empirical Evaluation --- p.91 / Chapter 5.3.1 --- Random Generated Problems --- p.92 / Chapter 5.3.2 --- Graph Coloring Game --- p.92 / Chapter 5.3.3 --- Min-Max Resource Allocation Problem --- p.93 / Chapter 5.3.4 --- Value Ordering Heuristics --- p.94 / Chapter 6 --- Concluding Remarks --- p.96 / Chapter 6.1 --- Contributions --- p.96 / Chapter 6.2 --- Limitations and Related Works --- p.97 / Chapter 6.3 --- Future Works --- p.99 / Bibliography --- p.100

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_327344
Date January 2011
ContributorsMak, Wai Keung Terrence., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering.
Source SetsThe Chinese University of Hong Kong
LanguageEnglish, Chinese
Detected LanguageEnglish
TypeText, bibliography
Formatprint, ix, 104 p. : ill. ; 30 cm.
RightsUse of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/)

Page generated in 0.0017 seconds