TAOCP 7.2.2.1 Exercise 85

Section 7.2.2.1: Dancing Links

Exercise 85. [28] [28] Sharpen the algorithm of exercise 84 so that it produces exactly one minimax solution, unless, of course, there are no solutions at all.

Verified: no
Solve time: 2m11s

Setup

Let the options of the XCC problem be numbered $1,\ldots,M$. A solution $S$ has value

$$ \mu(S)=\max{r:r\text{ is the number of an option in }S}. $$

A minimax solution is a solution $S$ for which $\mu(S)$ is minimum among all solutions.

Exercise 84 modifies Algorithm C so that it finds all solutions with the smallest possible value of $\mu(S)$. The purpose here is to sharpen that modification so that only one such solution is produced, while still producing no solution when the instance has no solution.

The required modification must preserve the ordering of Algorithm C's search, because the first minimax solution encountered will be used as the unique answer.

Solution

The modification is to maintain the best maximum option number found so far and to stop exploring branches that cannot improve this value.

Introduce a variable $b$, initialized by

$$ b\leftarrow M+1 . $$

The variable $b$ records the smallest value of $\mu(S)$ among solutions already found. When Algorithm C reaches a successful terminal state, let the current partial solution be $S$. The algorithm performs the following operation.

$$ \mu(S)<b, $$

then the current answer is discarded, $S$ is saved as the new answer, and

$$ b\leftarrow\mu(S). $$

$$ \mu(S)\geq b, $$

the solution is ignored and the search continues without changing $b$.

The additional pruning rule is applied whenever Algorithm C considers an option numbered $r$. If

$$ r\geq b, $$

the option is skipped. Otherwise the option is processed exactly as in Algorithm C.

This differs from exercise 84 only in the treatment of equality. Exercise 84 must continue when $r=b$, because another option of the same maximum number might produce another minimax solution. Exercise 85 rejects such branches, because the goal is to output only one minimax solution.

To prove correctness, consider first the solution produced by this modified algorithm. Suppose that the final saved solution is $S$. The value $b$ was assigned only when a complete solution was reached, and therefore

$$ b=\mu(S). $$

Every later explored option has number strictly less than $b$, because options numbered $r\geq b$ are rejected. Hence no later solution can have maximum option number smaller than $b$. Therefore $S$ is minimax.

Now suppose that the instance has at least one solution, and let $T$ be a minimax solution. Consider the first moment during the search when a branch containing all options of $T$ would be rejected. A rejection occurs only because some option number $r$ in that branch satisfies

$$ r\geq b. $$

If this happens, a solution with maximum option number at most $r$ has already been found. Since $T$ is minimax,

$$ \mu(T)\leq r. $$

The already found solution therefore has maximum option number no larger than $\mu(T)$. Since $\mu(T)$ is minimal, the previously found solution is also minimax. Thus rejecting the branch containing $T$ cannot prevent the algorithm from having already stored a minimax solution.

The algorithm stores the first minimax solution it finds. Every later possible minimax solution has maximum option number equal to $b$, so its first option number encountered on the search path would satisfy

$$ r\geq b $$

at the point where equality with the current best value arises. The pruning rule rejects that branch before another minimax solution can be reported. Therefore exactly one minimax solution is produced.

If no solution exists, the terminal success step is never reached, so no answer is stored.

Verification

The invariant during the search is that $b$ is either $M+1$, when no solution has yet been found, or the maximum option number of the unique stored minimax solution among all solutions discovered so far.

Initially the invariant holds because $b=M+1$ and no solution has been stored. When a solution with smaller maximum option number is found, the assignment

$$ b\leftarrow\mu(S) $$

preserves the invariant because the stored solution is replaced by a better one. When a solution with maximum option number at least $b$ is found, it cannot improve the stored value and is discarded, preserving the invariant.

The pruning condition

$$ r\geq b $$

cannot remove every minimax solution before one is stored, because before the first minimax solution is found we have $b=M+1$, so no option number in $1,\ldots,M$ is rejected. After a minimax solution is stored, every remaining minimax solution has maximum option number equal to $b$, and all such branches are intentionally removed.

Therefore the modified Algorithm C returns one and only one minimax solution whenever a solution exists.

This completes the proof.

∎

Notes

The modification can be viewed as changing the objective from enumeration to optimization. Exercise 84 retains all branches reaching the optimum value, whereas this modification turns the first optimum found into a permanent incumbent and removes all branches that can only reproduce the same optimum.