An Analysis of Backtracking with Search Rearrangement
Paul Walton Purdom, Cynthia A. Brown · SIAM Journal on Computing · 1983
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 \geqq 3)$, and $v^\alpha $ terms $((s/2) < \alpha < s)$, the average number of nodes in a search rearrangement backtrack tree is $\exp [\Theta (v^{(s - \alpha - 1)/(s - 2)} )]$ (i.e., for some positive constants $a_1 ,a_2 $, and $v_0 $, when $v \geqq v_0 $ the number of nodes is between $\exp (a_1 v^{(s - \alpha - 1)/(s - 2)} )$ and $\exp (a_2 v^{(s - \alpha - 1)/(s - 2)} )$. For $1 < \alpha \leqq s/2$ the average number of nodes is between $\exp [\Theta (v^{(s - \alpha - 1)/(s - 2)} )]$ and $\exp [\Theta ((\ln v)^{(s - 1)/(s - 2)} v^{(s - \alpha - 1)/(s - 2)} )]$. This compares with $\exp [\Theta (v^{(s - \alpha )/(s - 1)} )]$ for ordinary backtracking. For $1 < \alpha < 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.