View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #17aramy  Members

Posted 17 January 2008 - 11:49 PM

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?

### #2Álvaro  Members

Posted 17 January 2008 - 11:57 PM

What do you have so far? What specific difficulties do you have solving the problem?

### #37aramy  Members

Posted 18 January 2008 - 12:02 AM

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 )

### #4Luckless  Members

Posted 24 January 2008 - 06:54 AM

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.

### #5Sneftel  Senior Moderators

Posted 24 January 2008 - 07:05 AM

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.

### #6Vorpy  Members

Posted 24 January 2008 - 02:11 PM

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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.