Hamiltonian Circuit
Subset-Sum Problem
Copyright © 2007 Pearson Addison-Wesley. All rights reserved.
Backtracking
Backtracking is a more intelligent variation of exhaustive
search 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.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 12 12-2
Hamiltonian Circuit Problem
A Hamiltonian circuit is a circuit that visits every vertex
once with no repeats.
The main applications are computer graphics, electronic
circuit design, mapping genomes, and operations research.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 12 12-3
Example: Hamiltonian Circuit Problem
a b
c f
d e
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 12 12-4
Hamiltonian Circuit Problem
Using the alphabet order to break the three-way tie among the
vertices adjacent to a, we 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.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 12 12-5
Subset-Sum Problem
subset-sum problem: find a subset of a given set A = {a1, . . . , an}
of n positive integers whose sum is equal to a given positive
integer d.
The root of the tree represents the starting point, with no decisions
about the given elements made as yet. Its left and right children
represent, respectively, inclusion and exclusion of a1 in a set being
sought.
Similarly, going to the left from a node of the first level
corresponds to inclusion of a2 while going to the right corresponds
to its exclusion, and so on. Thus, a path from the root to a node on
the ith level of the tree indicates which of the first i numbers have
been included in the subsets represented by that node.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 12 12-6
Subset-Sum Problem
A={3, 5, 6, 7} d=15
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 12 12-7
Backtracking- Remarks
1) it is typically applied to difficult combinatorial problems for
which no efficient algorithms for finding exact solutions possibly
exist.
2) The exhaustive search approach is doomed to be extremely
slow for all instances of a problem, backtracking at least holds a
hope for solving some instances of nontrivial sizes in an
acceptable amount of time.
3) Even if backtracking does not eliminate any elements of a
problem’s state space and ends up generating all its elements, it
provides a specific technique for doing so, which can be of value
in its own right.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 12 12-8