Solving constraint satisfaction problems

OData support
Supervisor:
Dr. Mann Zoltán Ádám
Department of Computer Science and Information Theory

The constraint satisfaction problem is the natural, obvious model of several combinatorial problems, hence many different, constraint satisfaction solving algorithms are known. Among them, one of the most commonly used exact algorithm is the backtracking algorithm. Since the constraint satisfaction problem is NP-complete, the known exact algorithms’ runtime grows quite rapidly in the worst case, nevertheless we can handle many problems efficiently in the practice. Thus finding accelerations and heuristics, which could possibly improve the efficiency of the backtracking algorithm without violating its exact nature, is field of interest in constraint satisfaction problem solving.

My thesis covers the following:

• Presenting the backtracking algorithm, and its known heuristics and accelerations. Defining the used techniques descriptively and formally. Presenting the technique of frequent restarting and my backtracking search based best-first-search algorithm.

• Presenting the structure of my framework, in which the algorithms are implemented. During the implementation, I achieve to utilize inter alia the conflict driven backtracking, the frequent restarting and the BFS-like iteration using the backtracking algorithm.

• Comparing the results of the implemented algorithms for different real and random, solvable and unsolvable problem instances, and drawing conclusions about the efficiency of the described accelerations and mainly the frequent restarting and BFS-like iteration.

Downloads

Please sign in to download the files of this thesis.