Backtracking.pdf-Backtracking ˜ Examples...
Backtracking.pdf-Backtracking ˜ Examples: • Maze problem
Showing 1-7 out of 13
Backtracking.pdf-Backtracking ˜ Exa...
Backtracking.pdf-Backtracking ˜ Examples: • Maze problem
##### Page 1
Backtracking
˜
Examples:
Maze problem
The bicycle lock problem:
ü
Consider a lock with N switches, each of which can
be either 0 or 1.
ü
We know that the combination that opens the lock
should have at least
2
N
1's.
ü
Note: The total number of combinations is 2
N
ü
The solution space can be modeled by a tree
Finish
Start

##### Page 2
ü
Example: N=3
˜
Characteristics
Backtracking technique can be considered as an organized
exhaustive search that often avoids searching all
possibilities.
The solution space can be organized as a tree called:
search tree
Use depth-first search technique
The search tree is pruned using a bounding function.
Assumptions:
ü
X[1..n] contains the solution of the problem
ü
All possible values of X[i]are elements of a set
S
i
ROOT
1
0
000
001
010
011
101
110
111
100
00
01
10
11

##### Page 3
General algorithm:
Procedure backtrack(n)
/* X is the solution vector */
Integer k;
Begin
k =1;
Compute S
k
;
/* compute the possible solution values for k=1 */
While k> 0 do
While S
k
<>
φ
do
X[k] = an element of S
k
;
S
k
= S
k
-{X[k]};
If B(X[1], …, X[i],…, X[k]) = True
Then
Print the solution vector X;
else begin
k = k+1;
Compute S
k
;
End;
End;
End while;
k = k-1;
End while;
End;

##### Page 4
Recursive solution:
Procedure back_recursive(k)
begin
For each X[k] in Sk do
If B(X[1], …, X[i],…, X[k]) = True
then
Print the solution vector X;
else begin
Compute S
k
;
Back_recursive(k+1);
end if;
end for;
end;
˜
Examples:
n-queen
sum of subsets
Hamiltonian cycle
Graph coloring

##### Page 5
˜
n-queen problem:
Objective: place n queen in an n by n chessboard
such that no two queens are not on:
1)
same row
2)
same column
3)
same diagonal
4)
1), 2), and 3) form the
bounding function
Example: N=4
Q
Q
Q
Q
Q
Q
Q
Q
Q
Brute
force method or exhaustive search:
takes
O(
n
2
n
)
Using condition 2)
L
reduce the solution space to n
n
Using condition 1)
L
reduce the solution space to n!
The solution vector is characterized as follows:
ü
X[I] contains the column position of the queen
i in the ith row.
ü
S
k
= {1,2,…, n} S
k
represents the number of
columns for queen k in the kth row.

##### Page 6
Algorithm:
Function bound(k)
Integer i;
Begin
For i=1 to k-1 do
/* for each row up to k-1 */
If X[i] = X[k]
/* Are queens on the same row?*/
or
|X[i]-X[k]| = |i-k|
/* Are queens are on the same
diagonal */
then
return (False);
endif;
endfor;
return(True);
end;

##### Page 7
˜
Sum of subsets
Input: n distinct positive numbers w
i
where 1<=I<=n and
integer M
Output: all combinations whose sum is M
Solution:
ü
Use static binary tree where level I corresponds to
the selection of w
i
.
ü
The solution vector X is defined as follows:
It a bit-map vector where X[i] contains 1 if the
w
i
is included; otherwise it contains 0;
Example:
n=4
(w1,w2,w3,w4) = (11,13,24,7)
M = 31

Browse thousands of Study Materials & Solutions from your Favorite Schools
George Washington Univers...
George_Washington_University
School:
Design_and_Analysis_of_Algorithms
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades