解决水壶问题

在阅读关于初步数理论的一些讲义时,我遇到了水壶问题的解决方案(有两个水壶),总结如下:

使用两个数字的GCD的属性,GCD(a,b)是a和b的最小可能线性组合,因此一定量Q仅可由2个jug测量,iff Q是*GCD(a, b),因为Q = sA + tB,其中:

n = a positive integer
A = capacity of jug A
B=  capacity of jug B

然后,讨论了解决方案的方法

该解决方案的另一个模型是将各种状态建模为状态空间搜索问题,这在人工智能中经常使用.

我的问题是:存在哪些其他已知方法可以为解决方案建模,以及如何？谷歌并没有呕吐太多.

严格的2 Jug问题

Q = A * x + B * y

Q =你需要的加仑.

注意: Q必须是Gcd(A,B)的倍数,否则没有解决方案.如果Gcd(A,B)== 1,有任何Q的解决方案.

1)方法1: 扩展的Euclid算法将比任何图算法更快地解决它.

2)方法2: 这是一个天真的方法.(注意,这可以抛出2个解决方案,你必须选择哪个更短)

有问题可以简单地通过repeatedly填充从一个桶A到另一个桶B(顺序无关紧要)直到它填满你想要的数量来解决... ofcoz,当桶装满时,你将其清空并继续.

    A = 3, B = 4 and Q = 2

反复填充A-> B.

    A B
   ######
    0 0
    4 0
    1 3
    1 0
    0 1
    4 1
    2 3 <-Solution

让我们试着观察如果我们走另一条路会发生什么,填充B-> A.

A  B
#####
0  0
0  3
3  0
3  3
4  2 <- Solution

在这种情况下,填充B-> A使我们的目标状态比A-> B更快

Generic N Jugs 这是一篇有趣的论文