奶油冻沼泽拼图中的精灵

Question

(感谢Rich Bradshaw)

我正在为下面的难题寻找最优的策略。

作为新的仙女之王，你的职责就是绘制王国的奶油沼泽地图。

沼泽笼罩在虚幻的薄雾中，各处散布着奶油色的小岛。

你可以把你的小精灵送过沼泽，在每个点上指示飞得低或高。

如果一个小精灵扑到一块奶油冻上，它就会分心，无法完成它的序列。既然雾这么浓，你所知道的就是一个小精灵有没有走到对岸。

在编码术语中..

bool flutter( bool[size] swoop_map ); 

此函数返回给定的突袭序列中是否存在一个pixie。

最简单的方法是只需一次动作就可以在序列中传递。它显示了所有“大小”尝试的奶油蛋冻岛。

我更喜欢与custard的数量成正比的东西-但在序列方面有问题，比如：

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

链接到其他形式的这个难题也是受欢迎的。

Answer 1

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

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
}

在简单的英语中，它在蛋黄地图的每一半上调用flutter。如果任何一半返回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;
}

简单地说，它在奶油冻映射的每个元素上调用flutter，一次调用一个。如果找不到乳酪，则下一次调用的元素数量将是前一次调用的两倍。这有点像二进制搜索，除了只在一个方向上，因为它不知道它正在搜索多少项。我不知道这有多有效。

Answer 2

布赖恩的第一个分治算法在以下意义上是最优的:存在一个常数C，使得在所有有n个正方形和至多k个立方体的沼泽上，没有一个算法的最坏情况比布赖恩的算法好C倍以上。布赖恩的算法使用O(k log(n/ k) )次飞行，这是log2(n选择k) >= log2((n/k)^k) =k Omega(k log(n/k))的信息论下界的常数因子。(您需要像k <= n/2这样的假设才能使最后一步变得严格，但在这一点上，我们已经达到了O(n)次飞行的最大值。)

为什么Brian的算法只使用O(k (n/k))次飞行？在递归深度为i时，它至多执行min(2^i，k)次飞行。0 <= i <= log2(k)的和是O(k)。log2(k)