Date of Award
2004
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Computer Science.
Supervisor
Goodwin, S.
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
Constraint Satisfaction Problems (CSPs) can be used to represent and solve many problems in Artificial Intelligence and the real world. When solving Constraint Satisfaction Problems, many of the methods developed and studied have focused only on the solution of binary CSPs while a large portion of real life problems are naturally modeled as non-binary CSPs. In this thesis we have designed an empirical study to investigate the behaviour of several local search methods in primal and dual constraint graph representations when solving non-binary CSPs. Local search methods tend to find a solution quickly since they generally give up the guarantee of completeness for polynomial time performance. Such local search methods include simple hill-climbing, steepest ascent hill-climbing and min-conflicts heuristics hill-climbing. We evaluate the performance of these three algorithms in each representation for a variety of parameter settings and we compare the search time cost means of two groups to support the comparison. Our comparison shows that we can use local search to solve a CSP with tight constraints in its dual representation and gain a better performance than using it in its primal representation. When constraints are getting looser, using local search in primal representation is a better choice. Among the three local search methods used in our empirical study, min-conflicts heuristics hill-climbing always gain the best performance while steepest ascent hill-climbing tends to have the worst performance and simple hill climbing is in the middle or sometimes it is the best. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2004 .H824. Source: Masters Abstracts International, Volume: 43-01, page: 0237. Adviser: Scott Goodwin. Thesis (M.Sc.)--University of Windsor (Canada), 2004.
Recommended Citation
Huang, Mingyan, "Dueling CSP representations: Local search in the primal versus dual constraint graph." (2004). Electronic Theses and Dissertations. 1787.
https://scholar.uwindsor.ca/etd/1787