Please enable JavaScript.
Coggle requires JavaScript to display documents.
Two algorithm design techniques that often make it possible to solve at…
Two algorithm design techniques that often make it possible to solve at least some large instances of difficult combinatorial problems.
Backtracking
The principal ideia of
backtracking
is solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.
In the majority of cases, a
state-space tree
for a
backtracking
algorithm is constructed in the manner of DFS.
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
.
Problems that we can use
backtracking
to solve
n-Queens problem
The problem is to place
n
queens on an
n
x
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.
Hamiltonian Circuit problem
The problem consist of finding a
hamiltonian circuit
in a given graph.
Subset-Sum problem
The problem is to find a subset of a given set
A = {a1......an}
of
n
positive integers whose sum is equal to a given positive integer
d
.
From a more general perspective, an output of a
backtracking
algorithm can be thought of as an
n
-tuple (
x1, x2,...,xn
) where each coordinate
xi
is an element of some finite linearly ordered set
Si
.
Branch-and-Bound
Branch-and-bound
is generally used for solving combinatorial optimization problems. These problems are typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. The
Branch-and-bound
Algorithm technique solves these problems relatively quickly.
Problems that we can use
branch-and-bound
to solve
Assignment problem
The problem consist of assigning
n
people to
n
jobs so that the total cost of the assignment is as small as possible.
Knapsack problem
Given
n
items of known weights
wi
and values
vi
,
i
= 1,2,...,
n
, and a knapsack of capacity
W
, find the most valuable subset of the items that fit in the knapsack, that is the
knapsack problem
.
Traveling Salesman problem
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? That is the
traveling salesman problem
.
Typicall expands a
state-space tree
based on the BFS.
Compared to
backtracking
, two additional items are necessary in
branch-and-bound
:
For each node of the
state-space tree
, a bound
on the best value of the objective function
The value of the best solution so far
Both are based on the construction of a
state-space tree
whose nodes reflect specific choices made for a solution's components.