7

While reading through some lecture notes on preliminary number theory, I came across the solution to water jug problem (with two jugs) which is summed as thus:

Using the property of the G.C.D of two numbers that GCD(a,b) is the smallest possible linear combination of a and b, and hence a certain quantity Q is only measurable by the 2 jugs, iff Q is a n*GCD(a,b), since Q=sA + tB, where:

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

And, then the method to the solution is discussed

Another model of the solution is to model the various states as a state-space search problem as often resorted to in Artificial Intelligence.

My question is: What other known methods exist which models the solution, and how? Google didn't throw up much.

4

5 回答 5

7

严格针对 2 壶问题

Q = A * x + B * y

Q = 您需要的加仑数。

注意： Q 必须是 Gcd(A,B) 的倍数，否则无解。如果 Gcd(A,B) == 1，则任何 Q 都有解。

1）方法1： 扩展欧几里得算法将比任何图算法更快地解决它。

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 这是一篇有趣的论文

于 2010-09-25T11:21:12.670 回答
4

一个惊人而有趣的方法（对于 3 个水壶）是通过重心坐标（真的！），正如总是出色的网站 Cut-the-Knot: Barycentric coordinates: A Curious Application中所描述的那样。

于 2009-03-16T18:00:06.827 回答
1

这种类型的问题通常适用于动态规划技术。我经常看到这个特定问题被用作运筹学课程中的一个例子。一个很好的分步描述在这里。

于 2009-03-15T17:03:56.000 回答
0

搜索空间方法是我所建议的。我编写了一个程序来使用 BFS 解决一般水壶问题。如果你愿意，可以发给你。

于 2009-04-11T05:36:27.600 回答
0

我在一项研究中遇到了这个问题。正如你和 st0le 在这里所说的那样，我发现扩展欧几里德算法作为问题的答案。但是这个答案并不让我满意，因为我认为这是一个定量的答案，而不是一个定性的答案（即算法没有说要采取什么步骤才能达到结果）。

我想我找到了一个不同的解决方案，它总是以最少的步骤达到结果。

这里是：

  1. 检查问题的可行性：
    • Q 是 MCD(A,B) 的倍数；
    • Q <= max(A,B)。

  2. 选择服务水壶（即您将用泵重新装满的水壶）。假设 A > B（你可以很容易地找到哪个水壶更大）：

    if(Q is multiple of B)
    return B

a_multiplier = 1
b_multiplier = 1
difference = A - B
a_multiple = A
b_multiple = B
while(|difference| differs Q)
    if b_multiple < a_multiple
        b_multiple = b_multiplier + 1
        b_multiple = b_multiplier * B
    else
        a_multiple = a_multiplier + 1
        a_multiple = a_multiplier * A

    difference = a_multiple - b_multiple

if(difference < 0)
    return B
else
    return A

  3. 开始填充过程：

    • 用泵填充服务壶（如果为空）

    • 使用服务之一填充另一个水壶

    • 检查另一个水壶是否装满，以防万一，将其倒空

    • 当较大的水壶包含 Q 时停止

在下面，您会发现该算法在 C++ 中的一个非常幼稚的实现。随意重用它，或根据需要改进它。

#include <cstdio>
#include <cstdlib>
#include <cstring>

unsigned int mcd(unsigned int a, unsigned int b) {
    // using the Euclide's algorithm to find MCD(a,b)
    unsigned int a_n = a;
    unsigned int b_n = b;
    while(b_n != 0) {
        unsigned int a_n1 = b_n;
        b_n = a_n % b_n; 
        a_n = a_n1;
    }
    return a_n;
}

unsigned int max(unsigned int a, unsigned int b) {
    return a < b ? b : a;
}

unsigned int min(unsigned int a, unsigned int b) {
    return a > b ? b : a;
}

