動的計画法5 ロッド切り出し問題

ちょうど一年ぶりに動的計画法のエントリですが, Stixel を求める問題で動的計画法を使わないといけなかったので,簡単に復習の意味も込めてエントリをつくります.今回のロッド切り出し問題は Stixel を求める問題ととっても似てまして,これがわかれば Stixel 解決にむけて一気に理解が進むかな?と思いまして.

問題定義

ロッド切り出し問題
あなたはコーナンで働いているとします!長〜い金属棒を仕入れて,これを小分けに切断して販売したいですが,金属棒は長さによって販売価格が異なります.そして,販売価格は長さに比例しているとは限りません!このときに,長さ n の金属棒をどのように切断すれば売上を最大化できるでしょうか?

で,上記の問題を解くには金属棒の長さ毎の価格表が必要です.この価格表を下記のように定義します.(ちょっと話はそれますが,確かに長さの短いものは切れ端としていっぱいできそうなので,値段は安くなりそうですよね.)

長さ | 1 | 2 | 3 | 4 |  5 |  6 |  7 |  8 |  9 | 10
ーーー|ーーー|ーーー|ーーー|ーーー|ーーーー|ーーーー|ーーーー|ーーーー|ーーーー|ーーー
価格 | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30

で,いつもの如く図示します.

f:id:rkoichi2001:20191012164226j:plain
n = 4 の場合のロッド切り出し問題

で上図を見ていただけるとわかると思うのですが, n = 4 の場合の最適な切り出し方は [2, 2] であることがわかります.

次に,n = 5 の場合の切り出し方法を考えてみたいと思います.で,ここではちょっと考え方を変えて,n = 5 のロッドに対して一回だけカットする(もしくは全くカットしない)パターンを書き出してみます.

f:id:rkoichi2001:20191012170710j:plain
n = 5 のロッドに対して,一度だけ切り込みを入れた(もしくは入れなかった場合)場合

上図からわかると思うのですが,結局 n = 5 の問題の解はそれより小さい問題の最適解の組み合わせになります.全くカットしなかった場合は新しいパターンになりますが,これはテーブルから一発で求めることができ,どこか一箇所にでも切り込みを入れるとそれよりも小さい問題の最適解の足し算になります....

ということで,再帰的に求める方法がわかりそうです!

1.再帰的に求める方法を考える

では,いつものように「魔法の関数」を考えます.

get_optimal_cut(price, length)
price : ロッドの長さに応じた価格表
length : 最適価格を求めたいロッドの長さ

で,上記の関数がうまく動くとします.とすると,n = 5 の場合の関数のコールイメージは下記のようになります.

長さ = 5 のロッドの最適切り出し...
カットしなかった場合:p[n]  <- テーブルを直接参照
1,4 で分割:get_optimal_price(price, 1) + get_optimal_price(price, 4)
2,3 で分割:get_optimal_price(price, 2) + get_optimal_price(price, 3)
3,2 で分割:get_optimal_price(price, 3) + get_optimal_price(price, 2)
4,1 で分割:get_optimal_price(price, 4) + get_optimal_price(price, 1)

上記の組み合わせから最適なものをえらぶので...

max(
p[n], 
get_optimal_price(price, 1) + get_optimal_price(price, 4), 
get_optimal_price(price, 2) + get_optimal_price(price, 3),
get_optimal_price(price, 3) + get_optimal_price(price, 2),
get_optimal_price(price, 4) + get_optimal_price(price, 1),
)

となります.実際には(1,4)と(4,1)の切り出しは等価なのでもっと計算を減らせると思うのですが,ひとまずこのまま進みます.上記の関数をコードに落とすと,下記のようになります.

price_tbl = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

def rod_cutting(price, length):

    # Base Case
    if (length == 1):
        return price[length - 1]
    
    # No Cutting Case.
    opt_price = price[length - 1]
    for i in range(length - 1):
        left_length = i + 1
        right_length = length - left_length
        opt_price = max(opt_price, rod_cutting(price, left_length) + rod_cutting(price, right_length))

    return opt_price

if __name__ == '__main__':

    length = 4
    opt_price = rod_cutting(price_tbl, length)
    print('Optimal Price for length {0} : {1}'.format(length, opt_price))

2.再帰関数の分岐から漸化式を作る

ということで,ここまでくればあとは機械的に行けそうです.漸化式は,下記のようになります.opt_price[i] は長さ i のロッドの最適価格です.

no_cut_price = price_tbl[i]   :切り込みを入れないときの値段
cut_price = max1≦k≦i-1(opt_price[k] + opt_price[i - k])   :切り込みを入れたときの最適値段
opt_price[i] = max(no_cut_price, cut_price)   :最終的な最適値段

3.漸化式を使って,ボトムアップで表を埋めていく

漸化式が出来上がったので,長さが小さいロッドから表を埋めていけば,DPでこの問題を解くことができます.最終的な実装は下記のようになります.下記の実装では,最適値段だけでなくどの切り方をすれば最適値段が求まるかも出力しています.

price_tbl = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
opt_price_tbl = [-1 for elem in price_tbl]
cut_from_left = [-1 for elem in price_tbl]

def rod_cutting_with_dp(price, length, opt_price, cut_from_left):

    # Compute Optimal Price for Rod of Length i
    for i in range(length):

        # Base Case
        if (i == 0):
            opt_price_tbl[0] = price_tbl[0]
            cut_from_left[0] = 1
            continue

        # No Cutting Case.
        opt_price = price_tbl[i]
        cut_from_left[i] = i + 1

        for j in range(i):
            left_length = j + 1
            right_length = i + 1 - left_length

            new_price = opt_price_tbl[left_length - 1] + opt_price_tbl[right_length - 1]
            if (opt_price < new_price):
                opt_price = new_price
                cut_from_left[i] = j + 1

        opt_price_tbl[i] = opt_price

    return opt_price_tbl, cut_from_left


if __name__ == '__main__':

    length = 10
    opt_price_tbl, cut_from_left_tbl = rod_cutting_with_dp(price_tbl, length, opt_price_tbl, cut_from_left)
    print('Optimal Price Table : {0}'.format(opt_price_tbl))
    print('Optimal Cut Table   : {0}'.format(cut_from_left_tbl))

ということで,このことを踏まえて Stixel に戻ります!

参考文献

何冊本もってんだよ!?って話ですが,積読本の中の一つです(笑)

アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書

アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書