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 (<V₁,V₂,.....,V_n) and (<w₁,w₂,w₃,.....,w_n and W>0, We wish to determine the subset T∈{1,2,3,....,n} (of files to store)) that maximizes ∑_ieT V_i subject to ∑_ieT w_i≤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  → x_i'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.
{
for(i=1;i<=n;i++)
{
if(Place(k,i))then
{
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 x_i must relate to each other.

What is Explicit Constraints?

Explicit Constraints : Explicit constraints are rules that restrict each x_i to take on values only from a given set.

Common Examples of Explicit constraints are :
X_i≥0 or S_i = {all nonnegative real numbers} X_i = 0 or S_i = {0,1} 1_i≤x_i≤u_i or S_i = {a:1_i≥a≥u_i}
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(X₁,X₂,...,X_i): set of all possible values for x_i+1 such that (X₁,X₂,...,X_i,X_i+1) is also a B_i+1>(X₁,X₂,...,X_i,X_i+1): bounding function If B_i+1>(X₁,X₂,...,X_i,X_i+1) is false, then the path cannot be extended to reach an answer node.