ADA Module 5 - Full
ADA Module 5 - Full
of Algorithms
LIMITATIONS OF ALGORITHMIC POWER: Decision
Trees, P, NP, and NP-Complete Problems.
Indeed, a binary tree of height h with the largest number of leaves has all its
leaves on the last level. Hence, the largest number of leaves in such a tree is 2h. In
other words, 2h ≥ l, which immediately implies
if (key = A[j])
{
write(j);
Success();
}
NP
write(0);
Failure();
} P
Solve S = {1,2,3,4,5} d = 7
Backtracking and Branch and Bound
Concept of Backtracking
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.
This idea is implemented by constructing a tree of choices being
made, called the state-space tree.
Backtracking and Branch and Bound
Concept of Backtracking
Tree’s 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 non-promising (dead end).
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.
Backtracking and Branch and Bound
Concept of Backtracking
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.
Subset-sum problem
Finding a subset of a given set S = {s1,s2...,sn} of n positive integers
whose sum is equal to a given positive integer d.
For example, for S = {1, 2, 5, 6, 8} and d = 9, there are two
solutions: {1, 2, 6} and {1, 8}.
It is convenient to sort the set’s elements in increasing order. So, we
will assume that s1<=s2<=...<=sn .
Backtracking and Branch and Bound
Developing state-space tree for subset-sum problem
The state-space tree can be constructed as a binary tree for the
problem S = {3, 5, 6, 7} and d = 15.
The root of the tree represents the starting point, with no decisions
made about the given elements (empty subset).
Its left and right children represent, respectively, inclusion (with 3 in
the example) and exclusion of S1(without 3 in the example) in a
subset being sought.
Similarly, going to the left from a node of the first level corresponds
to inclusion of S2 (with 5 in the example) while going to the right
corresponds to exclusion of S2 (without 5 in the example) 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.
Backtracking and Branch and Bound
Developing state-space tree for subset-sum problem
Record the value of subset s, the sum of these numbers, in the node.
If s is equal to d, we have a solution to the problem. We can either
report this result and stop or, if all the solutions need to be found,
continue by backtracking to the node’s parent.
If s is not equal to d, we can terminate the node as non-promising if
either of the following two inequalities holds;
Backtracking and Branch and Bound
Algorithm SumOfSubset(s, k, r)
// Input: d & W[1…n] which holds the elements in increasing order
//Output: subsets whose sum = d.
{
x[k] = l;
if (s + w[k] == d) then
write (x[l : k]); // Subset found
else if (s + w[k] + w[k + 1] <= d) then //else add next element
SumOfSubset(s + w[k], k + l, r - w[k]);
if ((s + r - w[k] >= d) and (s + w[k + 1] <= d)) then //handle np nodes
{ // generate right child and evaluate that node
x[k] = 0;
s = initialSum = 0
SumOfSubset(s, k + l, r - w[k]);
k = index of the element = 1
} r = initial value is total of all elements = d
k = initial value = 1
n = number of queens
1 2 3 4
x 3 1 4 2
Backtracking and Branch and Bound
Branch and Bound
Compared to backtracking, branch-and-bound requires two additional
items:
1. 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.
2. The value of the best solution seen so far.
Terminate a node when any one of the following condition met.
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. The subset of feasible solutions represented by the node consists of a
single point and hence no further choices can be made.
Branch and Bound
ub = 0 + (10 – 0)(42/7)
= 60
ub = 40 + (10 – 4)(25/5) =
70
Adding item 4,
exceeds knapsack No more items, this is
capacity. optimal solution {1,3} = 65