|
|
|
Backtracking.pdf
Backtracking.pdf
Showing 1-7 out of 13
Backtracking.pdf-Backtracking ˜ Examples: • Maze p...
Backtracking.pdf-Backtracking ˜ Examples: • Maze problem
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
Ace your assessments! Get Better Grades
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
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
