Date Available
12-7-2011
Year of Publication
2003
Document Type
Thesis
College
Engineering
Department
Computer Science
First Advisor
Miroslaw Truszczynski
Abstract
Solution of any search problem lies in its search space. A search is a systematic examination of candidate solutions of a search problem. In this thesis, we present a search heuristic that we can cr-smodels. cr-smodels prunes the search space to quickly reach to the solution of a problem. The idea is to pick an atom for branching , that lowers the growth rate of the linear recurrence and thuse, minimizes the remaining search space. Our goal in developing cr-smodels is to develop a search heuristic that is efficient on a wide range of problems. Then, we test cr-smodels over a wide range of randomly generated benchmarks. we observed that often randomly generated graphs with no Hamiltonian cycle were trivial to solve. Since, Hamiltonian cycle is an important benchmark problem, my other goal is to develop techniques that generate hard instances of graphs with no Hamiltonian cycle.
Recommended Citation
Singhi, Soumya, "Computing stable models of logic programs" (2003). University of Kentucky Master's Theses. 223.
https://uknowledge.uky.edu/gradschool_theses/223
