Page 31 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 2: Problems, Problem Spaces and Search

+” x2 + 3x+sin2x cos 2x dx Notes
This can be performed by dividing it into three lesser problems and solving each by
applying particular rules. Adding the results the whole solution is attained.

2. Can solution steps be ignored or undone?
Problem occurs under three classes ignorable, recoverable and irrecoverable. This
categorization is pertaining to the steps of the solution to a problem.

Example: Consider theorem proving. We may later discover that it is of no aid. We can
still continue further, as nothing is lost by this outmoded step. This is an example of ignorable
solutions steps.
Now consider the 8 puzzle problem tray and arranged in particular order. While moving from
the begin state towards objective state, we may make some dull move and consider theorem
proving. We may carry on by first proving lemma. But we may backtrack and untie
the unnecessary move. This only includes additional steps and the explanation steps are
recoverable.

Finally consider the game of chess. If a wrong move is done, it can neither be ignored nor be
recovered. The thing to do is to make the best utilization of present situation and proceed. This
is an example of an irrecoverable solution steps.
1. Ignorable problems Ex: theorem proving
(i) In which solution steps can be ignored.
2. Recoverable problems Ex: 8 puzzle

(i) In which solution steps can be undone
3. Irrecoverable problems Ex: Chess
(i) In which solution steps can’t be undone
A knowledge of these will assist in identifying the control structure.

3. Is the Universal Predictable?
Problems can be categorized into those with firm result (eight puzzle and water jug
problems) and those with unsure result (playing cards) in certain outcome problems,
planning could be made to produce a sequence of operators that assures to lead to a
solution. Planning assists to evade unwanted solution steps. For unsure result problems,
planning can at best produce a sequence of operators that has a good likelihood of
approaching to a solution. The uncertain result problems do not assures a solution and it
is frequently very expensive as the number of solution and it is frequently very expensive
as the number of solution paths to be discovered enhances exponentially with the
number of points at which the result can not be predicted. Therefore one of the hardest
types of problems to resolve is the irrecoverable, uncertain outcome problems (Ex: Playing
cards).
4. Is good solution absolute or relative ? (Is the solution a state or a path?)
There are two groups of problems. In one, like the water jug and 8 puzzle problems, we
are content with the solution, unaware of the solution path taken, while in the other group
not just any solution is suitable. We want the finest, like that of traveling sales man
problem, where it is the shortest path. In any path problems, by heuristic methods we get
hold of a solution and we do not discover alternatives.

LOVELY PROFESSIONAL UNIVERSITY 25