UNIT – IV

Unit-IV/Lecture-01

Backtracking concept

Backtracking concept and its examples:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c (backtracks) as soon as it determines that c cannot possibly be completed to a valid solution.

The name backtrack was first coined by D. H. Lehmer in the 1950's. Early workers who studied the process were R. J. Walker who gave an algorithmic account of it in 1960 and Golomb and Baumert who presented a very general description of backtracking coupled with a variety of applications. Many problems which deal with searching for a set of solutions or which ask for an optimal solution satisfying some constraints can be solved using the backtracking formulation.

The example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned, since it cannot possibly be completed to a valid solution.

Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

In order to apply the backtrack method, the desired solution must be expressible as an n-tuple (x1, ... , Xn) where the x1 are chosen from some finite set Si. Often the problem to be solved calls for finding one vector which maximizes (or minimizes or satisfies) a criterion function P(x1, ... ,

Xn). Sometimes it seeks all such vectors which satisfy P. For example, sorting the integers in A(1:n) is a problem whose solution is expressible by an n-tuple where xi  is the index in A of the i^th smallest element. The criterion function P is the inequality A(xi)<= A(xi+ 1) for 1<=i<n. The set Si is finite and includes the integers 1 through n. Though sorting is not usually one of the problems solved by backtracking, it is one example of a familiar problem whose solution can be formulated as an n tuple.

Suppose m_i is the size of set Si. Then there are m = m1 m2 · · · m_n n-tuples which are possible candidates for satisfying the function P. The brute force approach would be to form all of these n-tuples and evaluate each one with P, saving those which yield the optimum. The backtrack

algorithm has as its virtue the ability to yield the same answer with far fewer than m trials. Its basic idea is to build up the same vector one component at a time and to use modified criterion functions Pi(x1. ... , xi) (sometimes called bounding functions) to test whether the vector being formed has any chance of success. The major advantage of this method is this: if it is realized that the partial vector (x 1, x2, ... , xi) can in no way lead to an optimal solution, then mi+ 1……… m_n possible test vectors may be ignored entirely.

Many of the problems we shall solve using backtracking require that all the solutions satisfy a complex set of constraints.

For any problem these constraints may be divided into two categories:

1. Explicit Constraints

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

Explicit constraints depend on the particular instance I of a problem being solved. All tuples that satisfy the explicit constraints define a possible solution space for I.

Example-

(1)    X_i>=0 or S_i ={all nonnegative real numbers}

(2)    x_i= 0 or 1 or S_i={0,1}

2. Implicit Constraints

Ø  Implicit Constraints:-are rules that determine which of the tuples in the solution space of I satisfy the criterion function.

Example that can be solved by backtracking are:-

·         8-queens problem

·         4-queens problem or in generalized way  n-queens problem

·         Sum of subset problem

Recursive Backtracking Algorithm:

1. Algorithm Backtrack (k)
2. //This schema describes the backtracking process using recursion.
3. //On entering the first k-1 values x[1],x[2],….x[k-1]of the solution
4. //vector x[n] have been assigned.
5. X[] and n are global.
6. {
7. for each x[k] belongs T(x[1],……………..x[k-1]) do
8.     {
9.                    if(B_k(x[1],x[2],….x[k])  != 0) then
10.                                 {
11.                                                 if(x[1],x[2],….x[k]  is a path to an answer node)
12.                                                                 then write ( x[1: k]);
13.                                                 if( k<n) then Backtrack( k+1)
14.                                 }
15.       }
16. }

Unit-IV/Lecture-02

8 queen’s problem

8 queen’s problem:

The 8-queens problem is a special form of n- queens  problem. Here we can think that there are 8 queens to be placed on a n x n chessboard . That means we have a chessboard having n row’s and n columns, and n queens are to be placed on this board such that no two queens are in same row or in same columns or in same diagonal. Then we call that no two queens “attack” each other.

Solution:

v  The solution vector X (X1…Xn) represents a solution in which Xi is the column of the  i^th row where I ^th queen is placed.

v  First, we have to check no two queens are in same row.

v  Second, we have to check no two queens are in same column.

v  The function, which is used to check these two conditions, is [I, X (j)], which gives position of the I ^th queen, where I represents the row and X (j) represents the column position.

v  Third, we have to check no two queens are in it diagonal.

v  Consider two dimensional array A[1:n,1:n] in which we  observe that every element on the same diagonal that runs from upper left to lower right has the same value.

v  Also, every element on the same diagonal that runs from lower right to upper left has the same value.

