AD8351-Unit IV

AD8351 Design & Analysis of Algorithm Unit-4
UNIT IV BACKTRACKING , ITERATIVE IMPROVEMENT, AND BRANCH & BOUND 10

Backtracking and permutations – N-queens problem – Hamilton circuits –
best-first search.
Iterative Improvement: Stable marriage -- Maximum matching in bipartite
graphs – maximum flow .
Branch and Bound: Knapsack problem -- Traveling salesman problem
BACKTRACKING AND PERMUTATIONS
Both backtracking and branch-and-bound are based on the

construction of a state-space tree whose nodes reflect specific choices
made for a solution’s components.
Both techniques terminate a node as soon as it can be guaranteed that
no solution to the problem can be obtained by considering choices that
correspond to the node’s descendants.
Backtracking
 n-Queens Problem
 Hamiltonian Circuit Problem
Branch – and – Bound
 Knapsack Problem
 Traveling Salesman Problem

Backtracking
 Backtracking is a more intelligent variation of this approach.
 The principal idea is to construct solutions one component at a
time and evaluate such partially constructed candidates as
follows.
 If a partially constructed solution can be developed further

without violating the problem’s constraints, it is done by taking
the first remaining legitimate option for the next component.
 If there is no legitimate option for the next component, no
alternatives for any remaining component need to be
considered. In this case, the algorithm backtracks to replace the
last component of the partially constructed solution with its
next option.
 To implement this kind of processing by constructing a tree of
choices being made, called the state-space tree.
State-Space Tree.
 Its root represents an initial state before the search for a solution
begins.
 The nodes of the first level in the tree represent the choices made
for the first component of a solution.
 The nodes of the second level represent the choices for the
second component, and so on.
 A node in a state-space tree is said to be promising if it
corresponds to a partially constructed solution that may still lead
to a complete solution; otherwise, it is called nonpromising.
 Leaves represent either nonpromising dead ends or complete
solutions found by the algorithm.
 In the majority of cases, a statespace tree for a backtracking
algorithm is constructed in the manner of depthfirst search.
 If the current node is promising, its child is generated by adding
the first remaining legitimate option for the next component of a
solution, and the processing moves to this child.
 If the current node turns out to be non-promising, the algorithm

backtracks to the node’s parent to consider the next possible
option for its last component; if there is no such option, it
backtracks one more level up the tree, and so on.
 Finally, if the algorithm reaches a complete solution to the
problem, it either stops (if just one solution is required) or
continues searching for other possible solutions.
n-Queens Problem
Problem Definition:
The problem is to place n queens on an n × n chessboard so that
no two queens attack each other by being in the same row or in the
same column or on the same diagonal.
 For n = 1, the problem has a trivial solution. Q
 For n = 2, it is easy to see that there is no solution to place 2
queens in 2 × 2 chessboard
Q
 For n = 3, it is easy to see that there is no solution to place 3

queens in 3 × 3 chessboard
 For n = 4 , there is solution to place 4 queens in 4 × 4 chessboard.

The four- queens problem solved by the backtracking technique.
 Since each of the four queens has to be placed in its own row, all
we need to do is to assign a column for each queen on the board
presented in the following Figure
Step 1: Start with the empty board
Figure : Board for the four-queens problem.

Step 2: Place queen 1 in the first possible position of its row, which is
in column 1 of row 1. 1 2 3 4
1 Q
2
3
4
Step 3: Place queen 2, after trying unsuccessfully columns 1 and 2, in
the first acceptable position for it, which is square (2, 3), the square in
row 2 and column 3.
1 2 3 4
1 Q
2 Q
3
4
Step 4: This proves to be a dead end because there is no acceptable

position for queen 3. So, the algorithm backtracks and puts queen 2 in
the next possible position at (2, 4).
1 2 3 4
1 Q
2 Q
3
4
Step 5: Then queen 3 is placed at (3, 2), which proves to be another

dead end.
1 2 3 4
1 Q
2 Q
3 Q
4
Step 6: The algorithm then backtracks all the way to queen 1 and
moves it to (1, 2).
1 2 3 4
1 Q
2
3
4
1 2 3 4
Step 7: Queen 2 then goes to (2, 4). 1 Q

2 Q
3
4
Step 8: Queen 3 to (3, 1).

