algorithm - 3つの卵の問題

Question

私はちょうど2つの卵の問題を読んでいました：

二卵問題

2つの卵が与えられ、100階建ての建物にアクセスできます。両方の卵は同一です。目的は、その階から窓から落としたときに卵が壊れない最上階を見つけることです。卵を落としても壊れない場合は、損傷はなく、再び落とすことができます。しかし、卵が壊れたら、それでその卵は終わりです。

卵が床から落とされたときに壊れた場合n、それはその上のどの床からも壊れたでしょう。卵が落下を生き残るならば、それはそれより短いどんな落下も生き残るでしょう。

問題は、解決策を見つけるために必要な卵滴の数を最小限に抑えるために、どのような戦略を採用する必要があるかということです。。（そして、それが取るドロップの数の最悪のケースは何ですか？）

私は「私が3つできることを見てください」セクションまで続いていました。著者は、最初の卵が壊れた後、それは2卵の問題に分解され、再帰的に解決できると述べています。

それは素晴らしいことですが、2個（最初の卵）ではなく3個の卵を使用する場合は、より大きなステップサイズを選択したいと思いませんか？どの階から最初の卵を投げますか？

卵が1つある場合は、1階から開始する必要があります。
卵が2つある場合は、を解いてn(n+1)/2=k切り上げます。ここnで、は開始階であり、kは階数です。
3で...私は式を思い付くのに苦労しています。

---

これについてもう少し考えてみると、卵が2つある場合、ドロップの最大数は、最初の卵をドロップするフロア数と同じになります。たとえば、2つの卵と100のフロアがある場合、ソリューションは14です。つまり、最初の卵を14階からドロップし、壊れた場合は、1〜13階でさらに13回ドロップする必要があります。

卵が3個の場合、解は9個になります（グラフに示されているように）。ただし、最初の卵を9階に投げたくはありません。その間に1を繰り返す必要がないため、より高く投げることができます。

14階から再び投げて、それが壊れた場合、私たちは再発します。n(n+1)/2=kここkで現在13です...しかし、それは4.815になります。これを天井にして前のドロップを追加すると、実際のソリューションよりも低い6が得られるため、ここで何かが間違っています...

---

Answer 1

14階から再び投げて、それが壊れた場合、私たちは再発します。n（n + 1）/ 2 = kここで、kは13になります...しかし、これで4.815が得られます。これを天井にして前のドロップを追加すると、6が得られます。これは、実際の解よりも低いため、次のようになります。間違い...

壊れない場合はどうなりますか？次に、86階の3卵の問題があります。これは、100階の問題よりも解決に1滴少ない可能性があります。

^50階から最初の卵を落としたとしましょう。それが壊れた場合、49階で2卵の問題が発生し、最大10滴の追加が必要になります。つまり、最悪の場合は11滴になります（壊れない場合は、50階建ての3個の卵の問題で最大7滴の追加が必要になるため）。

^{最初のドロップに37}階を選択した場合、それが壊れた場合は、36階の2卵の問題が発生し、最大8つの追加のドロップが必要になります。壊れない場合は、63階建ての3個の卵の問題が残っています。この問題を最大8滴で解決したいので、次の液滴が卵を割った場合、残りの2卵の問題は、最大7滴で解決できるはずです。したがって、2番目の液滴に選択できる最高階はです37 + 28 + 1 = 66。 28階は、最大7滴と2個の卵で解決できる最高の階です。卵が壊れない場合は、34階建ての3卵の問題があり、残り7滴です。卵割が21（6 * 7/2）の場合、残りの6滴で確実に解決できる最高値なので、フロアを選択できます66 + 21 + 1 = 88。卵が壊れない場合は、12階に6滴が残っていますが、これは2つの卵だけですでに実行可能です。

体系的に、あなたが確かにd滴とe卵で解決できる床の最大数は

          / 1, if d == 1
F(e,d) = |  d, if e == 1
          \ F(e-1,d-1) + 1 + F(e,d-1), if e > 1 and d > 1

一滴しかない場合は、卵が割れないことをまだ知らない最下階を選ぶしかない。それが壊れて、あなたがより高い階を試したなら、あなたは卵を壊すために1階を知りません。

卵が1つしかない場合は、卵が割れるまで、または滴がなくなるまで、すべてのフロアを順番にチェックする必要があります。

そうしないと、最初のドロップがより高いフロアからのものF(e-1,d-1) + 1である場合、卵が壊れたときに最初のブレークフロアを見つけることができない可能性があります。d-1最初のドロップが下の階からのものである場合、卵が壊れなければドロップでそれほど高く到達することはできないので、最初のドロップは床からのものでなければなりませんF(e-1,d-1) + 1。それが壊れた場合、あなたは仮定によって残りのe-1卵とd-1滴で解決することができます。F(e,d-1)そうでない場合は、残りの滴と卵で次の階を解決することができます。

逆に、卵のあるf床に必要な滴の数を見つけるには、見つける必要がありますe

D(e,f) = min { d | F(e,d) >= f }

F(e,d)行列を計算することでそれを見つけることができます。または、動的計画法を使用することもできます。

最初の一滴に床を選択sした場合、卵が壊れた場合D(e-1,s-1)、床を決定するために最大で滴が必要です。卵が壊れない場合はD(e,f-s)、床を決定するために最大でドロップする必要があります。sしたがって、最初のドロップのフロアを選択するための最悪のケースは

WC(s,e,f) = 1 + max { D(e-1,s-1), D(e,f-s) }

最悪の場合の最良のものは

D(e,f) = minimum { WC(s,e,f) | 1 <= s <= f }

