Two marks Questions with Answers

Two Marks Questions with Answers

Q.1 When is the class of problem said to be intractable.  AU: Dec.-03

Ans.: The problems whose algorithm take an unreasonably large amount of resources (time and/or space) are called intractable.

For example -TSP

Given set of 'N' points, one should find shortest tour which connect all of them. Algorithm will consider all N! orderings, i.e. consider n = 16. 16! > 250 which is impractial for any computer.

Q.2 What is the power of heuristic search? AU: Dec.-04

Why does one go for heuristic search? AU: Dec.-05

Ans.:Heuristic search uses problem specific knowledge while searching in state space. This helps to improve average search performance.

They use evaluation function which denote relative desirability (goodness) of a expanding node set. This makes the search more efficient and faster. One should go for heuristic search because it has power to solve large, hard problems in affordable times.

Q.3 What is the advantage of heuristic function?  AU: Dec.-09, 11

Ans.: Heuristic function ranks alternative paths in various search algorithms, at each branching step, based on the available information, so that a better path is chosen. The main advantage of heuristic function is that it guides for which state to explore now, while searching. It makes use of problem specific knowledge like constraints to check the goodness of a state to be explored. This drastically reduces the required searching time.

Q.4 State the reason when hill climbing often gets stuck.  AU: May-10

Ans. Local maxima is the state where hill climbing algorithm is sure to get stuck. Local maximum is the peak that is higher than each of its neighbour states, but lower than the global maximum. So we have missed the better state here. All the search procedure turns out to be wasted here. It is like a dead end.

Q.5 When a heuristic function h is said to be admissible? Give an admissible heuristic function for TSP.  AU: Dec.-10

Ans.: Admissible heuristic function is that function which never over estimates the cost to reach the goal state. It means that h(n) gives true cost to reach the goal state 'n'.

The admissible heuristic for TSP is,

i) Minimum spanning tree.

ii) Minimum assignment problem.

Q.6 What do you mean by local maxima with respect to search technique? AU: May-11

Ans.: Local maximum is the peak that is higher than each of its neighbour states, but lower than the global maximum i.e. a local maxima is a tiny hill on the surface whose peak is not as high as the main peak (which is a optimal solution). Hill climbing fails to find optimum solution when it encounters local maxima. Any small move, from here also makes things worse (temporarily). At local maxima all the search procedure turns out to be wasted here. It is like a dead end.

Q.7 How can we avoid ridge and plateau in hill climbing?  AU: Dec.-12

Ans.: Ridge and plateau in hill climbing can be avoided using methods like backtracking, making big jumps. Backtracking and making big jumps helps to avoid plateau, whereas, application of multiple rules help to avoid the problem of ridges.

Q.8 Define the effect of heuristic accuracy on performance. (Refer Q.2)  AU: Dec.-13

Ans.:Heuristic search uses problem specific knowledge while searching in state space. This helps to improve average search performance.

They use evaluation function which denote relative desirability (goodness) of a expanding node set. This makes the search more efficient and faster. One should go for heuristic search because it has power to solve large, hard problems in affordable times.

Q.9 What is heuristic search strategy? (Refer Q.2)   AU: Dec.-14