1 2 3 4
1 Q
2 Q
3 Q
4
Step 9: Queen 4 to (4, 3). This is a solution to the problem.

1 2 3 4
1 Q
2 Q
3 Q
4 Q
The state-space tree of this search is shown in Figure 6.2
Figure : State-space tree of solving the four-queens problem by

backtracking.× denotes an unsuccessful attempt to place a queen in the
indicated column. The numbers above the nodes indicate the order in which
the nodes are generated.
For n =8. There is solution to place in 8 x 8 chessboard.

1 2 3 4 5 6 7 8
1 Q
2 Q
3 Q
4 Q
5 Q
6 Q
7 Q
8 Q
Figure: Solution 8 queens problem in 8 x 8 chessboard
Hamiltonian Circuit Problem

A Hamiltonian circuit (also called a Hamiltonian cycle, Hamilton
cycle, or Hamilton circuit) is a graph cycle( i.e., closed loop) through
a graph that visits each node exactly once. A graph possessing a
Hamiltonian cycle is said to be a Hamiltonian graph.
Example - 1: Find Hamiltonian circuit starts at vertex a.
Solution: Assume that if a Hamiltonian circuit exists, it starts at

vertex a. accordingly, we make vertex a the root of the state-space tree
as in Figure
Figure: State-space tree for finding a Hamiltonian circuit. The numbers

above the nodes of the tree indicate the order in which the nodes are
generated.
 In a Graph G, Hamiltonian cycle begins at some vertex V 1 G,

and the vertices are visited only once in the order V 1, V2, . . . ,
Vn.(Vi are distinct except for V1 and Vn+1 which are equal)
 The first component of our future solution, if it exists, is a first
intermediate vertex of a Hamiltonian circuit to be constructed.
Using the alphabet order to break the three-way tie among the
vertices adjacent to a.
 Then select vertex b. From b, the algorithm proceeds to c, then to

d, then to e, and finally to f, which proves to be a dead end.
 So the algorithm backtracks from f to e, then to d, and then to c,
which provides the first alternative for the algorithm to pursue.
 Going from c to e eventually proves useless, and the algorithm
has to backtrack from e to c and then to b. From there, it goes to
the vertices f , e, c, and d, from which it can legitimately return to
a, yielding the Hamiltonian circuit a, b, f , e, c, d, a.
 If we wanted to find another Hamiltonian circuit, we could
continue this process by backtracking from the leaf of the
solution found.
Iterative Improvement
THE STABLE MARRIAGE PROBLEM.
Stable Marriage Problem
There is a set Y = {m1,…,mn} of n men and a set X = {w1,…,wn} of n women. Each man
has a ranking list of the women, and each woman has a ranking list of the men (with no ties
in these lists).
 A marriage matching M is a set of n pairs (mi, wj).

 A pair (m, w) is said to be a blocking pair for matching M if man m
and woman w are not
matched in M but prefer each other to their mates in M.
 A marriage matching M is called stable if there is no blocking pair
for it; otherwise, it’s
called unstable.
 The stable marriage problem is to find a stable marriage matching

for men’s and women’s
given preferences.
Stable Marriage Algorithm
Step 1:- Start with all the men and women being free
Step 2:- While there are free men, arbitrarily select one of them and do
the following:
o Proposal The selected free man m proposes to w, the next woman on
his preference list
o Response If w is free, she accepts the proposal to be matched with m.
If she is not free, she compares m with her current mate. If she prefers
m to him, she accepts m’sproposal, making her former mate free;
otherwise, she simply rejects m’s proposal,
leaving m free
Step 3:- Return the set of n matched pairs

An accepted proposal is indicated by a boxed cell; a rejected

proposal is shown by an underlined cell.
MAXIMUM MATCHING IN BIPARTITE GRAPHS
Bipartite Graphs
Bipartite graph: a graph whose vertices can be partitioned into two

disjoint sets V and U, notnecessarily of the same size, so that every
edge connects a vertex in V to a vertex in U.
A graph is bipartite if and only if it does not have a cycle of an odd
length
A bipartite graph is 2-colorable: the vertices can be colored in two

colors so that every edge has its vertices colored differently
Matching in a Graph
A matching in a graph is a subset of its edges with the property that no

two edges share a vertex
A maximum (or maximum cardinality) matching is a matching with