（もちろんどこでD(e,0) = 0）。

Answer 2

この問題は、次の3つのアプローチ（私が知っている）で解決できます。

1. 動的計画法
2. 二分探索木を使用したソリューション
3. 与えられた数の卵と与えられた数の滴でテストまたはカバーできる床の最大数の直接数式を取得することによる解決策

まず、いくつかのシンボルを次のように定義します。

e = number of eggs
f = number of floors in building
n = number of egg drops 
Fmax(e, n) = maximum number of floors that can be tested with e eggs and n drops

動的計画法アプローチの核心は、Fmaxの再帰式に従うことにあります。

Fmax(e, n) = 1 + Fmax(e-1, n-1) + fmax(e, n-1)

そして、Fmaxの直接数式を取得するための核心は、Fmaxの再帰式に従うことにあります。

Fmax(e, n) = { ∑Fmax(e-1,i) for i = 1 to n } - Fmax(e-1, n) + n 

この問題には、二分探索木（BST）を使用した代替ソリューションも可能です。分析を容易にするために、次のようにわずかな変更を加えてBSTを描画しましょう。

1.    If egg breaks then child node is drawn on left down side
2.    If egg does not break then child node is drawn straight down side

上記の種類の表現でBSTを描画する場合、BSTの幅（つまり、BSTの垂直列の数）は卵の数を表します。

上記の種類の表現で描画され、BST <= e（卵の数）の制約幅に従うf個のノードを持つBSTはすべて解決策ですが、最適な解決策ではない場合があります。

したがって、最適な解を取得することは、制約を受ける最小の高さでBSTのノードの配置を取得することと同じです。BSTの幅<= e

上記の3つのアプローチすべての詳細については、次のブログを確認してください。一般化された卵の落下問題を解決するための3つのアプローチ

Answer 3

これは、 Egg DropPrintingSolutionsで提供したのと同じ答えです。ここでは、決定木全体と推論のレイアウトを確認したい人のために提供しています。

# This uses dynamic programming to find the basic information.
def optimal_solution(floors, eggs):
    # dp[drops][eggs] = max_floors
    dp = []

    # With no drops, we can do no floors
    dp.append([0 for x in range(eggs+1)])

    # With one drop and any eggs, we can do 1 floor
    one_drop = [1 for _ in range(eggs+1)]
    one_drop[0] = 0 # Except no eggs is still no floors
    dp.append(one_drop)

    # Keep adding drops until we have our answer
    # Note, in python array element -1 is shorthand for the end of the array.
    while dp[-1][eggs] < floors:
        # 0 floors for 0 eggs.  1 more for one egg
        next_drop = [0, dp[-1][1] + 1]
        for i in range(2, eggs+1): # Python for 2..eggs
            # The best we can do is drop at floor dp[-1][i-1].
            # If the egg breaks, we can find the answer using that solution.
            # If the egg holds, we can find another dp[-1][i] floors.
            next_drop.append(dp[-1][i] + dp[-1][i-1])
        dp.append(next_drop)

    return dp

# This turns that optimal solution into a decision tree.    
def dp_to_decision_tree(dp, floors, start_floor=None, eggs=None, drops=None):
    # Figure out defaults if needed.
    if start_floor is None:
        start_floor = 0
    if drops is None:
        drops = len(dp) - 1
    if eggs is None:
        eggs = len(dp[0]) - 1

    # Are we done?
    if floors == start_floor:
        return start_floor
    elif dp[drops][eggs] < floors - start_floor:
        return None

    # Do we need all of our drops?
    while floors - start_floor < dp[drops-1][eggs]:
        drops -= 1

    drop_at = start_floor + dp[drops-1][eggs-1]
    if eggs == 1:
        drop_at = start_floor + 1
    if floors < drop_at:
        drop_at = floors
    return [
        drop_at,
        dp_to_decision_tree(dp,  floors,     drop_at,   eggs, drops-1),
        dp_to_decision_tree(dp, drop_at-1, start_floor, eggs-1, drops-1),
        {'eggs': eggs, 'floor_range': (start_floor, floors)}
        ]

# This prints the decision tree in a human readable format.
def print_decision_tree(tree, indent="", label="start"):
    if tree is None:
        print(f"{indent}{label}: ?")
    elif isinstance(tree, int):
        print(f"{indent}{label}: {tree} found")
    else:
        print(f"{indent}{label}: {tree[0]} {tree[3]}")
        print_decision_tree(tree[1], indent + "    ", label="held")
        print_decision_tree(tree[2], indent + "    ", label="broke")

# And this calls the previous functions.
def print_optimal_decisions(floors, eggs):
    print_decision_tree(
        dp_to_decision_tree(
            optimal_solution(floors, eggs), floors))

# And now we can try it.
print_optimal_decisions(36, 3)

Answer 4

単純な動的計画法ソリューションを使用できます。n-フロア数。k-卵の数。D [n、k] =あなたが答えます（最小スローの数）。D [j、1] = n-1 for each 1 <= j<=n。

k>1の場合にD[n、k]を計算するための主なアイデア。

D [n、k]=最大1<= j <= n-1{最大{D[j、k-1] + 1、D [nj、k]+1}。

Answer 5

ここのブログでは、1000階の3個の卵の数学的アプローチについて説明しています。

https://sankalpiitr.wordpress.com/2012/03/02/the-2-eggs-problem-extended-to-3-eggs/

このブログによると、式は

P = N +（N *（N + 1）*（N – 1））/ 6

ここで、Pはフロア数、Nは必要な最小ドロップ数です。

したがって、P = 100を解くと、Nは8.2になります。