Ques : Introduction to State Space Search

 Structure of a state space:

The structures of state space are trees and graphs. A tree has one and only one path from any
point to any other point. Graph consists of a set of nodes (vertices) and a set of edges (arcs). Arcs
establish relationship (connections) between the nodes, i.e., a graph has several paths to a given
node. Operators are directed arcs between nodes.

The method of solving problem through AI involves the process of defining the search space,
deciding start and goal states and then finding the path from start state to goal state through
search space.

Search process explores the state space. In the worst case, the search explores all possible paths
between the initial state and the goal state.

Problem Solution:

In a state space, a solution is a path from the initial state to a goal state or sometime just a goal
state. A numeric cost is assigned to each path. It also gives the cost of applying the operators to
the states. A path cost function is used to measure the quality of solution and out of all possible
solutions, an optimal solution has the lowest path cost. The importance of cost depends on the
problem and the type of solution asked.

Problem formulation:

Many problems can be represented as state space. The state space of a problem includes: an
initial state, one or more goal state, set of state transition operator (or a set of production rules),
used to change the current state to another state. This is also known as actions. A control
strategy is used that specifies the order in which the rules will be applied. For example, Depthfirst search (DFS), Breath-first search (BFS) etc. It helps to find the goal state or a path to the
goal state.

In general, a state space is represented by 4 tuples as follows:𝑺𝒔
: [𝑺, 𝒔𝟎, 𝑶,𝑮]

Where S: Set of all possible states.
𝒔𝟎: start state (initial configuration) of the problem, 𝑠଴ ∈ 𝑆 .
O: Set of production rules (or set of state transition operator)
used to change the state from one state to another. It is the set
of arcs (or links) between nodes.

The production rule is represented in the form of a pair. Each pair consists of a left side that
determines the applicability of the rule and a right side that describes the action to be performed,
if the rule is applied.

G: Set of Goal state, 𝐺 ∈ 𝑆.