我正在尝试解决著名的“水壶之谜”(就像电影中的Die Hard with a Vengeance)。
我很容易解决的难题与支持 2 壶在 C #。
但是现在我想用 N 个壶(2,3,4,5,...)实现相同的效果。它完全改变了算法的工作方式。
我目前的解决方案的工作原理如下:
将 m 升的水壶装满,然后将其倒入 n 升的水壶中。
每当 m 升壶变空时,就把它装满。
每当 n 升壶变满时,它就会变空。
重复步骤 1,2,3,直到 n 升壶或 m 升壶包含 d 升水。
然后,我通过颠倒水罐的顺序来重复操作,并在两者之间采用最快的解决方案。
该系统适用于 2 壶,但不能与更多的壶工作。
规则提示:您有 N 壶水,每个都有特定的容量。可以从水龙头完全装满一个壶,将一个壶完全倒入水槽中,然后将一个壶中的内容物转移到另一个壶中(取决于目标的可用容量和当前源的填充量)。
我们的目标是得到一个水壶与一定量的水(目标),并找到最快的方法来做到这一点。
例如:两个 3 升和 5 升的壶表示为 int [3,5] 的数组。目标是有一个带有 4 的壶 (用 int 表示)。该函数将这两个元素作为参数,并显示最快的路径 (如果有的话)。
到达那里的方法是(在这种情况下的 6 个步骤):(0,5)(3,2)(0,2)(2,0)(2,5)(3,4)
如前所述,我很容易地用 2 个 jugs 解决了这个简单的版本。但是如何用 N 个 jugs 做到这一点?有没有人做过类似的事情?或者有一个想
唯一精确的操作是
填充:从无限的供水中完全填充任何水罐。
空:完全清空任何壶的内容。
POUR:将 jugA的内容物倒入 jugB中,直到 jugB满或 jugA为空。
这些操作分别执行:
amount[A] = capacity[A];
amount[A] = 0;
temp = min(available(B),amount[A]);amount[B] += temp;amount[A]-= temp;
有了这个特殊的便利功能:available(i) => capacity[i] - amount[i]
从这些相对较少的可用操作中执行breadth first search,直到其中一个水壶中存在所需的水量。
操作 1 和 2 有 N 个索引选择(FILL 或 EMPTY),操作 3(POUR)有(N * N-1)个选择,换句话说,选择一个随机 A 和一个不等于 A 的随机 B。
优化注意事项
一个有用的优化是防止将已经被认为可以用更少的步骤到达的搜索状态排队。这里的state乍一看是由amount数组中的值表示的,但也可以由每个唯一容量和数量的水罐数量表示,因为除了容量和当前数量之外,水罐本身并不是唯一的。
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(33条)