v  Suppose two queens are in same position (i,j) and (k,l) then two queens lie on the same diagonal , if and only if |j-l|=|I-k|.

STEPS TO GENERATE THE SOLUTION:

v  Initialize x array to zero and start by placing the first queen in k=1 in the first row.

v  To find the column position start from value 1 to n, where ‘n’ is the no. Of columns or no. Of queens.

v  If k=1 then x (k)=1.so (k,x(k)) will give the position of the k ^th queen. Here we have to check whether there is any queen in the same column or diagonal.

v  For this considers the previous position, which had already, been found out. Check whether

      X (I)=X(k) for column |X(i)-X(k)|=(I-k) for the same diagonal.

v  If any one of the conditions is true then return false indicating that k th queen can’t be placed in position X (k).

v  For not possible condition increment X (k) value by one and precede   d until the position is found.

v  If the position X (k) n and k=n then the solution is generated completely.

v  If k<n, then increment the ‘k’ value and find position of the next queen.

v  If the position X (k)>n then k ^th queen cannot be placed as the size of the matrix is ‘N*N’.

v  So decrement the ‘k’ value by one i.e. we have to back track and after the position of the previous queen.

Algorithm:

Algorithm place (k,I)

//return true if a queen can be placed in k ^th row and I ^th column. otherwise it returns //

//false .X[] is a global array whose first k-1 values have been set. Abs® returns the //absolute value of r.

{

  For j=1 to k-1 do

     If ((X [j]=I)              //two in same column.

     Or (abs (X [j]-I)=Abs (j-k)))

Then return false;

Return true;

}

Algorithm Nqueen (k,n)

//using backtracking it prints all possible positions of n queens in ‘n*n’ chessboard. So

 //that they are non-tracking.

{

     For I=1 to n do

         {

            If place (k,I) then

              {

                 X [k]=I;

                  If (k=n) then write (X [1:n]);

                   Else nquenns(k+1,n)    ;

           }

      }

}

Example: 4 queens.

Two possible solutions are

Unit-IV/Lecture-03

Hamiltonian cycle

Let G=(V,E) be a connected graph with ‘n’ vertices. A HAMILTONIAN CYCLE is a round trip path along ‘n’ edges of G that visits every vertex once and returns to its starting position. If the Hamiltonian cycle begins at some vertex V1 belongs to G and the vertex are visited in the order of V1,V2…….Vn+1,then the edges are in E,1<=I<=n and the Vi are distinct except V1 and Vn+1 which are equal.

v  Consider an example graph G1.

4

1

2

3

 

6

8

7

5

 

The graph G1 has Hamiltonian cycles:

->1,3,4,5,6,7,8,2,1 and

->1,2,8,7,6,5,4,3,1.

The backtracking algorithm helps to find Hamiltonian cycle for any type of graph.

Procedure:

1.       Define a solution vector X(Xi……..Xn) where Xi represents the I th  visited vertex of the proposed cycle.

2.       Create a cost adjacency matrix for the given graph.

3.       The solution array initialized to all zeros except X(1)=1,b’coz the cycle should start at vertex ‘1’.

4.       Now we have to find the second vertex to be visited in the cycle.

5.       The vertex from 1 to n are included in the cycle one by one by checking 2 conditions,

             1.There should be a path from previous visited vertex to current vertex.

            2.The current vertex must be distinct and should not have been visited earlier.

6.   When these two conditions are satisfied the current vertex is included in the cycle, else the  next vertex is tried.

7.   When the nth vertex is visited we have to check, is there any path from nth vertex to first  8vertex. if no path, the go back one step and after the previous visited node.

8.   Repeat the above steps to generate possible Hamiltonian cycle.

Algorithm:(Finding all Hamiltonian cycle)

Algorithm Hamiltonian (k)

{

 Loop

             Next value (k)

If (x (k)=0) then return;

{

  If k=n then

      Print (x)

Else

Hamiltonian (k+1);

End if

}

Repeat

}

Algorithm Nextvalue (k)

