如何确定3个水壶问题中的可达状态？

问题描述 投票：0回答：1

考虑 3 个水壶 1、2、3，容量分别为 12、8、5。 3 个水壶的总水量应为 12 个单位。我们可以将罐 x 清空到罐 y (xEy) 中，或者从罐 x (xFy) 中填充罐 y。考虑到这些因素，给定起始状态和目标状态，我们如何在不实际执行算法的情况下判断目标状态是否可以在有限步骤中达到？

方程 x+y+z = 12 有 53 个解，即 2756 对可能的起始状态和目标状态。单独检查所有这些对的可达性，即使在计算机上也是疯狂的，就像目标状态 (0,7,5) 有 12 个可达的起始状态。或者说我还没有想到好的算法。不管怎样，这个数字太大了，我想要一些“经验法则”来识别可达状态。任何帮助或想法将不胜感激。

algorithm search artificial-intelligence number-theory diophantine
1个回答
0
投票

让我们用这个小数据结构（一个由 3 个整数组成的数组）唯一地将水罐状态标识为所有 3 个水罐中的水量。对于本练习，我将使用 C/C++ 进行编码，但它可以轻松移植到任何编程语言。

struct JugState
{
    int jugs[3];
};

例如，如果第一个水壶有 4 个单位的水，第二个水壶有 5 个单位的水，第三个水壶有 3 个单位的水。那么我们可以有一个上面的 JugState 

{4,5,3}
。

但是考虑到水壶的固定容量分别为 12、8 和 5。我们可以轻松地得到壶状态的整数表示。上面的 {4,5,3} 配置可以很容易地用数字 

453
来表示。 
{11,0,1}
的罐子配置可以表示为 
1101
。它不一定是十进制编码，但它使调试更容易。

我们可以拥有从 JugState 转换为“jug 状态索引”的辅助函数。

int getIndexFromJugState(const JugState& jugState)
{
    return jugState.jugs[0] * 100 + jugState.jugs[1] * 10 + jugState.jugs[2];
}

JugState getJugStateFromIndex(int index)
{
    int jug2 = index % 10;
    index = index / 10;

    int jug1 = index % 10;
    index = index / 10;

    int jug0 = index;
    return { jug0, jug1, jug2};
}

现在我们可以定义一个在 JugState 内移动水的函数，仅使用该函数知道每个壶的 12,8 和 5 单位容量。它采用初始“壶状态索引”作为参数，以及两个参数来指示水从何处移动（例如壶状态的 0,1,2 索引）

int moveWater(int index, int srcJug, int dstJug)
{
    if (srcJug == dstJug)
    {
        return index;
    }

    JugState js = getJugStateFromIndex(index);

    // how much water is in the source jug
    int sourceAmount = js.jugs[srcJug];

    // how much water is in the destination jug
    int dstAmount = js.jugs[dstJug];

    // how much more water can the destination jug take
    int maxTransfer = (dstJug == 0) ? 12 : ((dstJug == 1) ? 8 : 5) - dstAmount;

    // how much to actually move
    int transfer = (sourceAmount >= maxTransfer) ? maxTransfer : sourceAmount;

    js.jugs[srcJug] -= transfer;
    js.jugs[dstJug] += transfer;

    return getIndexFromJugState(js);
}

现在我们可以把这个问题看成一个图。给定任何状态，例如 

{4,5,3}
（索引 == 453），我们想要测试是否可以转换到 
{7,1,4}
（索引 == 714）。在任何给定状态下，可以进行 6 种有效转换。 （即从 jug0->jug1、jug0->jug2、...、jug2->jug0 移水）。因此，我们可以使用 
set
来跟踪我们访问过的节点索引，这样我们就不会无限递归。这种树遍历的最酷的部分是我们不需要构建一棵实际的树。

