Пазл в заварной крем болото - PullRequest
Новая
       32

Пазл в заварной крем болото

3 голосов
/ 21 мая 2009

(благодаря Ричу Брэдшоу)

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

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

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

bool flutter( bool[size] swoop_map );

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

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

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

Также приветствуются ссылки на другие формы этой головоломки.

Ответы [ 2 ]

2 голосов
/ 21 мая 2009

Первый алгоритм Брайана «разделяй и властвуй» является оптимальным в следующем смысле: существует постоянная C, такая, что на всех болотах с n квадратами и не более k заварных кремов ни один алгоритм не имеет худшего случая, который был бы более чем в C раз лучше, чем Брайан , Алгоритм Брайана использует O (k log (n / k)) полетов, что находится в пределах постоянного коэффициента в теоретико-информационной нижней границе log2 (n выберите k)> = log2 ((n / k) ^ k) = k Omega ( k log (н / к)). (Вам нужно предположение типа k <= n / 2, чтобы сделать последний шаг строгим, но на данный момент мы уже достигли максимума O (n) полетов.) </p>

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

2 голосов
/ 21 мая 2009

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

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
}

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

Идея вторая: 

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;
}

На простом английском языке он вызывает флаттер на каждом элементе карты заварного крема, по одному за раз. Если это не находит заварной крем, следующий вызов будет на вдвое больше элементов, чем предыдущий вызов. Это похоже на бинарный поиск, за исключением только в одном направлении, поскольку он не знает, сколько элементов он ищет. Я понятия не имею, насколько это эффективно.

...