Anna University DESIGN AND ANALYSIS OF ALGORITHMS Two Marks unit 5
1. What is backtracking?
Backtracking constructs solutions one component at a time and such partially constructed solutions are evaluated as follows
If a partially constructed solution can be developed furtherv 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, nov alternatives for the 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.
2. What is a state space tree?
The processing of backtracking is implemented by constructing a tree of choices being made. This is called the state-space tree. Its root represents a 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 the solution, the nodes in the second level represent the choices for the second component and so on.
3. What is a promising node in the state-space tree?
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.
4. What is a non-promising node in the state-space tree?
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.
5. What do leaves in the state space tree represent?
Leaves in the state-space tree represent either non-promising dead ends or complete solutions found by the algorithm.
6. What is the manner in which the state-space tree for a backtracking algorithm is constructed?
In the majority of cases, a state-space tree for backtracking algorithm is constructed in the manner of depth-first search. 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. If the current node turns out to be non-promising, the algorithm backtracks to the node’s parent to consider the next possible solution to the problem, it either stops or backtracks to continue searching for other possible solutions.
7. What is n-queens problem?
The problem is to place ‘n’ queens on an n-by-n chessboard so that no two queens attack each other by being in the same row or in the column or in the same diagonal.
8. Draw the solution for the 4-queen problem.
Q
Q
Q
Q
Q
Q
Q
Q
9. Define the Hamiltonian circuit.
The Hamiltonian is defined as a cycle that passes through all the vertices of the graph exactly once. It is named after the Irish mathematician Sir William Rowan Hamilton (1805-1865).It is a sequence of n+1 adjacent vertices
vi0, vi1,……, vin-1, vi0
where the first vertex of the sequence is same as the last one while all the other n-1 vertices are distinct.
10. What is the subset-sum problem?
Find a subset of a given set S={s1,………,sn} of ‘n’ positive integers whose sum is equal to a given positive integer ‘d’.
11. When can a node be terminated in the subset-sum problem?
The sum of the numbers included are added and given as the value for the root as s’. The node can be terminated as a non-promising node if either of the two equalities holds:
s’+si+1>d (the sum s’ is too large)
s’+ sj<d (the sum s’ is too small)
12. How can the output of a backtracking algorithm be thought of?
The output of a backtracking algorithm can be thought of as an n-tuple (x1, …xn) where each coordinate xi is an element of some finite linearly ordered set Si. If such a tuple (x1, …xi) is not a solution, the algorithm finds the next element in Si+1 that is consistent with the values of (x1, …xi) and the problem’s constraints and adds it to the tuple as its (I+1)st coordinate. If such an element does not exist, the algorithm backtracks to consider the next value of xi, and so on.
13. Give a template for a generic backtracking algorithm.
ALGORITHM Backtrack(X[1..i])
//Gives a template of a generic backtracking algorithm
//Input X[1..i] specifies the first I promising components of a solution
//Output All the tuples representing the problem’s solution
if X[1..i] is a solution write X[1..i]
else
Si+1 consistent with X[1..i] and the constraints doÎfor each element x
xßX[i+1]
Backtrack(X[1..i+1])
14. What are the tricks used to reduce the size of the state-space tree?
The various tricks are
Exploit the symmetry often present in combinatorial problems. Sov some solutions can be obtained by the reflection of others. This cuts the size of the tree by about half.
v Preassign values to one or more components of a solution
v Rearranging the data of a given instance.
15. What is the method used to find the solution in n-queen problem by symmetry?
The board of the n-queens problem has several symmetries so that some solutions can be obtained by other reflections. Placements in the last n/2 columns need not be considered, because any solution with the first queen in square (1,i), n/2 i n can be obtained by reflection from a solution with the first queen in square (1,n-i+1)
16. What are the additional features required in branch-and-bound when compared to backtracking?
Compared to backtracking, branch-and-bound requires:
A way to provide, for every node of a state space tree, a bound onv the best value of the objective function on any solution that can be obtained by adding further components to the partial solution represented by the node.
v The value of the best solution seen so far
17. What is a feasible solution and what is an optimal solution?
In optimization problems, a feasible solution is a point in the problem’s search space that satisfies all the problem’s constraints, while an optimal solution is a feasible solution with the best value of the objective function.
18. When can a search path be terminated in a branch-and-bound algorithm?
A search path at the current node in a state-space tree of a branch-and-bound algorithm can be terminated if
v The value of the node’s bound is not better than the value of the best solution seen so far
v The node represents no feasible solution because the constraints of the problem are already violated.
The subset of feasible solutions represented by the node consistsv of a single point in this case compare the value of the objective function for this feasible solution with that of the best solution seen so far and update the latter with the former if the new solution is better.
19. Compare backtracking and branch-and-bound.
Backtracking Branch-and-bound
State-space tree is constructed using depth-first search State-space tree is constructed using best-first search
Finds solutions for combinatorial non-optimization problems Finds solutions for combinatorial optimization problems
No bounds are associated with the nodes in the state-space tree Bounds are associated with the each and every node in the state-space tree
20. What is the assignment problem?
Assigning ‘n’ people to ‘n’ jobs so that the total cost of the assignment is as small as possible. The instance of the problem is specified as a n-by-n cost matrix C so that the problem can be stated as: select one element in each row of the matrix so that no two selected items are in the same column and the sum is the smallest possible.
21. What is best-first branch-and-bound?
It is sensible to consider a node with the best bound as the most promising, although this does not preclude the possibility that an optimal solution will ultimately belong to a different branch of the state-space tree. This strategy is called best-first branch-and-bound.
22. What is 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 the knapsack. It is convenient to order the items of a given instance in descending order by their value-to-weight ratios. Then the first item gives the best payoff per weight unit and the last one gives the worst payoff per weight unit.
23. Give the formula used to find the upper bound for knapsack problem.
A simple way to find the upper bound ‘ub’ is to add ‘v’, the total value of the items already selected, the product of the remaining capacity of the knapsack W-w and the best per unit payoff among the remaining items, which is vi+1/wi+1
ub = v + (W-w)( vi+1/wi+1)
24. What is the traveling salesman problem?
The problem can be modeled as a weighted graph, with the graph’s vertices representing the cities and the edge weights specifying the distances. Then the problem can be stated as finding the shortest Hamiltonian circuit of the graph, where the Hamiltonian is defined as a cycle that passes through all the vertices of the graph exactly once.
25. What are the strengths of backtracking and branch-and-bound?
The strengths are as follows
It is typically applied to difficult combinatorial problems forv which no efficient algorithm for finding exact solution possibly exist
v It holds hope for solving some instances of nontrivial sizes in an acceptable amount of time
Even if it does not eliminate any elements of a problem’s statev space and ends up generating all its elements, it provides a specific technique for doing so, which can be of some value.
Explain
• n-Queen’s Problem
• Hamiltonian Circuit problem
• Subset-Sum problem
2. Explain about Branch-and-Bound
Explain
§ Assignment problem
§ Knapsack problem
§ Travelling salesman problem.
3. Explain Travelling Salesman Problem with suitable diagrams
Explain
• TSP Concepts
• Graph
• Computation
• Algorithm
4. Discuss in detail about Assignment Problem
Explain
• Assignment Problem Definition
• Example
• Graph representation
• Algorithm computation
5. Explain Knapsack Problem & n-Queen’s Problem
Explain
• Knapsack 0/1Example & n-Queen’s Problem Example
• Graph representation
• Algorithm computation
1. What is backtracking?
Backtracking constructs solutions one component at a time and such partially constructed solutions are evaluated as follows
If a partially constructed solution can be developed furtherv 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, nov alternatives for the 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.
2. What is a state space tree?
The processing of backtracking is implemented by constructing a tree of choices being made. This is called the state-space tree. Its root represents a 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 the solution, the nodes in the second level represent the choices for the second component and so on.
3. What is a promising node in the state-space tree?
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.
4. What is a non-promising node in the state-space tree?
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.
5. What do leaves in the state space tree represent?
Leaves in the state-space tree represent either non-promising dead ends or complete solutions found by the algorithm.
6. What is the manner in which the state-space tree for a backtracking algorithm is constructed?
In the majority of cases, a state-space tree for backtracking algorithm is constructed in the manner of depth-first search. 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. If the current node turns out to be non-promising, the algorithm backtracks to the node’s parent to consider the next possible solution to the problem, it either stops or backtracks to continue searching for other possible solutions.
7. What is n-queens problem?
The problem is to place ‘n’ queens on an n-by-n chessboard so that no two queens attack each other by being in the same row or in the column or in the same diagonal.
8. Draw the solution for the 4-queen problem.
Q
Q
Q
Q
Q
Q
Q
Q
9. Define the Hamiltonian circuit.
The Hamiltonian is defined as a cycle that passes through all the vertices of the graph exactly once. It is named after the Irish mathematician Sir William Rowan Hamilton (1805-1865).It is a sequence of n+1 adjacent vertices
vi0, vi1,……, vin-1, vi0
where the first vertex of the sequence is same as the last one while all the other n-1 vertices are distinct.
10. What is the subset-sum problem?
Find a subset of a given set S={s1,………,sn} of ‘n’ positive integers whose sum is equal to a given positive integer ‘d’.
11. When can a node be terminated in the subset-sum problem?
The sum of the numbers included are added and given as the value for the root as s’. The node can be terminated as a non-promising node if either of the two equalities holds:
s’+si+1>d (the sum s’ is too large)
s’+ sj<d (the sum s’ is too small)
12. How can the output of a backtracking algorithm be thought of?
The output of a backtracking algorithm can be thought of as an n-tuple (x1, …xn) where each coordinate xi is an element of some finite linearly ordered set Si. If such a tuple (x1, …xi) is not a solution, the algorithm finds the next element in Si+1 that is consistent with the values of (x1, …xi) and the problem’s constraints and adds it to the tuple as its (I+1)st coordinate. If such an element does not exist, the algorithm backtracks to consider the next value of xi, and so on.
13. Give a template for a generic backtracking algorithm.
ALGORITHM Backtrack(X[1..i])
//Gives a template of a generic backtracking algorithm
//Input X[1..i] specifies the first I promising components of a solution
//Output All the tuples representing the problem’s solution
if X[1..i] is a solution write X[1..i]
else
Si+1 consistent with X[1..i] and the constraints doÎfor each element x
xßX[i+1]
Backtrack(X[1..i+1])
14. What are the tricks used to reduce the size of the state-space tree?
The various tricks are
Exploit the symmetry often present in combinatorial problems. Sov some solutions can be obtained by the reflection of others. This cuts the size of the tree by about half.
v Preassign values to one or more components of a solution
v Rearranging the data of a given instance.
15. What is the method used to find the solution in n-queen problem by symmetry?
The board of the n-queens problem has several symmetries so that some solutions can be obtained by other reflections. Placements in the last n/2 columns need not be considered, because any solution with the first queen in square (1,i), n/2 i n can be obtained by reflection from a solution with the first queen in square (1,n-i+1)
16. What are the additional features required in branch-and-bound when compared to backtracking?
Compared to backtracking, branch-and-bound requires:
A way to provide, for every node of a state space tree, a bound onv the best value of the objective function on any solution that can be obtained by adding further components to the partial solution represented by the node.
v The value of the best solution seen so far
17. What is a feasible solution and what is an optimal solution?
In optimization problems, a feasible solution is a point in the problem’s search space that satisfies all the problem’s constraints, while an optimal solution is a feasible solution with the best value of the objective function.
18. When can a search path be terminated in a branch-and-bound algorithm?
A search path at the current node in a state-space tree of a branch-and-bound algorithm can be terminated if
v The value of the node’s bound is not better than the value of the best solution seen so far
v The node represents no feasible solution because the constraints of the problem are already violated.
The subset of feasible solutions represented by the node consistsv of a single point in this case compare the value of the objective function for this feasible solution with that of the best solution seen so far and update the latter with the former if the new solution is better.
19. Compare backtracking and branch-and-bound.
Backtracking Branch-and-bound
State-space tree is constructed using depth-first search State-space tree is constructed using best-first search
Finds solutions for combinatorial non-optimization problems Finds solutions for combinatorial optimization problems
No bounds are associated with the nodes in the state-space tree Bounds are associated with the each and every node in the state-space tree
20. What is the assignment problem?
Assigning ‘n’ people to ‘n’ jobs so that the total cost of the assignment is as small as possible. The instance of the problem is specified as a n-by-n cost matrix C so that the problem can be stated as: select one element in each row of the matrix so that no two selected items are in the same column and the sum is the smallest possible.
21. What is best-first branch-and-bound?
It is sensible to consider a node with the best bound as the most promising, although this does not preclude the possibility that an optimal solution will ultimately belong to a different branch of the state-space tree. This strategy is called best-first branch-and-bound.
22. What is 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 the knapsack. It is convenient to order the items of a given instance in descending order by their value-to-weight ratios. Then the first item gives the best payoff per weight unit and the last one gives the worst payoff per weight unit.
23. Give the formula used to find the upper bound for knapsack problem.
A simple way to find the upper bound ‘ub’ is to add ‘v’, the total value of the items already selected, the product of the remaining capacity of the knapsack W-w and the best per unit payoff among the remaining items, which is vi+1/wi+1
ub = v + (W-w)( vi+1/wi+1)
24. What is the traveling salesman problem?
The problem can be modeled as a weighted graph, with the graph’s vertices representing the cities and the edge weights specifying the distances. Then the problem can be stated as finding the shortest Hamiltonian circuit of the graph, where the Hamiltonian is defined as a cycle that passes through all the vertices of the graph exactly once.
25. What are the strengths of backtracking and branch-and-bound?
The strengths are as follows
It is typically applied to difficult combinatorial problems forv which no efficient algorithm for finding exact solution possibly exist
v It holds hope for solving some instances of nontrivial sizes in an acceptable amount of time
Even if it does not eliminate any elements of a problem’s statev space and ends up generating all its elements, it provides a specific technique for doing so, which can be of some value.
16 Marks
1. Explain about Backtracking with suitable examplesExplain
• n-Queen’s Problem
• Hamiltonian Circuit problem
• Subset-Sum problem
2. Explain about Branch-and-Bound
Explain
§ Assignment problem
§ Knapsack problem
§ Travelling salesman problem.
3. Explain Travelling Salesman Problem with suitable diagrams
Explain
• TSP Concepts
• Graph
• Computation
• Algorithm
4. Discuss in detail about Assignment Problem
Explain
• Assignment Problem Definition
• Example
• Graph representation
• Algorithm computation
5. Explain Knapsack Problem & n-Queen’s Problem
Explain
• Knapsack 0/1Example & n-Queen’s Problem Example
• Graph representation
• Algorithm computation
0 comments:
Post a Comment