Contact us
 |
[email protected] |
 |
3275638434 |
 |
 |
| Paper Publishing WeChat |
Useful Links
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Article
A Non-heuristic Approach to the General Two Water Jugs Problem
Author(s)
Yiu-Kwong Man
Full-Text PDF
XML 621 Views
DOI:10.17265/1548-7709/2013.07 004
Affiliation(s)
ABSTRACT
The two water jugs problem is a famous problem in recreational mathematics, problem-solving, artificial intelligence, neuroscience, computer programming and cognitive psychology. The methods of solutions are usually based on heuristics or search methods such as BFS (breadth first search) or DFS (depth first search), which could be time and memory consuming. In this paper, we present a non-heuristic approach to solve this problem, which can be modeled by the Diophantine equation mx + ny = d, where m, n denote the capacities of the jugs and d denotes the amount of water to be determined, with 0 < m < n and 0 < d < n. By simple additions and subtractions only, the special solutions (x, y) can be found very easily by using the non-Heuristic approach, which correspond to the number of times of the water jugs being fully filled in the whole water pouring process. Also, a simple formula for determining an upper bound on the total number of pouring steps involved is derived, namely 2(m + n ¨C 2), based on the method of
linear congruence. Due to its simplicity and novelty, this approach is suitable for either hand calculation or computer programming. Some illustrative examples are provided.
KEYWORDS
Two water jugs problem, non-heuristic approach, Diophantine equation, problem-solving, artificial intelligence.
Cite this paper
References