Algorithms Course Notes
Backtracking 2
SUMMARY
Backtracking with permutations.
Application to the Hamiltonian cycle problem.
Backtracking with combinations.
Principles and analysis.
PERMUTATIONS
Problem: Generate all permutations of n distinct numbers.
Solution:
Backtrack through all n-ary strings of length n, pruning out
non-permutations.
Keep a Boolean array U[1..n], where U[m] is true iff n is
unused.
Keep current permutation in an array A[1..n].
Aim is to call process (A) once with A[1..n] containing each
permutation.
Call procedure permute(n):
procedure permute(m)
comment process all perms of length m
1.
2.
3.
4.
if m=0 then process(A) else
for j := 1 to n do
if U[j] then
U[j] := false
5.
A[m] := j; permute(m -1)
6.
U[j] := true
Note: this is what we did in the Hamiltonian cycle algorithm. A
Hamiltonian cycle is a permutation of the nodes of the graph.
ANALYSIS
Clearly, the algorithm runs in time O(nn). But this analysis is not
tight: it does not take into account pruning.
How many times is line 3 executed? Running time will be big-O of
this.
What is the situation when line 3 is executed? The algorithm has, for
some 0 i < n,
Filled in i places at the top A with part of a permutation, and
tries n candidates for the next place in line 2.
What do the top i places in a permutation look like?
i things chosen from n without duplicates
Permuted in some way
Permutations of i
things chosen from n
try n
things
How many ways are there of filling in part of a permutation?
n
i!
i
Therefore, number of items line 3 is executed is
n
n i!
i 0 i
n 1
n 1
n
i 0
n!
( n i )!
n
1
n.n!
i 1 i!
( n 1)!(e 1)
1.718( n 1)!
Analysis of Permutation Algorithm
Therefore, procedure permutes run in time O((n+1)!).
This is improvement over O(nn). Recall that
n!~
n
2n
e
FASTER PERMUTATIONS
The permutation generation algorithm is not optimal: off by a
factor of n
generates n! permutations
Takes time O((n+1)!)
A better algorithm : use divide and conquer to devise a faster
backtracking algorithm that generates only permutations.
Initially set A[i] = i for all 1 i n.
Instead of setting A[ n ] to 1n in turn, swap values from
A[1n 1 ] into it.
4
4
All permutations with 4 in the last place
All permutations with 3 in the last place
All permutations with 2 in the last place
?
1
1
All permutations with 1 in the last place.
procedure permute( m )
comment process all perms in A[1..m]
1. if m = 1 then process (A) else
2.
permute ( m 1)
3.
for i := 1 to m 1 do
4.
swap A[m] with A[j] for some 1 j m
5.
permute (m 1)
Problem: how to make sure that the values swapped into A[m]
in line 4 are distinct?
Solution: Make sure that A is reset after every recursive call,
and swap A[m] with A[ i ].
1.
2.
3.
4.
5.
6.
procedure permute (m)
if m = 1 then process else
permute ( m 1)
for i : = m 1 downto 1 do
swap A[m] with A [ i ]
permute ( m 1)
swap A[m] with A[ i ]
n=2
1 2 3 4
n=4
1 2 4 3
1 4 3 2
4 3 2 1
2 1 3 4
4 2 1 3
4 1 3 2
4 2 3 1
1 2 3 4
2 4 1 3
1 4 3 2
3 2 4 1
4 2 1 3
1 3 4 2
2 3 4 1
1 2 4 3
3 1 4 2
3 2 4 1
1 3 4 2
4 2 3 1
1 4 3 2
1 2 3 4
n=2
1 3 2 4
n=3
n=3
3 1 2 4
n=4
1 3 2 4
Unprocessed at
1 2 3 4
3 2 1 4
3 4 1 2
2 3 1 4
4 3 1 2
3 2 1 4
3 4 1 2
1 2 3 4
1 4 3 2
1 2 4 3
1 2 3 4
2 1 4 3
4 2 3 1
1 2 4 3
2 4 3 1
1 4 2 3
4 2 3 1
4 1 2 3
4 3 2 1
1 4 2 3
3 4 2 1
1 2 3 4
ANALYSIS
Let T(n) be the number of swaps made by permute(n). Then
T(1) = 0, and for n > 2,
T(n) = nT( n - 1) + 2( n - 1)
Claim: For all n 1, T(n) 2n! 2.
Proof: Proof by induction on n. the claim is certainly true for n
= 1. Now suppose the hypothesis is true for n. then,
T ( n 1) ( n 1)T ( n) 2n
( n 1)(2n!2) 2n
2( n 1)!2
Hence, procedure permute runs in time O(n!), which is
optimal.
Hamiltonian Cucles on Dense Graphs
Use adjacency matrix: M [ i, j] true iff (i, j) E.
1.
2.
3.
for i : = 1 to n do
A[ i ]: = i
hamilton( n 1 )
procedure hamilton( m)
comment find Hamiltonian cycle from A[m]
with m unused nodes
if m = 0 then process( A ) else
5.
for j : = m downto 1 do
6.
if M[A[m + 1], A[ j ]] then
7.
swap A[m] with A[ j ]
8.
hamilton(m - 1)
9.
swap A[m] with A[ j ]
procedure process(A)
comment check that the cycle is closed
10. if M[A[1], n] then print (A)
4.
ANALYSIS
Therefore, the Hamiltonian circuits algorithms run in time
O( dn ) (using generalized strings)
O((n 1 )!) (using permutations).
Which is the smaller of the two bounds? It depends on d. the
string algorithm is better if d n/e ( e = 2.7183)
Notes on algorithm:
Note upper limit in for loop on line 5 is m, not m 1: why?
Can also be applied to travelling salesperson.
COMBINATIONS
Problem: Generate all the combinations of n things chosen r at
a time.
Soultion: Keep the current combination in an array A[1..r]. Call
procedure choose(n, r).
procedure choose(m, q)
comment choose q elements out of 1..m
if q = 0 then process(A )
else for i:= q to m do
A[q] := i
choose(i 1, q 1 )
CORRECTNESS
Proved in three parts:
1.
Only combinations are processes.
2.
The right number of combinations are processed.
3.
No combination is processed twice.
Claim 1. If 0 r n, then in combinations processed by choose(n, r),
A[1..r] contains a combination of r things chosen from 1..n.
Proof: Proof by induction on r. the hypothesis is vacuously true for
r= 0.
CORRECTNESS
Now suppose that r > 0 and for all i r 1, in
combinations processed by choose(i, r 1), A[1..r 1]
contains a combination of r 1 things chosen from 1..i.
Now, choose(n, r) calls choose(i 1, r 1) with i running
from r to n. Therefore, by the induction hypothesis and
since A[r] is set to i, in combinations processed by
choose(n, r), A[1..r] contains a combination of r 1 things
chosen from 1..i -1, followed by the value i.
CORRECTNESS
Claim 2. a call to choose(n, r) processes exactly
n
combinations.
Proof: Proof by induction on r. the hypothesis is certain true
for r = 0.
Now suppose that r > 0 and a call to choose(i, r -1 )
Generates exactly i
r 1
Combinations, for all r 1 i n.
CORRECTNESS
Now, choose(n, r) calls choose( i 1, r 1) with i running from r to
n. Therefore, by the induction hypothesis, the number of
combinations generated is
i 1
r 1
i r
r 1
i r 1
n 1
The first step followed by re-indexing, and the second step follows
by Identity 2:
IDENTITY 1
Claim:
Proof:
n n
n 1
r 1
n
n
r
r 1
n!
n!
r!( n r )!
( r 1)!( n r 1)!
( n 1 r ) n! rn!
r!( n 1 r )!
( n 1) n!
r!( n 1 r )!
n 1
IDENTITY 2
Claim: For all n 0 and 1 r n,
n 1
r
r 1
i r
Proof: Proof by induction on n. Suppose r 1. the hypothesis is
certainly true for n = r, in which case both sides of the equation are
equal to 1.
Now suppose n > r and that
n 1
r
r 1
i r
IDENTITY 2 CONTD..
We are required to prove that
i n 2
r 1
i r
n 1
Now, by the induction hypothesis,
n 1
i r
i n 1
i r r
r
n 1 n 1
r 1 r
n 2
r 1
( By
Identity
1)
BACK TO THE CORRECTNESS PROOF
Claim 3. A call to choose(n, r) processes combinations of r things
chosen from 1..n without repeating a combination.
Proof: The proof is by induction on r, and is similar to the above.
Now we can complete the correctness proof: By claim 1, a call to
procedure choose(n, r) generates combinations of r things from 1..n
(since r things at a time are processed from the array A. By Claim
3, it never duplicates a combination.
By Claim 2, it generates exactly the right number of combinations.
Therefore, it generates exactly the combinations of r things chosen
from 1..n.
ANALYSIS
Let T(n, r) be the number of assignments to A made in
choose(n, r).
Claim: For all n 1 and 0 r n,
n
T ( n, r ) r
r
Proof: A call to choose(n, r) makes the following recursive calls:
for i := r to n do
A[ r ]:= i
choose(i 1, r 1)
ANALYSIS CONTD..
The cost are the following
Call
choose(r 1, r 1)
choose(r, r 1)
.
.
choose(n 1, r 1 )
Therefore, summing these costs:
T (n, r )
n 1
Cost
T(r 1, r 1 ) + 1
T(r, r 1 ) + 1
T(n 1, r 1) + 1
T (i, r 1) (n r 1)
i r 1
We will prove by induction on r that
n
T ( n, r ) r
r
ANALYSIS CONTD..
The claim is certainly true for r = 0. now suppose that r > 0
and for all i < n.
i
T (i, r 1) (r 1)
r 1
Then by the induction hypothesis and Identity 2.
T ( n, r )
n 1
T (i, r 1) (n r 1)
i r 1
((
r
1
)
r 1
) ( n r 1)
i r 1
n 1
i
( r 1)
r 1
( n r 1)
i r 1
n 1
n
( r 1)
r
( n r 1)
n
r
r
IDENTITY 2
This last step follows since, for 1 r n,
n
r
n r 1
This can be proved by induction on r. it is certainly true for r =
1, since both sides of the inequality are equal to n in this case.
Now suppose that r > 1
ANALYSIS CNTD..
n
n!
r
r!( n r )!
n( n 1)!
r ( r 1)!((n 1) ( r 1))!
n
( n 1)!
r ( r 1)!((n 1) ( r 1))!
n n 1
r r 1
n
((n 1) ( r 1) 1)
(by hyp.)
r
n r 1
(sin ce
r n)
ANALYSIS
A: Number of
assignment to
array A
C: is the number of
combinations
