Pythonで解く卵落としパズル ―― 動的計画法による最小試行回数の求め方

はじめに

この記事では、次の問題文に対する解決策を、Pythonでの実装を通して学んでいきます。

問題文

40階建てのビルがあるとします。私たちが知りたいのは、「どの階から卵を落としても安全か」「どの階から落とすと卵が割れてしまうか」という情報です。ただし、使える卵の数には限りがあります。
そこで、全階層を確実に判定できる最悪ケースにおける最小の試行回数を求めて表示するプログラムを作成します。

これは「卵投下問題（Egg Dropping Puzzle）」として知られる、動的計画法の定番問題の一つです。

アルゴリズムの考え方

eggFloor[i][j] を「i個の卵を使ってj階までの建物を調べるときに必要な最小試行回数」と定義します。

ある階xから卵を落としたとき、結果は次の2つに分かれます。

• 卵が割れた場合：残り i−1 個の卵で、x−1 階より下の階を調べる
• 卵が割れなかった場合：i 個の卵のまま、残り j−x 階分を上の階で調べる

したがって、再帰式は次のようになります。

eggFloor[i][j] = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])

この値が最小になるような x を全探索することで、答えが得られます。

サンプルコード

# 動的計画法
INT_MAX = 32767

# 最小試行回数を求める関数
def eggDrop(n, k):
    # テーブルの初期化
    eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
    # ベースケース
    for i in range(1, n + 1):
        eggFloor[i][1] = 1
        eggFloor[i][0] = 0
    # 卵が1個の場合は常にj回の試行が必要
    for j in range(1, k + 1):
        eggFloor[1][j] = j
    # 残りのテーブルを埋める
    for i in range(2, n + 1):
        for j in range(2, k + 1):
            eggFloor[i][j] = INT_MAX
            for x in range(1, j + 1):
                res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])
                if res < eggFloor[i][j]:
                    eggFloor[i][j] = res
    return eggFloor[n][k]

# メイン処理
n = 4
k = 40
print("Minimum number of trials in worst case scenario with " + str(n) + " eggs and "+ str(k) + " floors is " + str(eggDrop(n, k)))

実行結果

Minimum number of trials in worst case scenario with 4 eggs and 40 floors is 6

この結果から、卵4個・40階建てという条件では、最悪の場合でもわずか6回の試行ですべての階の安全性を判定できることがわかります。

なお、このアルゴリズムの計算量は O(n × k²) です。階数が大きくなると処理時間が増加するため、より効率的な戦略や数学的な解法と組み合わせる工夫も有効です。

まとめ

この記事では、動的計画法を用いて卵落としパズル（卵投下問題）を解くPythonプログラムの作成方法を学びました。「状態の定義」と「再帰式」を正しく立てることが、この種の問題を解くうえでの鍵となります。