# QUESTION : Water Jug problem ( depth , breadth-first) ?

This topic is 3651 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello I have an exam after 2 days ( not critical but still important ) in AI. I'm solving questions to understand how it's going in AI. Can any one solve or give me a hint or online tutorial ( simple not too deep into the AI ) .. Please help by any means ! Q" Suppose you have two jugs, the first can take 5 gallons; the second can take 7 gallons. If the goal is to have 3 gallons in the 7 gallons jugs. Draw 4 levels of the search space and introduce a mechanism for the best-first search such that each state appear in the search space takes higher weight. 4. Given the following graph with starting state A: • Apply the depth-first algorithm to find G as a goal. • Apply the breadth-first algorithm to find G as a goal. • Complete Hill Climbing. • Best-first. • A Is it A*? Why?

##### Share on other sites
What do you have so far? What specific difficulties do you have solving the problem?

##### Share on other sites
Thanks alvaro for your interesting ,
I'm trying to understand the AI thorough this type of questions , as it's not my main study nor I'm interesting in it. But i'm supposed to solve similar question to this in the next exam to pass all ones.
( I have very few knowledge about depth , breadth first searches )

##### Share on other sites
I'm not really sure how the question is having you tackle the problem. I know the answer but I can't think of why you would use a graph structure to solve it.

Any problem where you can have 2 known volumes (and can mark them. Could work with weights as well I guess) where X < Y, you can use X to mark a point on Y and get the value of Y-X. Using that new value you can proceed to make other values, but I can't think of a good use of graphs for such a problem.

##### Share on other sites
Quote:
 Original post by TalrothI'm not really sure how the question is having you tackle the problem. I know the answer but I can't think of why you would use a graph structure to solve it. Any problem where you can have 2 known volumes (and can mark them. Could work with weights as well I guess) where X < Y, you can use X to mark a point on Y and get the value of Y-X. Using that new value you can proceed to make other values, but I can't think of a good use of graphs for such a problem.

The question doesn't have anything to do with bar graphs or anything. Clicky. (That's a good clicky for you too, 7aramy.)

In general, graphs are used to solve problems like this by enumerating the state space and transitions. Each node in the graph is a possible state the world can be ("5 gallons in the first jug, 4 in the second"), each edge represents an action that can be taken from that state ("fill the second jug from the first"), each leading to the resultant state ("2 gallons in the first jug, 7 in the second"). Graph search algorithms are then used to find the solution.

##### Share on other sites
Depth and breadth first graph traversals have applications in lots of places, not just AI. You can't find any descriptions of them?