Pixies nel puzzle crema pasticcera palude

Question

(Si ringrazia Rich Bradshaw)

Sto cercando le strategie ottimali per il seguente puzzle.

Mentre il nuovo re delle fate, è il vostro dovere per mappare crema pasticcera palude del regno.
La palude è coperto in una nebbia eterea, con le isole di crema pasticcera sparsi.
È possibile inviare i folletti attraverso la palude, con le istruzioni per volare a bassa o alta in ogni punto.
Se un folletto piomba su una crema, sarà distratto e non completerà la sua sequenza. Dal momento che la nebbia è così fitta, tutto quello che sai è se un folletto ha verso l'altro lato o meno.

In termini di codifica ..

bool flutter( bool[size] swoop_map ); 

Ciò restituisce se un folletto uscito per una data sequenza di piomba.

Il modo più semplice è quello di passare in sequenze con un solo colpo solo. Che rivela tutte le isole crema di 'dimensioni' ci prova.
Preferirei qualcosa proporzionale al numero di creme - ma hanno problemi con sequenze come:

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

Collegamenti ad altre forme di questo puzzle sarebbe il benvenuto pure.

Answer 1

Questo mi fa pensare di divide et impera. Forse qualcosa di simile (questo è un po 'rotto pseudocodice Può avere errori recinzione post e simili.):

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
}

In parole povere, si chiama svolazzano su ogni metà della mappa crema pasticcera. Se qualsiasi mezzo restituisce false, che tutta la metà non ha alcuna crema pasticcera. Altrimenti, la metà della metà ha l'algoritmo ricorsivo applicata. Non sono sicuro se è possibile fare di meglio. Tuttavia, questo algoritmo è un po 'stupido se la palude è in gran parte crema pasticcera.

Idea Due:

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

In parole povere, si chiama svolazzano su ogni elemento della mappa crema pasticcera, uno alla volta. Se non trova crema pasticcera, la chiamata successiva sarà il doppio di molti elementi come la chiamata precedente. Questo è un po 'come la ricerca binaria, tranne che in una sola direzione, poiché non sa quanti articoli si sta cercando. Non ho idea di quanto efficiente questo è.

Answer 2

prima divisione di Brian e conquista algoritmo è ottimale nel senso seguente: esiste una costante C tale che su tutti acquitrini con n piazze e al massimo creme k, nessun algoritmo è un caso peggiore che è più di C volte meglio di Brian . Algoritmo di Brian utilizza O (log k (n / k)) voli, che è meno di un fattore costante le informazioni teoria limite inferiore log2 (n scegliere k)> = log2 ((n / k) ^ k) = k Omega ( log k (n / k)). (È necessario un assunto come k <= n / 2 per fare l'ultimo passo rigorosa, ma a questo punto, abbiamo già raggiunto il massimo di O n voli ()).

Perché l'uso dell'algoritmo di Brian O (log k (n / k)) i voli? Alla profondità di ricorsione i, rende al massimo min (2 ^ I, K) voli. La somma 0 <= i <= log2 (K) è O (k). La somma log2 (k) .