小蛋糕奶蛋糊沼澤拼圖

我正在尋找最佳的策略爲下面的謎題。

作爲新的仙女王，你有責任繪製王國的乳蛋糕沼澤。
沼澤覆蓋在空靈的薄霧中，散佈着各種各樣的乳蛋糕。
你可以在沼澤中發送你的小精靈，指示在每個點上飛低或高。
如果一個小精靈在蛋撻上猛撲過來，它會分心並且不會完成它的序列。由於霧太濃，所以你知道的是小精靈是否到達另一邊。

在編碼方面..

bool flutter(bool[size] swoop_map);

這將返回一個精靈是否爲退出俯衝給定的順序。

最簡單的方法是隻傳遞一次序列。這揭示了「大小」嘗試的所有奶油島。
我寧願什麼成正比，蛋奶的數量 - 但有樣序列問題：

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

鏈接到其他形式的這個難題將受到歡迎，以及。

來源

2009-05-21 caffiend

這些架次是自適應還是非自適應？也就是說，後期小精靈的飛行計劃能否取決於早期的結果？另外，你可以期望的最低點是log_2（size）來找到一個奶油蛋糕。 – Dave 2009-05-21 19:00:14

是的，如果可以減少總數，鼓勵適應性的架次。 – caffiend 2009-05-21 19:11:30

這讓我想到分而治之。也許這樣的事情（這是略微沙啞的僞代碼可能有柵欄後的錯誤等。）：

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

用簡單的英語，它的蛋奶地圖，一次一個的每個元素調用撲。如果它沒有找到奶油蛋糕，下一次調用將會是前一次調用的兩倍。這有點像二分搜索，除了在一個方向上，因爲它不知道它正在搜索多少項目。我不知道這是多高效。

來源

2009-05-21 18:54:21 Brian

布賴恩的第一個分治法在以下意義上是最優的：存在一個常數C，使得在n個平方和最多k個蛋格的所有沼澤中，沒有算法的最壞情況比C好多於C倍Brian的。 Brian的算法使用O（k log（n/k））飛行，其在常數因子log2（n選擇k）= log2（（n/k）^ k）= k歐米茄的信息論下界內k log（n/k））。（你需要像k < = n/2這樣的假設來使最後一步嚴格，但是在這一點上，我們已經達到了O（n）次航班的最大值。）

爲什麼Brian的算法只使用O （k日誌（n/k））航班？在遞歸深度i，它至多使得最小（2^i，k）航班。 0的總和爲0（k）。 log2（k）<的總和爲log2（n）= log2

來源

2009-05-21 19:40:50 Dave

小蛋糕奶蛋糊沼澤拼圖

回答

相關問題