在約束滿足問題中使用集合變量時，一般會利用集合範團相容算法結合基數推理來進行求解。對比單獨運用集合範團相容算法產生更多的剪枝。多重集合變量是集合變量的推廣，同一個元素可以在一個多重集合中出現多次。在本論文中，我們先把基數推理運用到多重集合變量上。男外，我們提出在建模時把多重集合的品種(即不同元素的數量)一同考慮，使模型能更具體地把問題表達出來，以加強約束傳播能力。為此，我們推論出一系列有關多重集合的品種推理規則。我們還演示了如何在一些常見的約束上運用品種推理。在子集範圍的表示方法中，一些如變量的長度因素(基數)和字典序的位置的重要訊息一概都被忽略，而這些訊息往往在求解的過程中能增加約束傳播能力。因此，按照集合變量的長度法表示方法，我們為多重集合變量提供八種以字典序為基礎的表示方法。多重集合變量中的域會按照不同的字典序，以全序關係順序排列起來。實驗結果表明，子集範團表示方法結合基數推理和品種推理，可以有效地減少問題的搜索空間，從而提升包含多重集合變量的約束滿足問題的求解效率。對於某些問題，子集範圍表示方法和以字典序為基礎的表示方法相比，後者更能提高修剪的效果和減少求解時所需要的運行時間。 / Set variables in constraint satisfaction problems (CSPs) are typically propagated by enforcing set bounds consistency together with cardinality reasoning, which uses some inference rules involving the cardinality of a set variable to produce more prunings than set bounds propagation alone. Multiset variables are a generalization of set variables by allowing the elements to have repetitions. In this thesis, we first generalize cardinality reasoning for multiset variables. In addition, we propose to exploit the variety of a multiset--the number of distinct elements in it--to improve modeling expressiveness and further enhance constraint propagation. We derive a number of inference rules involving the varieties of multiset variables. The rules interact varieties with the traditional components of multiset variables (such as cardinalities) to obtain stronger propagation. We also demonstrate how to apply the rules to perform variety reasoning on some common multiset constraints. While the subset bounds representation neglects to consider the information about the length (cardinality) and position in the lexicographic ordering, which can be important in many problems, we follow the length-lex (LL) representation for set variables and consider eight lex-based representations which give a total order for the multiset domain. The bounds of the multiset variables are maintained according to eight different orderings: length(co)lex (LL/LC), variety-(co)lex (VL/VC), length-variety-(co)lex (LVL/LVC), and variety-length-(co)lex (VLL/VLC) orderings. We implement both types of multiset variable representations and evaluate their performance. Experimental results show that performing variety reasoning on top of cardinality reasoning can effectively reduce more search space and achieve better runtime in solving multiset CSPs. In some kinds of problems, lex-based representations offer significantly better pruning and runtime when compared to the subset bounds representations. / Detailed summary in vernacular field only. / Woo, Hiu Chun. / "October 2012." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 101-108). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Set Variables --- p.2 / Chapter 1.3 --- Multiset Variables --- p.3 / Chapter 1.4 --- Motivations and Goals --- p.3 / 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 --- p.10 / Chapter 2.1.3 --- Local Consistencies in Backtracking Search --- p.15 / Chapter 2.2 --- Set Variables --- p.17 / Chapter 2.2.1 --- Tree Searching --- p.19 / Chapter 2.2.2 --- Set Bounds Consistency --- p.21 / Chapter 2.2.3 --- Length-lex Representation --- p.22 / Chapter 2.3 --- Multiset Variables --- p.23 / Chapter 2.3.1 --- Basic Multiset Variable Representations --- p.24 / Chapter 2.3.2 --- Multiset Bounds Consistency --- p.27 / Chapter 2.3.3 --- Multiset Constraints --- p.28 / Chapter 2.3.4 --- Enforcing Local Consistency --- p.28 / Chapter 3 --- Cardinality and Variety Information in Multisets --- p.32 / Chapter 3.1 --- Cardinality Variable --- p.32 / Chapter 3.2 --- Cardinality Reasoning --- p.34 / Chapter 3.3 --- Variety Variable --- p.39 / Chapter 3.4 --- Inferences within One Multiset Variable --- p.42 / Chapter 3.4.1 --- Inferences between occ(i, S) and CS --- p.42 / Chapter 3.4.2 --- Inferences between occ(i, S) and VS --- p.43 / Chapter 3.4.3 --- Inferences between CS and VS --- p.44 / Chapter 3.4.4 --- Inferences among occ(i, S), CS, and VS --- p.45 / Chapter 3.4.5 --- Failure --- p.47 / Chapter 3.4.6 --- Discussion --- p.47 / Chapter 3.5 --- Cardinality-Variety Reasoning --- p.50 / Chapter 4 --- Lex-induced Orderings in Multisets --- p.56 / Chapter 4.1 --- Multiset Variables --- p.57 / Chapter 4.2 --- Lex Orderings --- p.57 / Chapter 4.2.1 --- Length-lex Ordering --- p.58 / Chapter 4.2.2 --- Variety-lex Ordering --- p.58 / Chapter 4.2.3 --- Length-variety-lex Ordering --- p.58 / Chapter 4.2.4 --- Variety-length-lex Ordering --- p.58 / Chapter 4.3 --- Colex Orderings --- p.59 / Chapter 4.3.1 --- Length-colex Ordering --- p.59 / Chapter 4.3.2 --- Variety-colex Ordering --- p.59 / Chapter 4.3.3 --- Length-variety-colex Ordering --- p.59 / Chapter 4.3.4 --- Variety-length-colex Ordering --- p.60 / Chapter 4.4 --- Exactness --- p.62 / Chapter 4.5 --- Compactness --- p.67 / Chapter 4.6 --- Empirical Comparisons --- p.69 / Chapter 4.7 --- Bounds Consistency --- p.73 / Chapter 5 --- Experiments --- p.78 / Chapter 5.1 --- Template Design Problem --- p.79 / Chapter 5.2 --- Generalized Extended Steiner System --- p.82 / Chapter 5.3 --- Generalized Social Golfer Problem --- p.85 / Chapter 5.4 --- Generalized Warehouse Location Problem --- p.87 / Chapter 5.5 --- Discussion --- p.90 / Chapter 6 --- Related Work --- p.93 / Chapter 6.1 --- Set Variables and Constraints --- p.93 / Chapter 6.1.1 --- Subset Bounds Representation --- p.94 / Chapter 6.1.2 --- Length-lex Representation --- p.95 / Chapter 6.2 --- Weighted Constraint Satisfaction with Set Variables --- p.96 / Chapter 6.3 --- Multiset Variables and Constraints --- p.96 / Chapter 7 --- Concluding Remarks --- p.98 / Chapter 7.1 --- Contributions --- p.98 / Chapter 7.2 --- Future Work --- p.99 / Bibliography --- p.101
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_327990 |
| Date | January 2013 |
| Contributors | Woo, Hiu Chun., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (ix, 108 leaves) : ill. |
| Rights | Use 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.0027 seconds