{

 Repeat

{

  X [k]=(X [k]+1) mod (n+1); //next vertex

  If (X [k]=0) then return;

  If (G [X [k-1], X [k]] 0) then

{

  For j=1 to k-1 do if (X [j]=X [k]) then break;

  // Check for distinction.

  If (j=k) then          //if true then the vertex is distinct.

    If ((k<n) or ((k=n) and G [X [n], X [1]]  0)) then return;

}

} Until (false);

Unit-IV/Lecture-04

Graph Coloring problem

Graph coloring:

Ø  Let ‘G’ be a graph and ‘m’ be a given positive integer. If the nodes of ‘G’ can be colored in such a way that no two adjacent nodes have the same color. Yet only ‘M’ colors are used. So it’s called M-color ability decision problem.

Ø  The graph G can be colored using the smallest integer ‘m’. This integer is referred to as chromatic number of the graph.

Ø  A graph is said to be planar iff it can be drawn on plane in such a way that no two edges cross each other.

Ø  Suppose we are given a map then, we have to convert it into planar. Consider each and every region as a node. If two regions are adjacent then the corresponding nodes are joined by an edge.

Consider a map with five regions and its graph.

1

 

              4          5

                   2

              3

1 is adjacent to 2, 3, 4.

2 is adjacent to 1, 3, 4, 5

3 is adjacent to  1, 2, 4

4 is adjacent to   1, 2, 3, 5

5

4 Algorithm mColoring(k) // the graph is represented by its Boolean adjacency matrix G[1:n,1:n]  .All assignments //of 1,2,……….,m to the vertices of the graph such that adjacenct vertices are assignrd //distinct integers are printed.’k’ is the index of the next vertex to color.   {   repeat {     // generate all legal assignment for X[k].   Nextvalue(k);    // Assign to X[k] a legal color.          If (X[k]=0) then return;           // No new color possible.         If (k=n) then                  // Almost ‘m’ colors have been used to color the ‘n’ vertices                   Write(x[1:n]);           Else mcoloring(k+1); }until(false); }         Algorithm Nextvalue(k) // X[1],……X[k-1] have been assigned integer values in the range[1,m] such that //adjacent values have distinct integers.A value for X[k] is determined in the //range[0,m].X[k] is assigned the next highest numberes color while maintaining //distinctness form the adjacent vertices of vertex K.If no such color exists,then X[k] is 0.   {    repeat     {               X[k] = (X[k]+1)mod(m+1);    // next highest color.            If(X[k]=0) then return;             //All colors have been used.               For j=1 to n do              {                  // Check if this color is distinct from adjacent color.              If((G[k,j] 0)and(X[k] = X[j]))                  // If (k,j) is an edge and if adjacent vertices have the same color.              Then break;              }            if(j=n+1) then return;     //new color found.       } until(false);    //otherwise try to find another color. }   à The time spent by Nextvalue to determine the children is (mn) àTotal time is = (mn n).     Knapsack Problem using Backtracking:   Ø  The problem is similar to the zero-one (0/1) knapsack optimization problem is dynamic programming algorithm.   Ø  We are given ‘n’ positive weights Wi and’n’ positive profits Pi,and a positive number ‘m’ that is the knapsack capacity,thgis problem calls for chossing a subset of the weights such that,       m  and  is Maximized.     Xi àConstitute Zero-one valued Vector.   Ø  The Solution space is the same as that for the sum of subset’s problem.   Ø  Bounding functions are needed to help kill some live nodes without expanding them. A good bounding function for this problem is obtained by using an upper bound on the value of the best feasible solution obtainable by expanding the given live node.   Ø  The profits and weights are assigned in descending order depend upon the ratio.     (i.e) Pi/Wi  P(I+1) / W(I+1)   Solution :   Ø  After assigning the profit and weights ,we have to take the first object weights and check if the first weight is less than or equal to the capacity, if so then we include that object (i.e) the unit is 1.(i.e) Kà 1.   Ø  Then We are going to the next object,if the object weight is exceeded that object doesnat fit.So unit of that object is ‘0’.(i.e) K=0.   Ø  Then We are going to the bounding function ,this function determines an upper bound on the best solution btainal\ble at level K+1.   Ø  Repeat the process until we reach the optimal solution.       Algorithm:   Algorithm Bknap(k,cp,cw) // ‘m’ is the size of the knapsack;  ‘n’ à no.of weights & profits. W[]&P[] are the //weights & weights. P[I]/W[I]  P[I+1]/W[I+1]. //fwàFinal weights of knapsack. //fpà final max.profit. //x[k] = 0 if W[k] is not the knapsack,else X[k]=1. {        // Generate left child.         If((W+W[k] m) then         {                Y[k] =1;                 If(k<n) then Bnap(k+1,cp+P[k],Cw +W[k])                    If((Cp + p[w] > fp) and (k=n)) then                        {                         fp = cp + P[k];                         fw = Cw+W[k];                        for j=1 to k do X[j] = Y[j];                    }     }     if(Bound(cp,cw,k) fp) then   {         y[k] = 0;       if(k<n) then Bnap (K+1,cp,cw);     if((cp>fp) and (k=n)) then        {             fp = cp;              fw = cw;                for j=1 to k do X[j] = Y[j];          } } }                       Algorithm for Bounding function:   Algorithm Bound(cp,cw,k) // cpà current profit total. //cwà current weight total. //kàthe index of the last removed item. //màthe knapsack size.   {      b=cp;      c=cw;      for I =- k+1 to n do   {           c= c+w[I];         if (c<m) then b=b+p[I];              else return b+ (1-(c-m)/W[I]) * P[I]; } return b; }     Example:    M= 6  Wi = 2,3,4      4   2   2   N= 3   Pi = 1,2,5             Pi/Wi (i.e)       5  2  1   Xi = 1  0   1 The maximum weight is 6 The Maximum profit is (1*5) + (0*2) + (1*1)                               à 5+1                               à 6.     Fp = (-1)   1 3 & 0+4  6           cw = 4,cp = 5,y(1) =1              k = k+2     2 3  but 7>6            so y(2) = 0   So bound(5,4,2,6)      B=5   C=4   I=3 to 3 C=6 6 6 So return 5+(1-(6-6))/(2*1)                  5.5 is not less than fp.             So, k=k+1 (i.e) 3.              3=3 & 4+2 6              cw= 6,cp = 6, y(3)=1.            K=4.     If 4> 3 then    Fp =6,fw=6,k=3 ,x(1) 1  0  1   The solution Xi à 1  0  1     Profit à 6      Weight à6.

3

2

1

5 is adjacent to   2, 4

Steps to color the Graph:

v  First create the adjacency matrix graph(1:m,1:n) for a graph, if there is an edge between i,j then C(i,j) = 1 otherwise C(i,j) =0.

v  The Colors will be represented by the integers 1,2,…..m and the solutions will be stored in the array X(1),X(2),………..,X(n) ,X(index) is the color, index is the node.

v  He formula is used to set the color is,

            X(k) = (X(k)+1) % (m+1)

v  First one chromatic number is assigned ,after assigning a number for ‘k’ node, we have to check whether the adjacent nodes has got the same values if so then we have to assign the next value.

v  Repeat the procedure until all possible combinations of colors are found.

v  The function which is used to check the adjacent nodes and same color is,

If(( Graph (k,j) == 1) and X(k) = X(j))

Example:

1

3

2

4

N= 4

            M= 3

Adjacency Matrix:

            0   1   0   1

            1   0   1   0

            0   1   0   1

            1   0   1   0

à Problem is to color the given graph of 4 nodes using 3 colors.

àNode-1 can take the given graph of 4 nodes using 3 colors.

à The state space tree will give all possible colors in that ,the numbers which are inside the circles are nodes ,and the branch with a number is the colors of the nodes.

State Space Tree:

Unit-IV/Lecture-05

Introduction to branch & bound method

 The design technique known as branch and bound is very similar to backtracking in that it searches a tree model of the solution space and is applicable to a wide variety of discrete combinatorial problems.

Each node in the combinatorial tree generated in the last Unit defines a problem state. All paths from the root to other nodes define the state space of the problem. Solution states are those problem states 's' for which the path from the root to 's' defines a tuple in the solution space. The leaf nodes in the combinatorial tree are the solution states.

Answer states are those solution states’s’ for which the path from the root to 's' defines a tuple that is a member of the set of solutions (i.e., it satisfies the implicit constraints) of the problem.

                                                      The tree organization of the solution space is referred to as the state space tree. A node which has been generated and all of whose children have not yet been generated is called a live node. The live node whose children are currently being generated is called the E-node (node being expanded). A dead node is a generated node, which is not to be expanded further or all of whose children have been generated.

 Bounding functions are used to kill live nodes without generating all their children. Depth first node generation with bounding function is called backtracking. State generation methods in which the E-node remains the E-node until it is dead lead to branch-and-bound method. The term branch-and-bound refers to all state space search methods in which all children of the E-node are generated before any other live node can become the E-node.

      In branch-and-bound terminology breadth first search(BFS)- like state space search will be called FIFO (First In First Output) search as the list of live nodes is a first -in-first -out list(or queue).

 A D-search (depth search) state space search will be called LIFO (Last In First Out) search, as the list of live nodes is a list-in-first-out list (or stack). Bounding functions are used to help avoid the generation of sub trees that do not contain an answer node.

      The branch-and-bound algorithms search a tree model of the solution space to get the solution. However, this type of algorithms is oriented more toward optimization. An algorithm of this type specifies a real -valued cost function for each of the nodes that appear in the search tree.

      Usually, the goal here is to find a configuration for which the cost function is minimized. The branch-and-bound algorithms are rarely simple. They tend to be quite complicated in many cases.

Example -1[4-queens] How a FIFO branch-and-bound algorithm would search the state space tree for the 4-queens problem.

      Initially, there is only one live node, node1. This represents the case in which no queen has been placed on the chessboard. This node becomes the E-node.  It is expanded and its children, nodes2, 18, 34 and 50 are generated.

These nodes represent a chessboard with queen1 in row 1and columns 1, 2, 3, and 4 respectively.

The only live nodes 2, 18, 34, and 50.If the nodes are generated in this order, then the next E-node are node 2.

     It is expanded and the nodes 3, 8, and 13 are generated. Node 3 is immediately killed using the bounding function. Nodes 8 and 13 are added to the queue of live nodes.

    Node 18 becomes the next E-node. Nodes 19, 24, and 29 are generated. Nodes 19 and 24 are killed as a result of the bounding functions. Node 29 is added to the queue of live nodes.

 Now the E-node is node 34. Nodes that are killed as a result of the bounding functions are a "B" under them.

      Numbers inside the nodes correspond to the numbers in Figure. Numbers outside the nodes give the order in which the nodes are generated by FIFO branch-and-bound. At the time the answer node, node 31, is reached, the only live nodes remaining are nodes 38 and 54.

Unit-IV/Lecture-06

Travelling salesman problem of branch & bound

TRAVELLING SALESMAN PROBLEM:

A branch-and-bound algorithm consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidate s are discarded, by using upper and lower estimated bounds of the quantity being optimized. The Branch and Bound strategy divides a problem to be solved into a number of sub-problems. It is a system for solving a sequence of subproblems each of which may have multiple possible solutions and where the solution chosen for one sub-problem may affect the possible solutions of later sub-problems. Suppose it is required to minimize an objective function. Suppose that we have a method for getting a lower bound on the cost of any solution among those in the set of solutions represented by some subset. If the best solution found so far costs less than the lower bound for this subset, we need not explore this subset at all.

STEPS INVOLVED IN THIS PROCEDURE ARE AS FOLLOWS:

Generate cost matrix C [for the given graph g]

STEP 1:            [ROW REDUCTION] For all rows do step 2

STEP:               Find least cost in a row and negate it with rest of the elements.

STEP 3:         [COLUMN REDUCTION]

                        Use cost matrix- Row reduced one for all columns do STEP 4.

STEP 4:            Find least cost in a column and negate it with rest of the elements.

STEP 5:            Preserve cost matrix C [which row reduced first and then column reduced]               

                           for the i ^th time.

STEP 6:            Enlist all edges (i, j) having cost = 0.

STEP 7:            Calculate effective cost of the edges. (i, j)=least cost in the i ^th row excluding

                           (i, j) + least cost in the j ^th column excluding (i, j).

STEP 8:            Compare all effective cost and pick up the largest l. If two or more have same cost then arbitrarily choose any one among them.

STEP 9:            Delete (i, j) means delete i^th row and j^th column change (j, i) value to infinity. (Used to avoid infinite loop formation) If (i,j) not present, leave it.

STEP 10:          Repeat step 1 to step 9 until the resultant cost matrix having order of 2*2 and reduce it. (Both R.R and C.C)

STEP 11:          Use preserved cost matrix Cn, Cn-1… C1

Choose an edge [i, j] having value =0, at the first time for a preserved matrix and leave that matrix.

STEP 12:          Use result obtained in Step 11 to generate a complete tour.

Example

\

Unit-IV/Lecture-07

Meaning of lower bound theory, Use of lower bound

Least Cost (LC) Search:

In both LIFO and FIFO branch-and-bound the selection rule for the next E-node is rather rigid and in a sense blind. The selection rule for the next E-node does not give any preference to a node that has a very good chance of getting the search to an answer node quickly.

     Thus, in given figure,

when node 30 is generated, it should have become obvious to the search algorithm that this node will lead to answer node in one move. However, the rigid FIFO rule first requires the expansion of all live nodes generated before node 30 was expanded.            

     The search for an answer node can often be speeded by using an "intelligent" ranking function (.) for live nodes. The next E-node is selected on the basis of this ranking function.

     If in the 4-queens example we use a ranking function that assigns node 30 a better rank than all other live nodes, then node 30 will become E-node, following node 29.The remaining live nodes will never become E-nodes as the expansion of node 30 results in the generation of an answer node (node 31).

    The ideal way to assign ranks would be on the basis of the additional computational effort (or cost) needed to reach an answer node from the live node. For any node x, this cost could be

(1) The number of nodes on the sub-tree x that need to be generated before any   answer node is generated or, more simply,

 (2) The number of levels the nearest answer node (in the sub-tree x) is from x

   Using cost measure (2), the cost of the root of the tree of Figure 8.1 is 4 (node 31 is four levels from node 1).The costs of nodes 18 and 34,29 and 35,and 30 and 38 are respectively 3, 2, and 1.The costs of all remaining nodes on levels 2, 3, and 4 are respectively greater than 3, 2, and 1.

   Using these costs as a basis to select the next E-node, the E-nodes are nodes 1, 18, 29, and 30 (in that order).The only other nodes to get generated are nodes 2, 34, 50, 19, 24, 32, and 31.

   The difficulty of using the ideal cost function is that computing the cost of a node usually involves a search of the sub-tree x for an answer node. Hence, by the time the cost of a node is determined, that sub-tree has been searched and there is no need to explore x again. For this reason, search algorithms usually rank nodes only based on an estimate (.) of their cost.

   Let (x) be an estimate of the additional effort needed to reach an answer node from x. node x is assigned a rank using a function (.) such that (x) =f (h(x)) + (x), where h(x) is the cost of reaching x from the root and f(.) is any non-decreasing function.

   A search strategy that uses a cost function (x) =f (h(x)) + (x), to select the next e-node would always choose for its next e-node a live node with least (.).Hence, such a strategy is called an LC-search (least cost search). 

   Cost function c (.) is defined as, if x is an answer node, then c(x) is the cost (level, computational difficulty, etc.) of reaching x from the root of the state space tree. If x is not an answer node, then c(x) =infinity, providing the sub-tree x contains no answer node; otherwise c(x) is equals the cost of a minimum cost answer node in the sub-tree x.

   It should be easy to see that (.) with f (h(x)) =h(x) is an approximation to c (.). From now on (x) is referred to as the cost of x.

Bounding:

            A branch -and-bound searches the state space tree using any search mechanism in which all the children of the E-node are generated before another node becomes the E-node.

          We assume that each answer node x has a cost c(x) associated with it and that a minimum-cost answer node is to be found. Three common search strategies are FIFO, LIFO, and LC.

          A cost function (.) such that (x) <=c(x) is used to provide lower bounds on solutions obtainable from any node x. If upper is an upper  bound on the cost of a minimum-cost solution, then all live nodes x with (x)>upper may be killed as all answer nodes reachable from x have cost c(x)>= (x)>upper. The starting value for upper can be set to infinity.

         Clearly, so long as the initial value for upper is no less than the cost of a minimum-cost answer node, the above rule to kill live nodes will not result in the killing of a live node that can reach a minimum-cost answer node .Each time a new answer is found ,the value of upper can be updated.

Unit-IV/Lecture-08

Introduction to parallel algorithms

Parallel algorithm is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.

Some algorithms are easy to divide up into pieces like this. For example, splitting up the job of checking all of the numbers from one to a hundred thousand to see which are primes could be done by assigning a subset of the numbers to each available processor, and then putting the list of positive results back together.

Parallel algorithms are valuable because of substantial improvements in multiprocessing systems and the rise of multi-core processors. In general, it is easier to construct a computer with a single fast processor than one with many slow processors with the same throughput. But processor speed is increased primarily by shrinking the circuitry, and modern processors are pushing physical size and heat limits. These twin barriers have flipped the equation, making multiprocessing practical even for small systems.

The cost or complexity of serial algorithms is estimated in terms of the space (memory) and time (processor cycles) that they take. Parallel algorithms need to optimize one more resource, the communication between different processors. There are two ways parallel processors communicate, shared memory or message passing.

Shared memory processing needs additional locking for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm. Message passing processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special buses like crossbar so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.

Another problem with parallel algorithms is ensuring that they are suitably load balanced. For example, checking all numbers from one to a hundred thousand is easy to split amongst processors; however, some processors will get more work to do than the others, which will sit idle until the loaded processors complete.