the largest number of edges
• always exists not always unique
Augmenting Paths and Augmentation
An augmenting path for a matching M is a path from a free
vertex in V to a free vertex in U whose edges alternate between edges
not in M and edges in M
• The length of an augmenting path is always odd

• Adding to M the odd numbered path edges and deleting from it the
even numbered pathedges increases the matching size by 1
(augmentation)
• One-edge path between two free vertices is special case of
augmenting path
Algorithm
A matching M is maximum if and only if there exists no
augmenting path with respect to M.
Augmenting Path Method (template)
•Start with some initial matching. e.g., the empty set

• Find an augmenting path and augment the current matching along
that path.
• When no augmenting path can be found, terminate and return the last
matching, which is maximum
MAXIMUM FLOW NETWORK

• Finding a feasible flow through a single source ,single sink
(destination) flow network that is maximum.
• Maximizing the flow of data through a transportation network.
• Transportation network can be represented by a connected
weighted graph with n vertices numbered from 1 to n and a set of
edges.
Properties
• It contains exactly one vertex with no entering edges; this vertex
is called the source and assumed to be numbered 1.
• It contains exactly one vertex with no leaving edges; this vertex
is called the sink and assumed to be numbered n.
•
Definition of a Flow
A flow is an assignment of real numbers xij to edges (i,j) of a
given network that satisfy the following:
flow-conservation requirements
The total amount of material entering an intermediate vertex
must be equal to the total amount of the material leaving the
vertex
capacity constraints
Finding a flow-augmenting path
To find a flow-augmenting path for a flow x, consider paths from

source to sink in the underlying undirected graph in which any two
consecutive vertices i,j are either:
• connected by a directed edge (i to j) with some positive unused

capacity
rij = uij – xij known as forward edge ( ĺ )
OR
• connected by a directed edge (j to i) with positive flow xji – known
as backward edge ( ĸ )
Step 1: Start with zero flow
Augmenting path: 1->2->->3 ->6

Step 2: Finding the path
Step 3: Data Transformation
Step 4: Finding the next path

Maximum flow that takes place is 3

i) (5,6) (3,6)
ii) (1,2),(1,4)
iii) (2,5),(2,3),(4,3)
BRANCH-AND-BOUND
General Method
 A branch and bound is a general algorithm for finding optimal
solutions of various optimization problems.
 An optimization problem seeks to minimize or maximize an
objective function, subject to some constraints.
 To deal with optimization problem we compute the best value
of best solution achieved so far.
 A bound on the best solution that can be achieved by expanding
the node is computed and compared to best.
 For a maximization problem the bound is an upper bound
 The largest possible solution that can be achieved by
expanding the node is less or equal to the upper bound.
 If upper bound > best so far, a better solution may be found
by expanding the node and the feasible node is promising .
 For a minimization problem the bound is an lower bound
 The smallest possible solution that can be achieved by
expanding the node is less or equal to the lower bound.
 If lower bound < best so far, a better solution may be found
by expanding the node and the feasible node is promising .
 A Feasible Solution is a point in the problem’s search space that
satisfies all the problem’s constraints.
Example:
 a Hamiltonian circuit in the traveling salesman problem
 a subset of items whose total weight does not exceed the
knapsack’s capacity
 A optimal solution is a feasible solution with the best value of

the objective function.
Example The shortest Hamiltonian circuit , the most valuable subset
items that fit the knapsack .
Compared to backtracking, branch-and-bound requires two
additional items:
 For every node of a state-space tree, a bound on the best value of
the objective function on any solution that can be obtained by
adding further components to the partially constructed solution
represented by the node.
 The value of the best solution seen so far .
Terminate search path at the current node for any one of the
following three reasons:
1.The value of the node’s bound is not better than the value of the best
solution seen so far.
2.The node represents no feasible solutions because the constraints of
the problem are already violated.
3. When no further choices can be made— compare the feasible
solution with that of the best solution is found so far and update the
latter with the former if the new solution is better.
Knapsack Problem
Problem Definition: Given ‘n’ items of known weights w1,w2,. . . ,wn
and values v1,v2,. . . ,vn and a knapsack of capacity W, we have to find
the most valuable subset of the items that fit in the knapsack.
 This is a maximization problem. So, upper bound value is
