Problem Characteristics

Problem Characteristics

AU: Dec.-10, 14, May-14

To choose an appropriate method for a particular problem it is important to study the problem characteristics which are as follows:

1. Is the problem decomposable to smaller or easier problems? Can the problem be broken down to smaller problems so that it can be solved independently? Such a decomposed problem can be solved easily.

2. Can problem solution steps be ignored or undone?

The problem can fall in one of the following three categories.

Ignorable - In this type of problem solution steps can be ignored. For example - Theorem proving. In theorem proving if later it is known that certain step is not useful then still one can proceed further as nothing is lost due to repeated steps.

Recoverable - In this type of problem solution steps can be undone and backtracked. For example - The 8-Puzzle problem. In this problem while moving from initial state to goal state one may make some wrong moves but later can backtrack and recover by making correct move.

Irrecoverable - In this type of problem moves cannot be retracted. For example - Playing Chess in the game of chess one can make wrong move but then this move is neither to be ignored nor it can be recovered.

The above knowledge about the problem helps in determining the control structure. Ignorable problems can be solved using a simple control structure that never backtracks. Recoverable problems can be solved using backtracking. Irrecoverable problems can be solved by recoverable style methods via planning.

3. Is the problem universe predictable?

Further problem can be categorized as problem with certain outcome and problem with uncertain outcome. In certain outcome problems planning can be done to generate a sequence of operations that lead to a solution. For example in the 8-Puzzle problem every time move is made, it is known exactly what will happen. That is there is certain outcome!

In uncertain outcome problem planning can generate a best sequence of operations that can probably lead to problem solution. For example in Bridge game one cannot know exactly where all the cards are or what the other players will do on their turns. That is there is uncertain outcome.

For certain-outcome problems, planning can used to generate a sequence of operators that is guaranteed to lead to a solution where as for uncertain-outcome problems, a sequence of generated operators can only have a good probability of leading to a solution. Plan revision is made as the plan is carried out and the necessary feedback is provided.

4. Is a good solution absolute or relative?

Another category of problem is that, when we get solution is it the best one or may be some other path can give optimal (best among all) solution. For certain problems multiple feasible solutions exist but out them one is the best and it is the required solution.

Consider following example,

1. Marcus was a man

2. Marcus was a Pompeian

3. Marcus was born in 40 A.D.

4. All men are mortal.

5. All Pompeians died when the volcano erupted in 79 A.D

6. No mortal lives longer than 150 years.

7. It is now 2008 A.D.

Question: Is Marcus alive?

8. Marcus is mortal (1, 4)

9. Marcus is 1964 years. (3, 7)

10. Marcus is dead. (6, 8, 9)

- - - - OR - - - -

11. All Pompeians are died in 79 A.D.

12. Marcus is dead.

In above problem different reasoning paths lead to the answer. It does not matter not which path we follow.

In Travelling Salesman Problem one has to try all paths to find the shortest one. Any-path problems can be solved using heuristics that suggest good paths to explore. For best-path problems, much more exhaustive search will be performed to get optimal solution.

5. Is the solution a state or a path?

Consider following example,

Finding a consistent interpretation:

"The bank president ate a dish of pasta salad with the fork".

"bank" refers to a financial situation or to a side of a river?

"dish" or "pasta salad" was eaten?

Does "pasta salad" contain pasta, as "dog food" does not contain "dog"?

Which part of the sentence does "with the fork" modify? What if "with vegetables" is there?

In the above problem no processing record is required only final answer isoutcome.

In the Water Jug Problem the path that leads to the goal must be reported.

A path-solution problem can be reformulated as a state-solution problem by describing a state as a partial path to a solution. The question is whether that is natural or not.

6. Is the problem using consistent knowledge base? Does the problem require lots of knowledge or uses knowledge to constrain solutions?

To solve problem correctly it is highly necessary that the knowledgebase is consistent on the scale of time and data. In some problems the knowledge base is consistent and in some it is not. For example for evaluating Boolean expression complete knowledge of theorems and laws is required which are always true. Where as in data about rate card of hourly labour would change as per time and need to be updated so that manufacturing cost is correctly computed. Many reasoning system work well in consistent domain that are un-appropriate for inconsistent domain.

7. What is the role of knowledge?

In certain domain, knowledge plays crucial role while solving the problem. Consider following two problem,

i) Playing Chess

Here knowledge is important only to constrain the search for a solution. Additional knowledge of strategies would help to get faster solution.

ii) Reading Newspaper

Here knowledge is required even to be able to recognize a solution.

8. Does the task require periodic human-interaction with computer?

Here one need to distinguish between 2 types of problems:

i) Solitary problem, in which there is no intermediate communication and no demand for an explanation of the reasoning process.

ii) Conversational problem, in which intermediate communication is to provide either additional assistance to the computer or additional information to the user.

Problem Classification

There is a variety of problem-solving methods, but there is no one single way of solving all problems.

Not all new problems should be considered as totally new. Solutions of similar problems can be exploited.