Question

Water-Jug Problem

07 Nov 2017
Answer :
Word Count : 1346

Imagine that you have two jugs called X and Y. Initially, both are empty. You are allowed to fill either

jug X or jug Y from a tap but if you do, you have to fill it completely. You are also allowed to fill jug X

from jug Y, or jug Y from jug X, and to empty either jug on the ground. Jug X can hold 4 pints and jug

Y can hold 3 pints.

The problem is simply this: given the allowed actions, can you manage to reach a state where you have exactly 2 pints in jug X. This problem is known as the water jugs problem and it has no easy solution. If we just fill X from the tap we end up with 4 pints in X, not 2. If we fill Y from the tap and empty it into X, we end up with 3 pints in X. The only way to find a solution to this problem is to consider systematically the effects achieved by performing sequences of actions. But how can we go about this? Systematically considering all possible sequences of actions is just like systematically considering all possible sequences of locations (i.e. all possible routes). So the water jugs problem can be construed as a sort of search problem. Of course, if we are going to construe the water jugs problem as a search problem, nodes in the search space will have to represent states of the two jugs rather than locations in a physical environment. The start node, will have to be a representation of the initial state (e.g. 0 pints in both jugs); the goal node will have to be a representation of the goal state (e.g. 2 pints in X, any amount

in Y), and the successor function will have to return that set of new states which can be reached from

any given state by performing exactly one allowed action. So the main difference between this example and the one used in the previous chapter is that each state now contains some components (e.g. the contents of the two jugs) rather than just being an atomic value (e.g. clock_tower).

Constructing Successor Nodes

We can represent states in the water jugs problem as two-element lists in which the first element is an

integer representing the number of pints in the jug called X, and the second element is an integer

representing the number of pints in Y. Thus, the state in which X has 3 pints in it and Y has 2 would be

represented by the list expression:

[3 2]

We could implement the successor function using the approach that we took with the path-finding

problem, i.e. we could construct a database showing the connections between states and then use a

foreach loop to dig out the states we can achieve in one move. The beginning of the database might

look something like this:

[ [[0 0] [4 0]]

[[0 0] [0 3]]

...

...

] -> database;

These first two elements represent the fact that from the state [0 0] you can either fill X to achieve [4

0] or fill

