Combining the Scalability of Local Search with the Pruning Techniques of Systematic Search

摘要: Systematic backtracking is used in many constraint solvers and combinatorial optimisation algorithms. It complete can be combined with powerful search pruning techniques such as branch-and-bound, propagation dynamic variable ordering. However, it often scales poorly to large problems. Local incomplete, has the additional drawback that cannot exploit techniques, making uncompetitive on some Nevertheless its scalability makes superior for applications. This paper describes a hybrid approach called Incomplete Dynamic Backtracking, very flexible form of sacrifices completeness achieve local search. forward checking ordering, evaluated three problems: n-queens problem out-performs best algorithms; finds optimal Golomb rulers much more quickly than constraint-based backtracker, better genetic algorithm; benchmark graphs larger cliques almost all other tested We argue this actually space consistent partial assignments, offering generic way combining standard