4

（感谢 Rich Bradshaw）

我正在为以下难题寻找最佳策略。

作为新的仙王，你有责任绘制王国的奶油沼泽地图。
沼泽笼罩在飘渺的薄雾中，蛋奶沙司散落在各处。
您可以将您的小精灵送过沼泽，并附有在每个点低飞或高飞的指示。
如果小精灵从蛋奶冻上俯冲下来，它会分心，不会完成它的序列。由于雾气很浓，你只知道小精灵是否到达了另一边。

在编码方面.. 

bool flutter( bool[size] swoop_map );

这将返回小精灵是否退出给定的猛扑序列。

最简单的方法是一次性传递序列。这揭示了“大小”尝试中的所有蛋奶冻岛。
我更喜欢与蛋奶冻的数量成比例的东西 - 但在序列方面存在问题，例如：

     C......C     (that is, custards at beginning and end)

也欢迎链接到这个谜题的其他形式。

4

2 回答 2

2

这让我想到了分而治之。也许是这样的（这是稍微损坏的伪代码。它可能有栅栏错误等）：

retval[size] check()
{
   bool[size] retval = ALLFALSE;
   bool[size] flut1 = ALLFALSE;
   bool[size] flut2 = ALLFALSE;
   for (int i = 0; i < size/2; ++i) flut1[i] = TRUE;
   for (int i = size/2; i < size; ++i) flut2[i] = TRUE;
   if (flutter(flut1)) retval[0..size/2] = <recurse>check
   if (flutter(flut2)) retval[size/2..size] = <recurse>check
}

用简单的英语来说，它在 custard 地图的每一半上调用颤振。如果任何一半返回 false，则整个一半没有奶油冻。否则，一半的一半具有递归应用的算法。我不确定是否可以做得更好。然而，如果沼泽大部分是奶油冻，这个算法就有点蹩脚了。

想法二：

int itsize = 1
bool[size] retval = ALLFALSE;
for (int pos = 0; pos < size;)
{
    bool[size] nextval = ALLFALSE;
    for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) nextval[pos2] = true;
    bool flut = flutter(nextval)
    if (!flut || itsize == 1)
    {
        for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) retval[pos2] = flut;
        pos+=itsize;
    }
    if (flut) itsize = 1;
    if (!flut) itsize*=2;
}

用简单的英语，它在 custard map 的每个元素上调用颤振，一次一个。如果它没有找到 custard，下一次调用的元素数量将是上一次调用的两倍。这有点像二分搜索，除了只在一个方向上，因为它不知道它正在搜索多少个项目。我不知道这有多有效。

于 2009-05-21T18:54:21.037 回答
2

Brian 的第一个分治算法在以下意义上是最优的：存在一个常数 C，使得在所有具有 n 个正方形和最多 k 个蛋羹的沼泽中，没有算法的最坏情况比 Brian 的好 C 倍。Brian 的算法使用 O(k log(n/k)) 次飞行，它在 log2(n choose k) >= log2((n/k)^k) = k Omega( k 对数（n/k））。（你需要一个像 k <= n/2 这样的假设来使最后一步变得严格，但是在这一点上，我们已经达到了 O(n) 次飞行的最大值。）

为什么布赖恩的算法只使用 O(k log(n/k)) 航班？在递归深度 i，它最多进行 min(2^i, k) 次飞行。0 <= i <= log2(k) 的总和是 O(k)。log2(k) < i <= log2(n) 的总和是 k (log2(n) - log2(k)) = k (log2(n/k))。

于 2009-05-21T19:40:50.087 回答