State space search

state space search and its example

1. STATE SPACE SEARCH Prof. Neeraj Bhargava Kapil Chauhan Department of Computer Science School of Engineering & Systems Sciences MDS University, Ajmer

2. STATE SPACE SEARCH Contents:- Introduction State space search phases Water jug problem Example of state space search Types of state space search algorithm Heuristic search algorithm Uninformed search algorithm

3. STATE SPACE SEARCH Introduction :-A state space search consist of a tree of symbolic stack that are generated when all possible operation are iteratively apply to the current state of symbol represented object composing the problem. Problem can be characterized as a space consisting of a set of state and set of operation.

4. STATE SPACE SEARCH THREE PHASE Initial state:- it is the started where we start the solving the problem. Intermediate state: - a solution to a problem is sequence of operation that maps initial state to final state. Final state :- it is the state that is final an solution on the problem.

5. WATER JUG PROBLEM You have a 4-gallon and 3-gallon water jug You have a faucet with an unlimited amount of water You need to get exactly 2 gallons in 4-gollans jug State representation :-(x , y) X:-contents of four gallon Y:-contents of three gallon Initial state(0 , 0) Goal state(2 , n)

6. EXAMPLE OF STATE SPACE SEARCH

7. TYPES OF STATE SPACE SEARCH Heuristic search algorithm:- Hill climbing A* algorithm Uninformed search algorithm:- 1. breath-first search 2. depth-first search 3. depth-limited search 4.iterative depending depth-first search 5. uniform cost search

8. HEURISTIC SEARCH ALGORITHM Generate a possible solution which can either be a point in the problem space or a path from the initial state. Test to see if this possible solution is a real solution by comparing the state reached with the set of goal states. If it is a real solution, return. otherwise repeat from 1.

9. UNINFORMED SEARCH ALGORITHM Uninformed search algorithm is a class of general-purpose search algorithm which operates in brute force way. Uninformed search algorithm about state or search space other than how to traverse the tree, so it is also called blind search.

10. Assignment Explain State Space S earch in Artificial I ntelligence with example.