NOTE TO CHEGG EXPERTS

**********************************

PLEASE DO NOT COPY FROM GEEKS FOR GEEKS TO RATE YOUR REVIEW AS 5 STARS.

I TRIED BUT COULD NOT GET IT AT ALL.

PLEASE WRITE A CODE IN PYTHON FOR ABOVE STATE SPACE SEARCH

IMPLEMENT BFS AND IDFS ALGORITHM (PYTHON CODE) FROM HOMEWORK PROBLEM. 3

USE THE STATE SPACE SEARCH ON ITS STATES

*******************************************************************************************************************************************************************************************************************

Use the implicit state space of the third question of homework 1: You need exactly one liter of water. You have only a 17-liter jug and a 7-liter jug. You can 1. fill either jug from a well, 2. empty the contents of a jug, or 3. pour water from one jug to the other jug. Unfortunately, you are hopeless at guessing quantities. Given only these three operations, how can you get one liter of water in a jug? The solution to this problem can be reduced to a state space graph searching algorithm. We will use a state representation consisting of the pair (i,j)where i is the amount, in liters, in the 17-liter jug and j is the amount in the 7-litter jug. Define the neighbors of an arbitrary node associated with state (i,j)? That is, you have three operations that can be applied to either jug. For each of the six possible operations applied to (i,j), what is the resulting state.

Note: there are a finite number of states as i and j are integers with 0 i 17 and 0 j 7.

1. (30 points) Implement a program to conduct a depth-first search of this space. The search should use (0,0)as the start state. The states (1,?)and (?,1)are the goal states (that is, one want one liter in a jug, and you dont care what is in the other jug. Use graph search. That is, dont repeatedly expand the same state. Remember the states that have been seen. Output the list of states in order of expansion. Mention how your code ordered the operations for pushing new states onto the stack. Output the sequence of state, operation that creates a path from the initial state to a goal state. You can use an abbreviation or number for the operation. Such as the number 1-6 for the operations, or abbreviations such as 1i, 1j, 2i, 2j, 3i, and 3j for the rule and jug. So the start of the sequence could look like (0,0), 1i , (17,0), 3i, (10,7), ...

2. (30 points) Implement a program to conduct iterative deepening search of the same space. For each depth level, output the level and the list of states in order of expansion. Output the sequence of state, operation that creates a path from the initial state to a goal state.

3. You need exactly one liter of water. You have only a 17-liter jug and a 7-liter jug. You can 1. fill either jug from a well, 2. empty the contents of a jug, or 3. pour water from one jug to the other jug. Unfortunately, you are hopeless at guessing quantities. Given only these three operations, how can you get one liter of water in a jug? The solution to this problem can be reduced to a state space graph searching algorithm. We will use a state representation consisting of the pair (i, j) where i is the amount, in liters, in the 17-liter jug and j is the amount in the 7-litter jug. (a) (10 points) Define the neighbors of an arbitrary node associated with state (i, j)? That is, you have three operations that can be applied to either jug. For eacn of the six possible operations applied to (i, j), what is the resulting state. (b) (10 points) With an initial state of (0,0), draw all states of the state space graph reachable with three operations from the initial state. Label each are between the states with the operations that causes the transition. An arc may have multiple labels. For example, emptying either jug in the initial state causes a self loop back to (0,0)