**0**

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

Started by Jan 17 2008 11:49 PM

,
5 replies to this topic

###
#1
Members - Reputation: **122**

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?

###
#3
Members - Reputation: **122**

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.

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 )

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 )

###
#4
Crossbones+ - Reputation: **2885**

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.

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.

###
#5
Senior Moderators - Reputation: **1788**

Posted 24 January 2008 - 07:05 AM

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.