bool canTransitionExist(int startIndex, int endIndex, unordered_set<int>& visited)
{
    if (startIndex == endIndex)
    {
        return true;
    }

    // visit the start state
    visited.insert(startIndex);

    // there's 6 possible candidate states to transition to
    int candidates[6];
    candidates[0] = moveWater(startIndex, 0, 1);
    candidates[1] = moveWater(startIndex, 0, 2);
    candidates[2] = moveWater(startIndex, 1, 0);
    candidates[3] = moveWater(startIndex, 1, 2);
    candidates[4] = moveWater(startIndex, 2, 0);
    candidates[5] = moveWater(startIndex, 2, 1);

    // let's try visiting each one of these if we haven't visited before
    for (int i = 0; i < 6; i++)
    {
        // don't visit nodes we've seen before
        if (visited.count(candidates[i]) == 0)
        {
            bool result = canTransitionExist(candidates[i], endIndex, visited);
            if (result)
            {
                return true;
            }
        }
    }
    return false;
}

bool canTransitionExist(int startIndex, int endIndex)
{
    std::unordered_set<int> visited;
    return canTransitionExist(startIndex, endIndex, visited);
}

现在我们来介绍2个辅助函数。一个函数可以帮助我们用 12 个单位的水建立 53 个有效水罐状态的初始集合。此功能了解罐子的 12/8/5 限制。但您可以将任何您想要的目标状态金额传递给它。

void getValidJugStates(int targetAmount, vector<int>& validStates)
{
    for (int i = 0; i <= 12; i++)
    {
        for (int j = 0; j <= 8; j++)
        {
            for (int k = 0; k <= 5; k++)
            {
                if ((i + j + k) == targetAmount)
                {
                    JugState js = { i,j,k };
                    validStates.push_back(getIndexFromJugState(js));
                }
            }
        }
    }
}

以及一个辅助函数，用于制作水罐状态的字符串表示：

std::string getStringFromIndex(int index)
{
    auto js = getJugStateFromIndex(index);
    std::string s = "{";
    s += std::to_string(js.jugs[0]) + "," + std::to_string(js.jugs[1]) +  "," + std::to_string(js.jugs[2]);
    s += "}";
    return s;
}

现在我们有足够的能力为 12 种水配置单位的所有 2756 种转换组合编写测试代码。

int main()
{
    vector<int> validStates;

    const int capacityAmount = 12;
    getValidJugStates(capacityAmount, validStates);

    std::cout << "there are: " << validStates.size() << " initial starting states of jugs with " << capacityAmount << " units total\n";

    size_t testIndex = 0;

    for (size_t i = 0; i < validStates.size(); i++)
    {
        for (size_t j = 0; j < validStates.size(); j++)
        {
            if (i == j)
            {
                continue;
            }

            int start = validStates[i];
            int end = validStates[j];

            bool success = canTransitionExist(start, end);

            std::cout << "Test number " << testIndex << ": ";
            testIndex++;

            if (success)
            {
                std::cout << "valid path from " << getStringFromIndex(start) << " to " << getStringFromIndex(end) << endl;
            }
            else
            {
                std::cout << "there is not a path from " << getStringFromIndex(start) << " to " << getStringFromIndex(end) << endl;
            }
        }
    }

    return 0;
}

运行我们的代码（这是一个片段）...

...
...
Test number 1968: there is not a path from {7,5,0} to {9,2,1}
Test number 1969: valid path from {7,5,0} to {9,3,0}
Test number 1970: valid path from {7,5,0} to {10,0,2}
Test number 1971: there is not a path from {7,5,0} to {10,1,1}
Test number 1972: valid path from {7,5,0} to {10,2,0}
Test number 1973: valid path from {7,5,0} to {11,0,1}
Test number 1974: valid path from {7,5,0} to {11,1,0}
Test number 1975: valid path from {7,5,0} to {12,0,0}
Test number 1976: valid path from {8,0,4} to {0,7,5}
Test number 1977: valid path from {8,0,4} to {0,8,4}
Test number 1978: valid path from {8,0,4} to {1,6,5}
Test number 1979: there is not a path from {8,0,4} to {1,7,4}
Test number 1980: valid path from {8,0,4} to {1,8,3}
Test number 1981: valid path from {8,0,4} to {2,5,5}
Test number 1982: there is not a path from {8,0,4} to {2,6,4}
Test number 1983: there is not a path from {8,0,4} to {2,7,3}
...
...

您可以在此处获取完整列表：

https://github.com/jselbie/ Threejugproblem/blob/main/main.cpp

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.