Generalizing Partial Order and Dynamic Backtracking

Abstract

RecentlyFtwo new backtracking algorithmsF dynamic backtracking (DB) and partial order dynamic backtrack-ing (PDB) have been presented. These algorithms have the property to be additive on disjoint subproblems and yet use only polynomial space. Unlike DBFPDB only im-poses a partial search order and therefore appears to have more freedom than DB to explore the search space. HoweverFboth algorithms are not directly comparable in terms of flexibility. In this paper we present new backtracking algorithms that are obtained by relaxing the ordering conditions of PDB. This gives them addi-tional flexibility while still being additive on disjoint subproblems. In particularF we show that our algo-rithms generalize both DB and PDB.