ISE 390 -- Programming Challenges -- Week 7 Notes
This Weeks Goals:
To review the principles of backtracking and exhaustive search.
To introduce this week's problems on backtracking.
Business:
Email me a *single* attachment of a Unix shar or tar file
with all your programs to date. Feel free to add a README
with any explanation you want. I'd like to receive this
by the first class after break.
Backtracking
Backtracking is a systematic way to go through all the possible
configurations of a search space.
In the general case, we assume our solution is a vector
$v=(a_{1}, a_{2},..., a_{n})$ where each element $a_i$ is selected
from a finite ordered set $S_{i}$,
We build from a partial solution of length $k$
$v = (a_{1}, a_{2},..., a_{k})$ and try to extend it by adding another
element. After extending it, we will test whether what we have so
far is still possible as a partial solution.
If it is still a candidate solution, great.
If not, we delete $a_{k}$ and try the next element from $S_k$.
In pseudocode, this is:
Compute $S_{1}$, the set of candidate first elements of $v$.
$k = 1$
While $k > 0$ do
While $S_{k} \neq \emptyset$ do (*advance*)
$a_{k}$ = an element in $S_{k}$
$S_{k} \leftarrow S_{k} - {a_{k}}$
if ($a_{1}, a_{2},..., a_{k}$) is solution, print!
$k = k + 1$
compute $S_{k}$, the candidate $k$th elements given $v$
$k = k - 1$ (*backtrack*)
Recursive Backtracking
Recursion can be used for elegant and easy backtracking implementation:
Backtrack(a, k)
if a is a solution, print(a)
else {
$k = k +1$
compute $S_{k}$
while $S_{k} \neq \emptyset$ do
$a_{k}$ = an element in $S_{k}$
$S_{k}$ = $S_{k} - a_{k}$
Backtrack(a, k)
}
Backtracking can easily be used to iterate through all subsets
or permutations of a set.
Backtracking ensures correctness by enumerating all possibilities.
For backtracking to be efficient, we must prune the search space.
Constructing all Subsets
To construct all $2^n$ subsets, set up an array/vector of $n$ cells,
where the value of $a_i$ is either true or false, signifying whether
the $i$th item is or is not in the subset.
To use the notation of the general backtrack algorithm,
$S_k = (true, false)$, and $v$ is a solution whenever $k \geq n$.
What order will this generate the subsets of $\{1,2,3\}$?
(1) --- (1,2) --- (1,2,3)* --- (1,2,-)* --- (1,-) --- (1,-,3)* ---
(1,-,-)* --- (1,-) --- (1) --- (-) --- (-,2) --- (-,2,3)* ---
(-,2,-)* --- (-,-) --- (-,-,3)* --- (-,-,-)* --- (-,-) --- (-) --- ()
Constructing all Permutations
To construct all $n!$ permutations, set up an array/vector of
$n$ cells, where the value of $a_i$ is an integer from $1$ to $n$
which has not appeared thus far in the vector, corresponding to
the $i$th element of the permutation.
To use the notation of the general backtrack algorithm,
$S_k = (1,\ldots,n) - v$, and $v$ is a solution whenever $k \geq n$.
(1) --- (1,2) --- (1,2,3)* --- (1,2) --- (1) --- (1,3) ---
(1,3,2)* --- (1,3) --- (1) --- () --- (2) --- (2,1) ---
(2,1,3)* --- (2,1) --- (2) --- (2,3) --- (2,3,1)* --- (2,3) --- ()
(2) --- () --- (3) --- (3,1) --- (3,1,2)* --- (3,1) --- (3) ---
(3,2) --- (3,2,1)* --- (3,2) --- (3) --- ()
The $n$-Queens Problem
The first use of pruning to deal with the combinatorial explosion
was by the king who rewarded the fellow who discovered chess!
In the eight Queens, we prune whenever one queen threatens another.
Assigned Problems:
148 -- Find all sets of words which give an anagram of a sentence.
Efficiency is critical for such a potentially large search.
165 -- What set of k stamp denominations will maximize the range of
values 1 .. n(h,k) you can reach with at most h stamps per letter?
167 -- Interesting variation of the 8-queens problem.
195 -- Construct all permutations of a multiset. Efficiency matters,
so constructing all permutations, sorting them and throwing
away duplicates is probably too slow. Consider permutations
of aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.
386 -- This problem is very similar to one of the war stories in
"The Algorithm Design Manual". Look for an O(n^2) solution
instead of O(n^4).