Tuesday, June 20, 2017

What is the Idea of Developing a DP Algorithm?

The Idea of Developing a DP Algorithm :

Step 1: Structure : Characterize the structure of an optimal solution.

-Decompose the problem into smaller problems, and find a relation between the structure of the optimal solution of the original problem and the solutions of the smaller pronlms.

Step 2 : Principle of Optimality : Recursively define the value of an optimal solution.

-Express the solution of the original problem in terms of optimal solutions for smaller problems.

Step 3 : Bottom-up computation: Compute the value of an optimal solution in a bottom-up fashion by using a table structure.

Step 4 : construction of optimal Solution : Construct an optimal solution from computed information.Steps 3 and 4 may often be combined. 

What is 0-1 Knapsack Problem?

0-1 Knapsack Problem : Given two n-tuples of positive numbers (<V1,V2,.....,Vn) and (<w1,w2,w3,.....,wn and W>0, We wish to determine the subset T∈{1,2,3,....,n} (of files to store)) that maximizes ∑ieT Vi subject to ∑ieT wi≤W

What is the 8-Queens Problem

The 8-Queens Problem :
The Bounding function for 8-queens problem is
No two queens placed on the same column  → xi's are distinct
No two queens placed on the same diagonal → how to test?

The same value of "row-column" or "row+column" indicates that two queens placed on the same diagonal.

Supposing two queens on (i,j) and (k,1)
i-j=k-1(i.e,j-1=i-k) or i+j = k+1(i.e, j-1 = k-i)
So, two queens placed on the same diagonal iff
[j-i] = [i-k] 

Algorithm NQueen(k,n)

// Using backtracking, this procedure prints all
//possible placements of n queens on an nXn
//chessboard so that they are nontracking.
x[k] = i;
if(k=n)then write(x[1:n]);
else NQueens(k+1, n);

What is Implicit Constraints?

Implicit Constraints : The implicit constraints are rules that determine which of the tuples in the solution space of I satisfy the criterion function.Thus implicit constraints describe the way in which the xi must relate to each other.

What is Explicit Constraints?

Explicit Constraints : Explicit constraints are rules that restrict each x<sub>i</sub> to take on values only from a given set.

Common Examples of Explicit constraints are :
Xi≥0 or Si = {all nonnegative real numbers} Xi = 0 or Si = {0,1} 1i≤xi≤ui or Si = {a:1i≥a≥ui}
All tuples satisfying the explicit constraints define a possible solution space for 1(I = Problem instance)

What is the Formulation of the backtracking?

The Formulation of the backtracking : T(X1,X2,...,Xi): set of all possible values for xi+1 such that (X1,X2,...,Xi,Xi+1) is also a Bi+1>(X1,X2,...,Xi,Xi+1): bounding function If Bi+1>(X1,X2,...,Xi,Xi+1) is false, then the path cannot be extended to reach an answer node.