Backtracking
Backtracking is a methodical way of trying out various sequences of decisions, until
\we find one thst “works”. Backtracking algorithms are based on a depth-first recursive
search,
‘There are two versions of backtracking algorithms:
+ Solution needs only to be satisfy problem's constraints
For example Sum of subsets,
+ Solution needs also to be optimal
For example knapsack problem,
22.1 THE BACKTRACKING METHOD
+ A given problem has a set of constraints and possibly an objective function,
‘The solution optimizes an objective function, and is satifies,
We can represent the solution space for the problem using a state space tree:
‘The root of the tree represent 0 choice
—Nodes at depth | represent first choice.
— Nodes st depth 2 represent the second choice
In this tree a path from a root to a leaf represents a candidate solution
22.1.1 Sum of Subsets Problem
Given n positive imegers Wy, W, Ws, .., W, and a positive integer S. Find al subsets of|
Wis Wyo » Wy that SM 10 S,
Examples: Given a setS'~ (2, 4, 6} and P~ 6, Find subset sum using backtracking
approach.
Solution: =3, = 2,9) = 4,9, = 6 and = 6,
‘The state space tee,
rae
a
oe of
~~@ © ©
x oS
be subae mem~ (24) ad (6)
ample 2 Foen=3, 35) 2-4, j= 5 md 976, um of et
Selo: The st pce ee 1.2 maueens Problem
Place msusens on ann *n chessboard sa hat no two of them are on the sme om
come, or ditgonak.
4-Queens Problem
‘Thed-queens puzl isthe problem of poting four chess queens on and = 4chessboars
such that nom of hem is able fo captre any other using the senda cess queen's
“The gusens mit be place in ach away thet ao two queens wold Be able 16
stack each oder. Ths, sliaion requires thar no to queens share the same 78.
‘column, or diagonal 4a. paguna sapou yu ened wuss ae ‘8-Queens Problem
‘The eight queen puazle is tho problem of puting sight chers queens on an $ « S
chessboard such hat aon of them i able o capture anyother using the standard chess
ueen's moves.
“The queens must be placed in such # way tat no fvo queens would be able to
sutach each other, Thos, 2 slution requits that no vo queens shate the same sow,
colums er diagonal
Solution othe 8-queens problems:
Solution: (9
123 es es
(ne slulon 4.6, 8.2.7.1.3.5>
Solution: (9)
' @
Unique seanen2
2212 Graph Coloring
‘ven gap anda eyes lor eres ig 0c than m ol 30 at
so aacen! ere ae he ue eoe
That te ggheloae Ihe pedi of clring exch vere na gh sh
that no eset vere svete alae “Adjre™ ar an come
ee
Example:
Minima ee cols ae ei clr the gr
mpl Cee be got an ph lec tere,
{wo adjacent vertices have same color. The number of color should be minimum,
AyRed
Green F) ate
rei(e Bon
BYpne
‘The minimum requited color = 3 (Red, Green, Blue) Branch and Bound
23.1 BRANCH AND BOUND
Branch end bovnd algorithms are eccive for glving various search and global
optimization problems. Branch and bound algorithms work bythe divide and conquer
ptnsile ths ssarch space i subdivide into sealer subregions (This subdivision is
fefered to as branching). and bounds are found on ll te soluions conned in each
subregion under consideration. The tength of the branch and tound approach comes
‘when bounds on a large suegion show tht it contins only inteviorspltions nd so
he ene subeeion ean be sitesded without farther exarsiation
“The banchvand-bound desig strategy i very similar to backtracking in that a
‘iste space tve is used fo solve a problem. The dilference are thatthe brane-ané
bound methoe:
1. doesnot init vs to any particular way of raves the tee, and
2. used only for optization problems
53. ateach sage, we caculace te bound fora parcula node and check whethoe
‘this bound wl be able to give the solution a nt.
Key Points
‘+ Branch and bound is a general search method,
1 Stating by eonsieringhe oot problem (the orginal problem withthe coapete
[easibleregon)tbelower-bouning and upper- bounding proceduresare applied
{0 the root problem,
‘= lthebounds match then an optimal solutions been Foundland the procedire
23.1.1. Knapsack Problem
“The 01 napsac problem restricts the aur of, cops ofeach kind af ism
(o-210 ot one mathematically the O~ 1 knapsack problem can be felted a8
soasiine= 5 2%,
and Dw ew He wy
a7
Rey points:
‘We wish the maximize the profit in the knapsace
+ Maximization
+ Use of upper bound (UB),
‘The node structure s follows: Node is divided into throe pats
The first part indicates the total weight of the ilem.
+The second purt indicates the value ofthe eurent item.
‘+The third par indicates the upper bound forthe node.
‘Noo
UB = V+ (WW) PasMad