associated with each node.
 It is convenient to order the items of a given instance in
descending order by their value-to-weight ratios.
 Then the first item gives the best payoff per weight unit and the
last one gives the worst payoff per weight unit, with ties resolved
arbitrarily:
v1/ w1 ≥ v2/ w2 ≥ . . . ≥ vn/ wn
Construction of the state space tree
 Each node on the ith level of this tree, 0 ≤ i ≤ n, represents all
the subsets of n items that include a particular selection made
from the first i ordered items.
 This particular selection is uniquely determined by the path from
the root to the node: a branch going to the left indicates the
inclusion of the next item, and a branch going to the right
indicates its exclusion.
 Record the total weight w and the total value v of this selection in
the node, along with some upper bound ub on the value of any
subset that can be obtained by adding zero or more items to this
selection.
The upper bound ub is computed using the formula
ub = v + (W - w)(vi+1/w i+1)
where, v  Total value of the items already selected
W-w  Product of the remaining capacity of the knapsack
vi+1/w i+1  Best per unit payoff among remaining items, which
is:
Characteristics of knapsack while solved using Branch and Bound
Technique
 The internal nodes of a state space tree do not define a point of
the problem’s search space, because some of the solution’s
components remain undefined.
 Every node of the tree represents a subset of the items given and
uses this fact to update the information about the best subset seen
so far after generating each new node in the tree.
Example: Computing the value to weight ratios and sorting the items
in non increasing order of these efficiency ratios yields.
 At the root of the state-space tree (see Figure 7.4), no items have
been selected as yet. Hence, both the total weight of the items
already selected w and their total value v are equal to $0. The
value of the upper bound computed by formula
ub = 0 + (10 - 0) (10) =100
 Node 1, the left child of the root, represents the subsets that
include item 1. The total weight and value of the items already
included are 4 and $40, respectively; the value of the upper
bound is 40 + (10 - 4) * 6 = $76.
 Node 2 represents the subsets that do not include item 1.
Accordingly, w = 0, v = $0, and ub =0+(10 - 0) * 6 = $60.
 Since node 1 has a larger upper bound than the upper bound of
node 2, it is more promising for this maximization problem, and
we branch from node 1 first.
 Its children—nodes 3 and 4—represent subsets with item 1 and

with and without item 2, respectively.
 Since the total weight w of every subset represented by node 3
exceeds the knapsack’s capacity, node 3 can be terminated
immediately.
 Node 4 has the same values of w and v as its parent; the upper
bound ub is equal to 40 + (10 - 4) * 5 = $70.
Figure: State-space tree of the best-first branch-and-bound algorithm for

the instance of the knapsack problem.
 Selecting node 4 over node 2 for the next branching and get
nodes 5 and 6 by respectively including and excluding item 3.
 Calculate the total weights and values as well as the upper
bounds for these nodes are computed in the same way as for the
preceding nodes.
 Branching from node 5 yields node 7, which represents no
feasible solutions, and node 8, which represents just a single
subset {1, 3} of value $65.
 The remaining live nodes 2 and 6 have smaller upper-bound
values than the value of the solution represented by node 8.
 Hence, both can be terminated making the subset {1, 3} of node
8 the optimal solution to the problem.
Example 2
Traveling Salesman Problem

Problem Definition:
Given a set of cities and the distances between them, determine the
shortest path starting from a given city, passing through all the other
cities exactly once and returning to the first city.
 This is a minimization problem. So lower bound value is
associated with each node.
 Lower bound can be obtained by finding the smallest element in
the intercity distance matrix D and multiplying it by the number
of cities n. But there is a less obvious and more informative lower
bound, which does not require a lot of work to compute.
 A lower bound on the length l of any tour can be computed as
follows:
 For each city i,1≤ i ≤ n, find the sum s i of the distances from
city i to the two nearest cities;
 Compute the sum s of these n numbers
 Divide the result by 2
 If all the distances are integers, round up the result to the
nearest integer: lb = ┌s/2┐
Example: Solve the following travelling salesman problem using the

branch and bound approach
 For the instance of the above graph, the formula yields

lb = ┌[1 + 3) + (3 + 6) + (1 + 2) + (3 + 4) + (2 + 3)]/2┐=14.
 Moreover, for any subset of tours that must include particular
