再帰で漸化式を解こうとしたが、引数が大きくなると実行時間が長くなりすぎる

Question

前提

以下の問題を解いています。漸化式を立て、再帰で解くことを試しております。

dice_number個の、sides面ダイスを振ったとき、出目の総和がtargetとなる確率を出力するプログラムを作成せよ

※再帰についての理解はあまり深くないです。「関数のreturn文に関数自身を書いておくと、プログラムが勝手に何回も走って答を出してくれる」くらいに理解しております。

発生している問題

dice_numberが小さいうちはすぐに答えが出るのですが、10前後になるとプログラムが終了しません。
また、出力そのものの正しさについては、小さいdice_numberで確認しております。

###方針
dice_numberをn, sidesをs, targetをtと書きます。問題の条件を満たす場合の数N=N(n,s,t)は漸化式
N(n,s,t)=N(n-1,s,t-1)+N(n-1,s,t-2)+...+N(n-1,s,t-s)
を満たすので、再帰で計算できる（はず）。

該当のソースコード

# 場合の数Nを求める
def N(dice_number: int, sides: int, target: int) -> int:
    # 初期条件
    if dice_number == 1:
        if 1 <= target <= sides:
            return 1
        else:
            return 0
    # 漸化式の本体
    else:
        return sum([N(dice_number-1, sides, target-i) for i in range(1, sides+1)])


# 場合の数Nを全組み合わせのsides**dice_numberで割ると確率になる
def probability(dice_number, sides, target):
    return N(dice_number, sides, target)/sides**dice_number

教えていただきたいこと

1. そもそも再帰で解くのが最適な問題なのでしょうか？
2. （もしそうだとすれば）どこを直せばもっと高速に動作するプログラムになるのでしょうか？

ご教示お願い致します。

補足情報（FW/ツールのバージョンなど）

出典はこちら

Answer 1

そもそも再帰で解くのが最適な問題なのでしょうか？

いいえ

（もしそうだとすれば）どこを直せばもっと高速に動作するプログラムになるのでしょうか？

全部

再帰って避けられるなら避け計算量を減らす方向性が正しいです。
今回のケースだと、計算結果をキャッシュしておくのが定石かと。

Comments

[hayataka2049]

pythonだと幸い標準ライブラリにありますね。手元で試したところ、10面10個くらいなら一瞬で終わるようです。
https://docs.python.org/ja/3/library/functools.html#functools.lru_cache

[退会済みユーザー]

自前実装前提で回答してました＾＾；
この辺が整理されているのはさすが python って感じですね。

フォローありがとうございます。

[hayataka2049]

コメントしてから気づきましたが、Lhankor_Mhyさんの「メモ化」のリンクが思いっきりこの話でした。かぶった

Answer 2

とりあえず、

def N(dice_number: int, sides: int, target: int) -> int:
    print(dice_number, sides, target)
    ...

として、probability(3,6,7)のログをとってみた結果が以下です。

3 6 7
2 6 6
1 6 5
1 6 4
1 6 3
1 6 2
1 6 1
1 6 0
2 6 5
1 6 4
1 6 3
1 6 2
1 6 1
1 6 0
1 6 -1
2 6 4
1 6 3
1 6 2
1 6 1
1 6 0
1 6 -1
1 6 -2
2 6 3
1 6 2
1 6 1
1 6 0
1 6 -1
1 6 -2
1 6 -3
2 6 2
1 6 1
1 6 0
1 6 -1
1 6 -2
1 6 -3
1 6 -4
2 6 1
1 6 0
1 6 -1
1 6 -2
1 6 -3
1 6 -4
1 6 -5

よく見ると、同じパラメータでの呼び出しが何度も行われています。これをメモ化すれば、かなり計算量を減らせるでしょう。
また、targetが負になっているものはそれ以上ダイスロールがいらないはずなので、それ以上の呼び出しを刈ることができるはずです。

Answer 3

メモ化した例を示します。
x.py

from functools import lru_cache
import time

# 場合の数Nを求める
def N(dice_number, sides, target):
    if dice_number < 1 or target < dice_number or dice_number * sides < target:
        return 0
    if dice_number == 1:
        if 1 <= target <= sides:
            return 1
        else:
            return 0
    return sum([N(dice_number - 1, sides, target - i) for i in range(1, sides + 1)])

@lru_cache()
def N_X(dice_number, sides, target):
    if dice_number < 1 or target < dice_number or dice_number * sides < target:
        return 0
    if dice_number == 1:
        if 1 <= target <= sides:
            return 1
        else:
            return 0
    return sum([N_X(dice_number - 1, sides, target - i) for i in range(1, sides + 1)])

loop = 4


for _x in range(loop):
    start = time.time()
    print(N(10, 6, 30))
    print("elapsed N  :{:f}".format(time.time() - start))

    start = time.time()
    print(N_X(10, 6, 30))
    print("elapsed N_X:{:f}".format(time.time() - start))

実行例

参考情報

• Pythonで再帰フィボナッチのメモ化

https://qiita.com/takey/items/4b1767af0f0652ef8764

• Pythonのベンチマークライブラリ「Benchmarker」

http://dragstar.hatenablog.com/entry/2015/04/21/193025

Answer 4

10面ダイスを10回振った場合の確率を求めるテストケースもあるようなので、全ての組み合わせを求める方法では制限時間をオーバーします。動的計画法などを使う必要があると思います。

参考: 複数のサイコロの目の和がある値になる確率を求める