Uninformed Search
The uninformed search strategies are given no information about the problem other than its definition. It is also called as blind search. It simply generate successor and distinguishes a goal state from a non goal state.
The following are types of uninformed search strategies
- Breadth first search.
- Uniform cost search
- Depth first search
- Depth limited search
- Iterative deepening depth first search.
- Bidirectional search
Formulating the State Space
In order to apply a specific search method on state space, first we need to formulate the problem, To do that we need to analyze the problem carefully for finding appropriate abstractions and ignore irrelevant details. This process involves defining the goal and set of actions performed which effects the state space.
For example consider fifteen puzzle problem. It contains fifteen tiles set and one empty block into which an adjacent tile can be sided. The goal situation is 2 particular arrangement which is obtained by a sequence of movements of tiles.
For this problem, there will be a maximum of 15 x 4 different moves (move left, move right, move up, move down moves-for each tile). An alternative approach involves only moving the blank (4 moves) the number of nodes in the state space graph for this representation of fifteen puzzle is 15!
Components of Implicit State Space Graphs
A particular part of the graph can be reached from start node is representing implicitly by a description of start node and descriptions of the successor nodes until acceptable path to a goal node has been found.
Basically, there are three components to an implicit representation of a state space graph.
- Description of start node.
- Operators: Labeled to arcs between two states. These are the functions of state transformation. These represents the models of the effects of actions.
- Goal Condition: It is a true false valued function on state descriptions.
