**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, 𝐺 ∈ 𝑆.**

## 0 टिप्पणियाँ:

## Post a Comment