An Analysis of Backtracking with Search Rearrangement

The search rearrangement backtracking algorithm of Bitner and Reingold Comm. ACM, 18 (1975), pp. 651–655 introduces at each level of the backtrack tree a variable with a minimal number of remaining values; search order may differ on different branches. For conjunctive normal form formulas with v variables, s literals per term (s 3), and v^ terms ( (s/2) < < s), the average number of nodes in a search rearrangement backtrack tree is (v^ (s - - 1) / (s - 2) ) (i. e. , for some positive constants a₁, a₂, and v₀, when v v₀ the number of nodes is between (a₁ v^ (s - - 1) / (s - 2) ) and (a₂ v^ (s - - 1) / (s - 2) ). For 1 < s/2 the average number of nodes is between (v^ (s - - 1) / (s - 2) ) and ( (v) ^ (s - 1) / (s - 2) v^ (s - - 1) / (s - 2) ). This compares with (v^ (s -) / (s - 1) ) for ordinary backtracking. For 1 < < s, simple search rearrangement has approximately the same effect on speeding up backtracking as does reducing the problem complexity by decreasing the number of literals per term by one. Thus simple search rearrangement backtracking leads to a dramatic improvement in the expected running time.