Pixies im Vanillesoße Sumpf Puzzle

Question

(Mit Dank Rich Bradshaw)

Ich suche nach optimalen Strategien für das folgende Rätsel.

Als neuer Fee König, es ist Ihre Pflicht, das Reich des Vanillesoße Sumpf zu kartieren.
Der Sumpf wird in einem etherischen Nebel bedeckt, mit Inseln Vanillesoße verstreut.
Sie können Ihre Pixies durch den Sumpf, mit Anweisungen zu fliegen niedrig oder hoch an jedem Punkt senden.
Wenn ein Elf über einen Pudding stürzt nach unten, wird es abgelenkt und wird nicht seine Sequenz abzuschließen. Da der Nebel so dick ist, alles, was Sie wissen, ob eine Elf auf der anderen Seite bekam oder nicht.

Bei der Codierung Begriffe ..

bool flutter( bool[size] swoop_map ); 

Das gibt, ob ein Elf für eine gegebene Folge von swoops verlassen.

Der einfachste Weg ist in Sequenzen mit nur einem Schlag zu übergeben. Das zeigt alle Vanillesoße Inseln in ‚Größe‘ versucht.
Ich würde eher proportional etwas zu der Anzahl der Puddings - aber haben Probleme mit Sequenzen wie:

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

Links zu anderen Formen dieses Puzzle wären auch willkommen.

Answer 1

Das macht mich denken teile und herrsche. Vielleicht so etwas wie (dieser Pseudo-Code leicht gebrochen Es kann Zaun-post-Fehler und dergleichen hat.):

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
}

Im Klartext, nennt es flattert auf jeder Hälfte der Vanillesoße Karte. Wenn jede Hälfte false zurückgibt, hat die ganze Hälfte keine Vanillesoße. Andernfalls wird die Hälfte der Hälfte hat der Algorithmus rekursiv angewendet. Ich bin mir nicht sicher, ob es möglich ist, es besser zu machen. Doch dieser Algorithmus irgendwie lahm ist, wenn der Sumpf meist Vanillesoße ist.

Idee zwei:

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

Im Klartext, ruft es flattern auf jedes Element der Vanillesoße Karte, einer nach dem anderen. Wenn es nicht Vanillesoße findet, wird der nächste Anruf auf doppelt so viele Elemente wie die vorherigen Anruf. Dies ist eine Art, wie binäre Suche, mit der Ausnahme nur in einer Richtung, da sie nicht weiß, wie viele Elemente es sucht. Ich habe keine Ahnung, wie effizient das ist.

Answer 2

Brians erste Teile und Herrsche-Algorithmus sind in folgendem Sinne optimal: es existiert eine Konstante C, so dass über alle Sümpfe mit n- Plätzen und höchstens k Puddings, kein Algorithmus eine Worst-Case hat, die mehr als C-mal besser als Brians ist . Brians Algorithmus verwendet O (k log (n / k)) Flüge, die in einem konstanten Faktor ist die informationstheoretische Niederstwertprinzip log2 gebunden (n wählen k)> = log2 ((n / k) ^ k) = k Omega ( k log (n / k)). (Sie benötigen eine Annahme wie k <= n / 2 der letzte Schritt rigoros zu machen, aber zu diesem Zeitpunkt haben wir bereits erreicht das Maximum von O (n) Flüge.)

Warum Brian Algorithmus Verwendung nur O (k log (n / k)) Flüge? Bei Rekursionstiefe i, macht es höchstens min (2 ^ i, k) Flüge. Die Summe für 0 <= i <= log2 (k) O (k). Die Summe für log2 (k) .