TAOCP 7.2.2.1 Exercise 31

Section 7.2.2.1: Dancing Links

Exercise 31. [M21] The running time of Algorithm X depends on the order of primary items in the active list, as well as on the order of options in the individual item lists. Explain how to randomize the algorithm so that (a) every item list is in random order after step X1; (b) step X3 chooses randomly among items with the minimum LB.

Verified: yes
Solve time: 1m23s

Solution

The two requested randomizations can be obtained by adding random choices before the deterministic parts of Algorithm X begin and by replacing the deterministic minimum selection in step X3 by a randomized tie-breaking rule.

For part (a), the goal is to make every item list random after step X1. The item lists are the vertical lists headed by the item nodes. The order of the nodes in each such list affects the order in which the options are considered by the recursive step X3. Before the first execution of step X2 or X3, independently randomize each vertical list.

For an item $i$, let its current list be

$p_1,p_2,\ldots,p_{\operatorname{LEN}(i)}.$

Generate a uniformly random permutation $\pi$ of

$1,2,\ldots,\operatorname{LEN}(i),$

and replace the vertical successor order by

$p_{\pi(1)},p_{\pi(2)},\ldots,p_{\pi(\operatorname{LEN}(i))}.$

The circular links are changed by setting

\operatorname{ULINK}(p_{\pi(j+1)})\leftarrow p_{\pi(j)}$$ for $1\le j<\operatorname{LEN}(i)$, with the first and last nodes joined back to the item header: $$\operatorname{ULINK}(p_{\pi(1)})\leftarrow i,\qquad \operatorname{DLINK}(i)\leftarrow p_{\pi(1)},$$ $$\operatorname{DLINK}(p_{\pi(\operatorname{LEN}(i))})\leftarrow i,\qquad \operatorname{ULINK}(i)\leftarrow p_{\pi(\operatorname{LEN}(i))}.

The number $\operatorname{LEN}(i)$ is unchanged, and every node remains in exactly one vertical list. Hence the representation still satisfies the invariants required by $\operatorname{cover}$, $\operatorname{hide}$, $\operatorname{uncover}$, and $\operatorname{unhide}$. Since the permutation is chosen uniformly, every possible ordering of the item list is obtained with the same probability.

For part (b), step X3 chooses an item with the minimum lower bound value. Let the active primary items be

$i_1,i_2,\ldots,i_s,$

and suppose the minimum value of LB is

$m=\min_{1\le j\le s}\operatorname{LB}(i_j).$

Form the set

$S={i_j:1\le j\le s,\ \operatorname{LB}(i_j)=m}.$

Replace the deterministic choice in step X3 by the following rule: generate a uniformly random element of $S$ and choose that item for covering.

Every item selected by this rule has the same minimum LB value, so the pruning property of step X3 is unchanged. The backtrack tree may differ because different items with equal LB values can lead to different orders of recursive exploration, but every possible choice permitted by the MRV heuristic remains possible.

Combining the two modifications gives the desired randomized Algorithm X. The initial random permutations ensure the condition in part (a), and the uniform choice from the set $S$ ensures the condition in part (b). ∎