Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In AI we can classify a problem in 3 classes, ignorable, recoverable or irrecoverable problems. Now while reading Water jug Problem
I am wondering in which of these 3 class it should fall? It should reside under recoverable right? As we can go back to the previous state in Water Jug Problem by altering the water level, I think it is recoverable. Is my thinking right?
Recoverable, as we can pour all water back to the 12L jug to restore the original state, hence any state derived thereof (by following the same steps from the start). The problem is, also, solvable:
[12, 0, 0]
[4, 8, 0]
[4, 3, 5]
[9, 3, 0]
[9, 0, 3]
[1, 8, 3]
[1, 6, 5]
[6, 6, 0] # <-- SOLVED; 7 steps
DETAILS: The problem stated as-is is recoverable, and in a machine learning problem statement, we take the problem as-defined, not how it could be defined. For any # of jugs of any sizes, as long as we start with only one jug filled, the entire system is recoverable - but if more than one jugs are filled, that changes the entire problem, and can make it irrecoverable.
[0, 0, ..., X, ..., 0] <-- only one jug filled
[2, 0, ..., X-2, ..., 0]
...
[2, 4, ..., ?, ..., 7] <-- some arbitrary state
...
[0, 0, ..., X, ..., 0] <-- RECOVERED; empty all other jugs into original jug
Update: the system is also recoverable if starting with any # of jugs filled, as long as they're fully filled. They also don't necessarily have to be fully filled, but it then becomes jugsize-dependent, and no generalization w/o mathematical formulation can be made.
DEFINITIONS: OP hasn't defined "recoverable", "irrecoverable", or "ignorable" - and neither Google nor DuckDuckGo reveal much. Giving my best attempt at making sense of it, each can be defined as follows:
t0 can be restored from any other state T when starting at t0T we can get to from t0, but no longer revert to t0Irrecoverable example: [0, 1, 2] --> [0, 0, 3]. Goodbye forever, 1 liter & 2 liters.
Ignorable example: goal: two jugs empty. In this case, both the original [12, 0, 0] and the irrecoverable case [0, 1, 2] work.
I couldn't in a quick Google through the textbooks tell whether recoverability requires immediate, single-move recoverability (ctrl-Z-style) with each undo step being O(1) complexity, and which can be implementable as a sequence of moves in a push/pop stack. They always use guaranteed-single-move-undo examples (8-puzzle, Towers of Hanoi) for their recoverable examples, and always chess for their irrecoverable example.
Textbooks never describe the interesting cases :(
If our criteria for recoverability requires single-move-undo, then it's easy to think of an example where it is not recoverable in a single move:
(1,8,3) -> (0,8,4) cannot be undone in a single move (or pour).
If recovery can be multi-move, then (0,8,4 -> (some magic steps here) -> 1,8,3) gives recovery in multiple pours. However, this recovery path requires solving a path to recovery, which is sort of putting the cart before the horse: to undo a step towards solving the problem, we have to first solve the problem!
But in the example given, we can always guarantee that we can regain a previous position by doing: rightmost jug to leftmost jug; center jug to leftmost jug (thus returning to the initial condition); repeat all steps from the start until we get back to the desired recovery step. This does require that we store all moves made, though; but I think that would likely be the output of most answers anyway, so may be considered OK?
It seems intuitively obvious that we can't, through any sequence of moves, get to a position that we can't duplicate by repeating that set of moves from the initial condition. So the problem as given is recoverable, though we can't just implement it as a push/pop stack: while that's all we need for write, we need to be able to iterate it for reading.
More importantly, this makes undo an O(N+2) operation, instead of an O(1) operation. For most problems, we can just hit the reset button and replay in O(N), so we really gain nothing from doing this. Unless initial setup is prohibitively expensive for some reason, we'll be slightly more efficient if we solve it as non-recoverable, than if we kept replaying the whole thing every time we backtracked. So the problem given is not worth recovering this way.
And what if the problem stated instead: "We start with the same jugs, this time containing 9, 1.5, and 1.5 liters." Now we can never regain that initial state through any sequence of moves, so there exist jug problems which are not recoverable.
I think this makes the class of jug problems as a whole "non-recoverable", but any example we'll ever find in a textbook is likely to be "recoverable but not worth recovering", because textbooks never describe the interesting cases :(
Suppose the leftmost jug had 3 liters, the center jug had 2 liters, the right jug is empty. Suppose you poured the leftmost jug to the center jug. Now the leftmost jug is empty, and the center jug contains 5 liters. At this point you cannot go back to your original state. Consequently, your problem is irrecoverable.
In Recoverable method: 12lit. 8lit. 5lit. ( 4 , 8, 0) ( 4, 3, 5) ( 9, 3, 0) ( 1, 8, 3) ( 1, 6, 5) ( 6, 6, 0) //step 6 Splited. In step 6,you can split up the water to give away exactly 6 litres and keep 6 litres
{12,0,0}to{6,6,0}?". $\endgroup$