_________ _____ ___ __________ ___ __________ ______ _____ ________ ________ _______.
___ _________ ____ ___ _____ __________ _______ ____ ________ _______ _________ ___.
_____ ______ _______ ____ ______ ______ ________.
__________ ________ _________ ________ ___.
____ ________ ____ _____ _____ _________ __________ ___ ____ _____ ________.
_______ ______ _________ _____ ______ _________ ___ ____ _________ ___.
_____ ________ ____ __________ ___ ____.
____ ______ _________ _________ __________ _________ ____ ________ __________ ___ _____.
______ ___ _____ ______ ____ ___ ________ ______ ___ ____ __________ _____.
_________ _________ _______ __________ _______ ___ _________ _____ __________ _________ _________.
____ ______ __________ __________ _______.
_______ _____ __________ __________ ______ _____ ____.
___ _________ _________ _________ _____ ____ _________ ____ ______ ______ ________ ___.
_______ _________ ______ _________ ____ ______ __________ _________ _______ ______.
____ ________ _____ ________ __________ ______ ______ ______ _________ _______.
_______ ______ _______ _________ ________.
_______ ________ __________ ______ _____ ____ ___.
_________ _____ _________ _________ ______ __________ ______ _____ _________ ________ ______ ________.
_____ ____ __________ _______ _______ ______ ________ ___.
________ ____ ___ ___ ___ _______ _________ _______ _______ __________.
________ ___ _________ _________ ___ ___ __________ ______ _________ ____ ______ _______.
______ ___ _____ ________ ________.
____ _______ _____ ________ _____.
___ __________ __________ __________ _______ _____ ______ _________.
_________ __________ _____ ___ _________ _________ _________ _______ ______ _______ _________ ______.
_________ _____ _________ _________ ____ ________ _________.
_______ _____ ______ ________ ______ _____ __________ _____ ____.
_____ ____ ________ __________ ___ ______.
__________ __________ ______ ____ ___.
_______ ___ _______ _____ ___.
____ _______ ____ _________ ___.
_________ ___ __________ ________ ____ ______ ______ _____ ____ _______ _____.
__________ __________ ____ ________ ________ ____ ____ _____ __________ ____.
______ ___ _____ ____ ______ ______ _____ _______ __________ ________ _______.
_______ ____ ______ __________ ______ ____ __________ ____ ___ ________.
________ _____ _____ _______ ___ ___.
___ ______ ______ __________ _________.
___ _________ ____ __________ __________.
________ ____ _________ _______ ___.
________ ______ _______ ________ ______ _____.
_____ ____ _________ _______ _______ ________ ______ _________ ________.
________ _______ ___ __________ ___ _____ _________ ___ _________ _____ ______.
______ ___ ______ ____ _______ ___ ________ _________ ______.
___ ________ ______ ______ _________ _________ _________.
____ ___ _______ _______ ________ ________ _____ ____ ________ __________ _____ ______.
_____ ____ ____ __________ __________ ____ _________ _____ ______ __________ __________.
____ _________ __________ _________ __________ _____ _____ _________ ___ __________ _________.
________ ___ __________ __________ _______.
______ _________ ________ _______ ____ __________ _____ ______ __________ _______ _____.
______ _______ _______ ___ ____.
__________ ________ ____ _________ ______ _____ ________ _________.
________ _____ _________ _________ _______ _______ _______ __________ ______ ______.
________ _____ ________ ____ _____ _____ ____ _____ _______ ________ __________ _______.
________ ____ ____ __________ ______ ____ __________.
___ _________ _________ _________ ______ ____ ________ ________ ____ ____ ________.
_____ ________ ____ ____ _________ ______ ______ ______ ________ ______ ____ _____.
_______ ________ ___ _________ _______.
______ ________ ___ _____ ____.
________ _____ ________ _______ _____.
____ ____ __________ _______ _________ ____ _________ ______ ________ _______.
___ __________ ___ _______ _____ __________ _____ __________ ________ ____.
____ ______ ____ _____ ___.
____ _________ _________ __________ ______ ____ _____ __________ ______.
____ ______ ___ ____ _______ _______ _____ _______ __________ _____ _______.
________ ________ ______ ______ _______ _________ ___ _____ _________ ___ _____ _______.
____ ______ __________ ____ _____ _______ ______ ______ ______.
______ __________ __________ ____ __________ _______ _______ _________ ___ ______ ______ __________.
__________ ____ _________ ________ __________ ________ ______ _____.
________ __________ ____ ________ _______ _________ ___ _____ ______ _______ ___ _____.
_______ ___ ________ ___ _______ _______ ____ __________ ___ _________ ______ ____.
______ _____ ___ __________ _________.
___ ______ ___ ________ ________.
______ ________ _____ __________ _________ _______.
______ __________ ________ _______ __________ ___ _______ _________ ____ ______ _________.
_____ __________ ______ _______ _____ ____ _____ ____.
_________ ____ ___ ______ _____ _____.
_______ ___ ___ _____ _____ _______ ________ __________ _____ ___ ___ ____.
____ __________ ___ ________ __________ ________ ____ ___ ____.
__________ ___ _________ _______ _________ _______ ______ ________ _______ _____.
_______ __________ ______ _____ _________ ______ ____.
_____ ______ ______ __________ __________.
___ _________ ______ ________ __________ _________ _________ _____.
____ __________ ______ ______ _________ ___ _____ _______ ________ __________.
____ ___ ___ ______ _______ _______ _____ _______ ________ ________ _________ __________.
_________ _________ ____ _______ ______ __________ __________ ________ __________.
____ _______ ____ _________ _____ __________.
_______ __________ ___ _____ ________ _____ ___ _________.
________ ________ _________ ___ ____ _________ ______ ________ ____ ________ _____.
______ _________ _________ ________ ____ __________ _________ ____ _____.
_______ ________ ___ ____ ___ _________ _________ ____ ___ _________ _________ _______.
__________ __________ _________ ______ _______ _________ _______ ____ ____.
______ _________ ______ _________ ____.
____ ___ ___ ______ ___ _________ ______.
_______ ______ ___ __________ __________ ____ _________ __________ ________ ________.
_______ _____ _________ ________ _________ ___ ______.
______ ________ _______ _____ ______.
_________ _________ __________.
IGNOU ACADEMY
Your IGNOU journey, made easier.
  • Solved Assignments
  • Study Notes
  • Guess Papers
  • Question Papers
Skip in 10
Top
📞
Call Support Instant phone assistance IGNOU MCSE 3 2011 - Water-Jug Problem | IGNOU Academy
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→