4

(Rich Bradshaw に感謝)

次のパズルの最適な戦略を探しています。

新しい妖精の王として、王国のカスタード湿地の地図を作成するのはあなたの義務です。
湿地は空気のような霧に覆われ、カスタードの島々が散らばっています。
各ポイントで低くまたは高く飛ぶように指示して、ピクシーを沼地に送ることができます。
ピクシーがカスタードの上に急降下すると、気が散ってシーケンスを完了できません。霧が濃いので、ピクシーが向こう側に来たかどうかしかわかりません。

コーディング用語で.. 

bool flutter( bool[size] swoop_map );

これは、指定された一連の急降下で妖精が退出したかどうかを返します。

最も簡単な方法は、1 回の急降下だけでシーケンスを渡すことです。これにより、「サイズ」試行ですべてのカスタード島が明らかになります。
カスタードの数に比例したものがいいのですが、次のようなシーケンスに問題があります。

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

このパズルの他の形式へのリンクも歓迎します。

4

2 に答える 2

2

ブライアンの最初の分割統治アルゴリズムは、次の意味で最適です: n 個の正方形と最大で k 個のカスタードを含むすべての沼地で、ブライアンのアルゴリズムよりも C 倍以上優れた最悪のケースを持たないアルゴリズムが存在する定数 C が存在します。ブライアンのアルゴリズムは、O(k log(n/k)) フライトを使用します。これは、log2(n choose k) >= log2((n/k)^k) = k オメガ( k log(n/k))。(最後のステップを厳密にするために k <= n/2 のような仮定が必要ですが、この時点で、すでに O(n) フライトの最大数に達しています。)

Brian のアルゴリズムが O(k log(n/k)) フライトのみを使用するのはなぜですか? 再帰の深さ i では、最大で min(2^i, k) 回のフライトが行われます。0 <= i <= log2(k) の合計は O(k) です。log2(k) < i <= log2(n) の合計は k (log2(n) - log2(k)) = k (log2(n/k)) です。

于 2009-05-21T19:40:50.087 に答える
2

これは私に分割統治法を考えさせます。次のようなものかもしれません (これは少し壊れた疑似コードです。fence-post エラーなどがあるかもしれません):

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
}

平易な英語では、カスタード マップの各半分でフラッターを呼び出します。いずれかの半分が false を返した場合、その半分全体にはカスタードが含まれていません。それ以外の場合、半分の半分にアルゴリズムが再帰的に適用されます。もっとうまくやれるかどうかはわかりません。ただし、沼地がほとんどカスタードである場合、このアルゴリズムはちょっと不十分です。

アイデア 2:

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

平易な英語では、カスタード マップの各要素に対してフラッターを 1 つずつ呼び出します。カスタードが見つからない場合、次の呼び出しは前の呼び出しの 2 倍の要素になります。これは二分探索に似ていますが、検索対象の項目数がわからないため一方向のみです。これがどれほど効率的かはわかりません。

于 2009-05-21T18:54:21.037 に答える