void getServiceJugIndex(unsigned int capacities[2], unsigned int targetQty, unsigned int &index) {
    unsigned int biggerIndex = capacities[0] < capacities[1] ? 1 : 0;
    unsigned int smallerIndex = 1 - biggerIndex;
    if(targetQty % capacities[smallerIndex] == 0) {
        // targetQty is a multiple of the smaller jug, so it's convenient to use this one
        // as 'service' jug
        index = smallerIndex;
        return;
    }

    unsigned int multiples[2] = {capacities[0], capacities[1]};
    unsigned int multipliers[2] = {1, 1};
    int currentDifference = capacities[0] - capacities[1];
    while(abs(currentDifference) != targetQty) {
        if(multiples[smallerIndex] < multiples[biggerIndex])
            multiples[smallerIndex] = capacities[smallerIndex] * ++multipliers[smallerIndex];
        else
            multiples[biggerIndex] = capacities[biggerIndex] * ++multipliers[biggerIndex];

        currentDifference = multiples[biggerIndex] - multiples[smallerIndex];
    }

    index = currentDifference < 0 ? smallerIndex : biggerIndex;
}

void print_step(const char *message, unsigned int capacities[2], unsigned int fillings[2]) {
    printf("%s\n\n", message);
    for(unsigned int i = max(capacities[0], capacities[1]); i > 0; i--) {
        if(i <= capacities[0]) {
            char filling[9];
            if(i <= fillings[0])
                strcpy(filling, "|=====| ");
            else
                strcpy(filling, "|     | ");
            printf("%s", filling);
        } else {
            printf("        ");
        }
        if(i <= capacities[1]) {
            char filling[8];
            if(i <= fillings[1])
                strcpy(filling, "|=====|");
            else
                strcpy(filling, "|     |");
            printf("%s", filling);
        } else {
            printf("       ");
        }
        printf("\n");
    }
    printf("------- -------\n\n");
}

void twoJugsResolutor(unsigned int capacities[2], unsigned int targetQty) {
    if(capacities[0] == 0 && capacities[1] == 0) {
        printf("ERROR: Both jugs have 0 l capacity.\n");
        return;
    }
    // 1. check feasibility
    //  1.1. calculate MCD and verify targetQty is reachable
    unsigned int mcd = ::mcd(capacities[0], capacities[1]);
    if ( targetQty % mcd != 0 ||
    //  1.2. verify that targetQty is not more than max capacity of the biggest jug
            targetQty > max(capacities[0], capacities[1])) {
        printf("The target quantity is not reachable with the available jugs\n");
        return;
    }
    // 2. choose 'service' jug
    unsigned int serviceJugIndex;
    getServiceJugIndex(capacities, targetQty, serviceJugIndex);
    unsigned int otherJugIndex = 1 - serviceJugIndex;
    unsigned int finalJugIndex = capacities[0] > capacities[1] ? 0 : 1;
    // 3. start fill process
    unsigned int currentFilling[2] = {0, 0};
    while(currentFilling[finalJugIndex] != targetQty) {
        // 3.1 fill with the pump the service jug (if needed)
        if(currentFilling[serviceJugIndex] == 0) {
            currentFilling[serviceJugIndex] = capacities[serviceJugIndex];
            print_step("Filling with the pump the service jug", capacities, currentFilling);
        }

        // 3.2 fill the other jug using the service one
        unsigned int thisTimeFill = min(currentFilling[serviceJugIndex], capacities[otherJugIndex] - currentFilling[otherJugIndex]);
        currentFilling[otherJugIndex] += thisTimeFill;
        currentFilling[serviceJugIndex] -= thisTimeFill;
        print_step("Filling the other jug using the service one", capacities, currentFilling);
        // 3.3 check fullness of the other jug and, in case, empty it
        if(currentFilling[otherJugIndex] == capacities[otherJugIndex]) {
            currentFilling[otherJugIndex] = 0;
            print_step("Empty the full jug", capacities, currentFilling);
        }
    }
    printf("Done\n");
}

int main (int argc, char** argv) {
    if(argc < 4)
        return -1;
    unsigned int jugs[] = {atoi(argv[1]), atoi(argv[2])};
    unsigned int qty = atoi(argv[3]);

    twoJugsResolutor(jugs, qty);
}

我不知道我描述的过程背后是否有任何数学概念来选择正确的水壶以最小化所需步骤的数量，我将其用作启发式。

我希望这可以帮助你。

于 2015-09-17T12:55:22.320 回答