🔒 Locked

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

Started by 7aramy Jan 18, 2008 at 5:49 AM 4 replies 10.2k views

Original Post

Jan 18, 2008 at 5:49 AM

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?

alvaro

Jan 18, 2008 at 5:57 AM

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

7aramy

Jan 18, 2008 at 6: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.
So , I still don't have any idea about this question or how to answer it.
( I have very few knowledge about depth , breadth first searches )

Luckless

Jan 24, 2008 at 12:54 PM

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.

Sneftel

Jan 24, 2008 at 1:05 PM

Quote:
Original post by Talroth
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.

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.

Vorpy

Jan 24, 2008 at 8: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?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.