Improving backtrack search : three case studies of localized dynamic hybridization
Author(s)
El-Sakkout, Hani
Abstract
Hybrid constraint programming algorithms can outperform their pure counterparts on constraint satisfaction and optimization problems. This thesis considers how hybridization can be used to improve the conventional backtrack search algorithm. Specifically, techniques for localized, dynamic hybridization are proposed and investigated: the methods hybridized with backtrack search target specific sub-problems, and co-operate with backtrack search as it executes. The thesis consists of three case studies exploring different problems. Each case study describes an original algorithm that uses this style of hybridization to enhance the efficiency of backtrack search. A conclusion reviews the forms of hybridization the algorithms exemplify.
Version
Open Access
Date Awarded
1999
Copyright Statement
Attribution-Non Commercial-No Derivatives 4.0 International Licence (CC BY-NC-ND)
Advisor
Wallace, Mark
Publisher Department
Department of Computing
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)