edges of a given graph, we can modify lower bound accordingly.
Figure 7.5: State-space tree of the branch-and-bound algorithm

to find a shortest Hamiltonian circuit in this graph. The list of vertices

in a node specifies a beginning part of the Hamiltonian circuits
represented by the node.
 For example, for all the Hamiltonian circuits of the graph that
must include edge (a, d), the following lower bound by summing
up the lengths of the two shortest edges incident with each of the
vertices, with the required inclusion of edges (a, d) and (d, a):
┌[(1 + 5) + (3 + 6) + (1 + 2) + (3 + 5) + (2 + 3)]/2┐=16.
 Now apply the branch-and-bound algorithm, with the bounding
function given by lb =┌ s/2┐ to find the shortest Hamiltonian
circuit for the given graph .
 To reduce the amount of potential work, we take advantage of

two observations:
 Consider only tours that start at a
 Because our graph is undirected, generate only tours in
which b is visited before c.
 After visiting n - 1 = 4 cities, a tour has no choice but to visit the
remaining unvisited city and return to the starting one.
Example 2:

AD8351-Unit IV

Uploaded by

Copyright:

Available Formats

AD8351-Unit IV

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

AD8351-Unit IV

Uploaded by

Copyright:

Available Formats

AD8351 Design & Analysis of Algorithm Unit-4

UNIT IV BACKTRACKING , ITERATIVE IMPROVEMENT, AND BRANCH & BOUND 10

BACKTRACKING AND PERMUTATIONS

Both backtracking and branch-and-bound are based on the

 If a partially constructed solution can be developed further

 If the current node turns out to be non-promising, the algorithm

 For n = 3, it is easy to see that there is no solution to place 3

 For n = 4 , there is solution to place 4 queens in 4 × 4 chessboard.

Figure : Board for the four-queens problem.

Step 4: This proves to be a dead end because there is no acceptable

Step 5: Then queen 3 is placed at (3, 2), which proves to be another

Step 7: Queen 2 then goes to (2, 4). 1 Q

Step 8: Queen 3 to (3, 1).

Step 9: Queen 4 to (4, 3). This is a solution to the problem.

Figure : State-space tree of solving the four-queens problem by

For n =8. There is solution to place in 8 x 8 chessboard.

Hamiltonian Circuit Problem

Example - 1: Find Hamiltonian circuit starts at vertex a.

Solution: Assume that if a Hamiltonian circuit exists, it starts at

Figure: State-space tree for finding a Hamiltonian circuit. The numbers

 In a Graph G, Hamiltonian cycle begins at some vertex V 1 G,

 Then select vertex b. From b, the algorithm proceeds to c, then to

THE STABLE MARRIAGE PROBLEM.

Stable Marriage Problem

 A marriage matching M is a set of n pairs (mi, wj).

 The stable marriage problem is to find a stable marriage matching

Stable Marriage Algorithm

Step 3:- Return the set of n matched pairs

An accepted proposal is indicated by a boxed cell; a rejected

MAXIMUM MATCHING IN BIPARTITE GRAPHS

Bipartite graph: a graph whose vertices can be partitioned into two

A bipartite graph is 2-colorable: the vertices can be colored in two

A matching in a graph is a subset of its edges with the property that no

A maximum (or maximum cardinality) matching is a matching with

• The length of an augmenting path is always odd

Augmenting Path Method (template)

•Start with some initial matching. e.g., the empty set

MAXIMUM FLOW NETWORK

To find a flow-augmenting path for a flow x, consider paths from

• connected by a directed edge (i to j) with some positive unused

Step 1: Start with zero flow

Augmenting path: 1->2->->3 ->6

Step 3: Data Transformation

Step 4: Finding the next path

Maximum flow that takes place is 3

 A optimal solution is a feasible solution with the best value of

 Its children—nodes 3 and 4—represent subsets with item 1 and

Figure: State-space tree of the best-ﬁrst branch-and-bound algorithm for

Traveling Salesman Problem

Example: Solve the following travelling salesman problem using the

 For the instance of the above graph, the formula yields

Figure 7.5: State-space tree of the branch-and-bound algorithm

to find a shortest Hamiltonian circuit in this graph. The list of vertices

 To reduce the amount of potential work, we take advantage of

You might also like