Пикси в головоломке "Заварное болото"

Question

(С благодарностью Ричу Брэдшоу)

Я ищу оптимальные стратегии для следующей головоломки.

Как новый король фей, вы обязаны нанести на карту заварное болото королевства.
Болото покрыто воздушным туманом, повсюду разбросаны островки заварного крема.
Вы можете отправить своих пикси через болото с инструкциями летать низко или высоко в каждой точке.
Если пикси спикирует на заварной крем, он будет отвлечен и не завершит свою последовательность.Поскольку туман такой густой, все, что вы знаете, это добрался ли пикси на другую сторону или нет.

В терминах кодирования..

bool flutter( bool[size] swoop_map ); 

Это возвращает, вышел ли пикси для данной последовательности налетов.

Самый простой способ - проходить последовательно только одним махом.Это показывает все островки заварного крема в пробах "размер".
Я бы предпочел что-нибудь пропорциональное количеству заварных кремов, но у меня проблемы с такими последовательностями, как:

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

Ссылки на другие формы этой головоломки также приветствовались бы.

Answer 1

Это наводит меня на мысль о разделяй и властвуй.Может быть, что-то вроде этого (это слегка нарушенный псевдокод.В нем могут быть ошибки столба ограждения и тому подобное):

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 для каждого элемента карты custard, по одному за раз.Если он не найдет custard, следующий вызов будет выполняться для вдвое большего числа элементов, чем предыдущий вызов.Это похоже на бинарный поиск, за исключением того, что только в одном направлении, поскольку он не знает, сколько элементов он ищет.Я понятия не имею, насколько это эффективно.

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) пролетов.)

Почему алгоритм Брайана использует только O(k log(n / k)) рейсов?При глубине рекурсии i он совершает не более min(2^i, k) пролетов.Сумма для 0 <= я <= log2(k) равно O(k).Сумма для log2(k) < i <= log2(n) равно k (log2(n) - log2(k)) = k (log2(n/k)).