Q.Write any problem with its solution in respect to problem solving technique.

Answer:

The process of problem-solving using searching consists of the following steps.

Define the problem

Analyze the problem

Identification of possible solutions

Choosing the optimal solution

Implementation

Example:

8 Puzzle Problem:

• Here, we have a 3×3 matrix with movable tiles numbered from 1 to 8 with a blank space. The tile adjacent to the blank space can slide into that space. The objective is to reach a specified goal state similar to the goal state, as shown in the below figure.

• In the figure, our task is to convert the current state into goal state by sliding digits into the blank space.

In the above figure, our task is to convert the current(Start) state into goal state by sliding digits into the blank space.

The problem formulation is as follows:

• States: It describes the location of each numbered tiles and the blank tile.
• Initial State: We can start from any state as the initial state.
• Actions: Here, actions of the blank space is defined, i.e., either left, right, up or down
• Transition Model: It returns the resulting state as per the given state and actions.
• Goal test: It identifies whether we have reached the correct goal-state.
• Path cost: The path cost is the number of steps in the path where the cost of each step is 1.

1. Note: The 8-puzzle problem is a type of sliding-block problem which is used for testing new search algorithms in artificial intelligence.

When a problem can be divided into a set of sub problems, where each sub problem can be solved separately and a combination of these will be a solution, AND-OR graphs or AND – OR trees are used for representing the solution.

The decomposition of the problem or problem reduction generates AND arcs.

The figure shows an AND-OR graph 

1. To pass any exam, we have two options, either cheating or hard work.
2. In this graph we are given two choices, first do cheating or (The red line) work hard and (The arc) pass.
3. When we have more than one choice and we have to pick one, we apply OR condition to choose one.(That’s what we did here).
4. Basically the ARC here denote AND condition.
5. Here we have replicated the arc between the work hard and the pass because by doing the hard work possibility of passing an exam is more than cheating.