第一回はこちら。
シリーズ化なんて考えてなかったんですけど、まあ勢いで。
さて許される計算量のオーダーは推測できた、ではアルゴリズムを考えよう……、
という時に、自分は、どうも3種類くらいの方法でアルゴリズムの設計を試みているように思います。
今回はそのうちの一つをまとめてみます。
問題
題材は "Small Change"。
どういう問題かというと、﹃Anarchygolfania という国で流通している貨幣(コイン)の一覧と、
払いたい金額が与えられます。できるだけコインの枚数が少なくなる払い方を答えましょう﹄です。
たとえば、Anarchygolfania には1円玉と7円玉と12円玉だけがある場合、14円を払うには、7円玉2枚で払うのが最適です。
現実の貨幣では、たいてい単純に大きい額のコイン/紙幣から順に使っていくと最適になるものですが、
この例の場合は、それをやると 12+1+1 の3枚になっちゃって、ダメです。
というわけで、最適解を見つけるにはいささか工夫が必要です。
ええと、問題を整理しましょう。こうですね。
●入力‥ C[0], C[1], ..., C[N-1] ︵コインの金額一覧︶
●入力‥T︵払いたい金額︶
●出力‥ P[0], P[1], ..., P[M-1] ︵最適な払い方︶
いくらでも解き方は考えられますが、さてさて…。
パラメータ いっこ へらす
自分はよく、ちょっとだけ問題を﹁小さく﹂して考えてみます。
たとえば、入力 Tを小さくしてみる。
コインの金額は同じままで、T-1 円 の最適な払い方をまず計算してみよう。
そしたらそこから簡単にT円 の最適な払い方も求まったりしないでしょうか…？
残念ながら、難しそうです。T-1円の払い方を応用してT円を払うなんて、
あとに1円玉を付け足すくらいしか手がありません。けど、それが最適になるとは限りません。
諦めずに問題を小さくしまくります。
T-1 円 の最適な払い方と
T-2 円 の最適な払い方と、(中略)、
3円 の最適な払い方と
2円 の最適な払い方と
1円 の最適な払い方と
0 円 の最適な払い方を全部計算したらどうだ！
今度はなんとかなります。たとえば、コインが1円玉、7円玉、12円玉だったら、T円の最適な払い方は、
﹁T-1円の最適な払い方 + 1円玉﹂ か
﹁T-7円の最適な払い方 + 7円玉﹂ か
﹁T-12円の最適な払い方 + 12円玉﹂ のどれかしかありえないので。
コードで書くとこうです。
opt[T] = # T円の最適な払い方は
C.select{|c| opt[T-c]}.
map{|c| opt[T-c]+[c]}. # T-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
よし、でき…てないですね、まだ。
T-1 円の最適な払い方とT-2 円の最適な払い方と︵中略︶の最適な払い方を全部計算しておかないと、
このコードだけではうまくいきません。計算しましょう。ハイパーコピペタイム！
...
opt[T-2] = # T-2円の最適な払い方は
C.select{|c| opt[T-2-c]}.
map{|c| opt[T-2-c]+[c]}. # T-2-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
opt[T-1] = # T-1円の最適な払い方は
C.select{|c| opt[T-1-c]}.
map{|c| opt[T-1-c]+[c]}. # T-1-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
opt[T] = # T円の最適な払い方は
C.select{|c| opt[T-c]}.
map{|c| opt[T-c]+[c]}. # T-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
嘘ですすみません。ループしてください。
opt = {} # opt[t] はt円の最適な払い方。これから求めるよ！
opt[0] = [] # 0円 はコイン0枚で最適に(?)払えます
1.upto(T) do |t|
opt[t] = # t円の最適な払い方は
C.select{|c| opt[t-c]}.
map{|c| opt[t-c]+[c]}. # t-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
end
p opt[T]
これが答えその1。
ほかを減らす
﹁なんで Tを小さくしたの？ 他の部分を小さくするのはダメなの？﹂
と思ったので、N を小さくしてみましょうか。
﹁C[0] .. C[N-2] のコインだけを使ったT円の最適な払い方﹂をまず計算してみよう。
そしたら簡単に﹁C[0] .. C[N-1] のコインを使ったT円の最適な払い方﹂も求まるのではないか。
……これもやっぱり、そのままでは上手くいかなそうです。どこに C[N-1] 円玉 を挟み込んだものだかよくわからない。
今度はNを減らしまくって C[0] .. C[N-3]でのT円の最適な払い方、
C[0] .. C[N-4]でのT円の最適な払い方、
︵中略︶
C[0] だけでのT円の最適な払い方、
を全部計算するのでもうまい方法が思いつきません…少なくとも私には。
めんどうになったのでTの方も同時に小さくします。
﹁C[0] .. C[N-2] のコインだけを使った0円と1円と2円と︵中略︶T-1円とT円の最適な払い方﹂
がわかればなんとかなるだろう！
opt = [[]] # コインを1種類も使わない場合、0円だけは払えます。他は払えません
C.each_with_index do |c, n| # c==C[n] 番目までのコインだけを使う0円と1円と（中略）T円の払い方は…
opt = (0..T).map do |t|
(0..t/c).select{|k| opt[t-c*k]}.
map{|k| opt[t-c*k] + [c]*k}. # C[n-1]までを使った t-c*kの最適な払い方 + c円玉をk枚
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
end
end
p opt[T]
こんな感じで。答えその2でした。
さらにほかを減らす
たとえば C[1] を小さく、というのは流石に上手く行かないような気がするのですよ。7円玉の代わりに6円玉がある世界での最適解がわかっても、そこで6円玉が7円玉に変わったらちょっとどうしようもない。
話が違いすぎる。︵……と私が思っているだけで、上手い手があるかもしれません。みなさん考えてみて下さい。︶
ということで、入力パラメータ C[i], N, T の減らし方は全部ひととおり考えてみたので、
もう小さくする他の方法はありません！
なんてことはありませんね！！ 出力、M を小さくしてみちゃいます。
ちょっと発想の転換が必要です。元々の問題ではMは、﹁T円を払うのには最低M枚コインが必要﹂
という値でした。逆に言うと、これは﹁M枚あればT円払える﹂ということです。
さて、減らしにかかりましょう。﹁M-1枚 あればT円を払える﹂かどうかわかれば、M枚あればT円を払えるかどうかもわかるのではないでしょうか？
……やっぱり、今度も、ちょっとわかりません。
﹁0枚では払えない、1枚では︵中略︶、M-1枚では払えない﹂とだけ言われても、
その次、M枚で払えるか払えないかは判断つきません。
仕方がないので、またTの方をいじります。﹁M-1枚 あれば払える金額一覧﹂
があれば﹁M枚あれば払える金額一覧﹂も計算できます。
payable_by_m = {0 => []} # 0枚で払える金額一覧 == 0円:[]
0.upto(T) do |m|
if payable_by_m[T] # Tがm枚で払えるならそれが答え
p payable_by_m[T]
break
end
payable_by_m_plus_1 = {} # m+1枚で払える金額一覧を計算…
payable_by_m.each do |money, howto| # m枚あればmoney円を払えて
C.each do |c| # c円玉が存在するならば
payable_by_m_plus_1[money+c] = howto+[c] # m+1枚でmoney+c円を払える
end
end
payable_by_m = payable_by_m_plus_1
end
答えその3でした。ただし、実際には、いくつか高速化の余地があります。
﹁T円より大きい金額が払えるか払えないか計算しても無駄なので、money+c >T
の時にはpayable_by_...に記憶しない﹂とか﹁最適解じゃないmoney, howtoペアを考えてもしかたが無いので、
すでに払い方が求まってるmoneyのリストを別に覚えておいて、それが出てきたらpayable_by_...に記憶しない﹂
辺りですかね。
まとめ
問題をみたらとりあえず
﹁パラメータ1個小さくした問題を先に解いておけば、そこから簡単に元の問題の答えも求まるんじゃない？﹂
と考えてみる、というのが今回紹介したやり方でした。
こうやって作ったアルゴリズムは、基本的には
動的計画法
(DP / Dynamic Programming)
と呼ばれるものになります。
︵ただし、答えその3みたいなのは微妙なところで、普通は幅優先探索などと呼ばれると思う。︶
今回の例でループで書いた部分を、再帰
(+メモ化)
で実装するという方法もあります。関数型大好きっ子はたぶんそっちの方が楽だと思います。
いずれにせよ、﹁パラメータをひとつ小さくしてみる﹂のがポイント。
大抵のアルゴリズム設計の本に載ってると思うので、詳細は書籍等で熟知すべし。
﹁どのパラメータを小さくすればいいか？﹂の判断や、
小さくしてみてダメだった時に﹁話をさらに進めてみる︵今回だと、Nと同時にTも小さくしてみる /
払える金額一覧を計算する、のような拡張︶﹂判断は、ある程度慣れるしかないかもしれないです。
今回はたまたまどの方向も上手く行きましたが︵…といっても、どれも結局Tをいじってるので、Tを減らす方法以外は上手く行ってないと言う見方もできるかもしれませんけど︶、
問題によっては、減らす正解のパラメタは一つで、
しかも、適度に求めるものを調整してやらないと全然ダメだったりします。
もちろん、この手段では解けない問題も当然あります。
ただ、でも、漠然と考えるよりは、﹁ひとまわり小さい問題の答えから大きな問題の答えを作れるかどうか﹂
に焦点を絞って考えた方が、答えが見つかりやすいんじゃないかなーと思うのでした。
