Defining problem as state space search

Problem as State Space Search

 

State space search

“It is complete set of states including start and goal states, where the answer of the problem is to be searched”.

Problem

“It is the question which is to be solved. For solving the problem it needs to be precisely defined. The definition means, defining the start state, goal state, other valid states and transitions”.

A state space representation allows for the formal definition of a problem which makes the movement from initial state to the goal state quite easily. So we can say that various problems like planning, learning, theorem proving etc. are all essentially search problems only.

State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property.

 For Example:

The eight tile puzzle problem formulation

The eight tile puzzle consist of a 3 by 3 (3*3) square frame board which holds 8 movable tiles numbered 1 to 8. One square is empty, allowing the adjacent tiles to be shifted. The objective of the puzzle is to find a sequence of tile movements that leads from a starting configuration to a goal configuration.

problem_formulation_001

The states of 8 tile puzzle are the different permutations of the tiles within frame.

Lets do a standard formulation of this problem now.

States: It specifies the location  of each of the 8 tiles and the blank in one of the nice squares.

Initial state : Any state can be designated as the initial state.

Goal :  Many goal configurations are possible one such is shown in the figure

Legal moves ( or state) : They generate legal states that result from trying the four actions-

  • Blank moves left
  • Blank moves right
  • Blank moves up
  • Blank moves down

Path cost: Each step costs 1, so the path cost is the number of steps in the path.

The tree diagram showing the search space is shown in figure.

problem_formulation_002

 

Defining problem as state space search

Leave a Reply

Your email address will not be published. Required fields are marked *

Scroll to top
You cannot copy content of this page. The content on this website is NOT for redistribution