コイン両替問題を３種類の探索方法で解いてみた
20140812修正：DPの説明と記事タイトルを修正。DPの認識間違ってましたorz
いつも通り、Objective-Cね。
深さ優先探索（既出）と両替問題の内容
csny/exchange_problem · GitHub
幅優先探索
csny/BFS · GitHub
BFS/main.m at master · csny/BFS · GitHub
メモ化再帰
csny/memorecurse · GitHub
memorecurse/main.m at master · csny/memorecurse · GitHub
見よう見まねで動くようにしただけなので、個人的に慣れ親しんだ深さ優先探索ほどは使いやすくなかった。調べれば調べるほど、動的計画法DP＝全経路探索による課題解決は遅いのでメモしちまおうというだけであって、あまり深い意味がないことに気づかされる。間違いがあったら指摘よろ。
深さ優先探索
関数の中で関数自身を呼ぶ作りにすると自然とこれになる。条件で枝を落とさないと、探索対象の数に応じて指数関数的に遅くなる。
幅優先探索
M.Hiroi's Home Page / Puzzle De Programming
この辺を参考に、FIFO型でやってみたけど、キューのサイズが圧倒的に足りない。これも、条件で枝を落とさないと、探索対象の数に応じて指数関数的に厳しくなる。主にメモリが。
ネックがメモリなので、[[NSMutableArray alloc] init]とか[[NSMutableDictionary alloc] init](Cで言えばmalloc)やリングバッファ使った柔軟（面倒）な処理が必要になるみたい。単純化する（面倒な）ため、今回は配列の要素を定数にしてます。
リングバッファと配列 - NAVER まとめ
今回の課題は配列の要素2万でも最後まで探索できませんでしたw 幅優先探索そもそもの作りとして自然と最短経路を見つけてくれるし、子ノードを全部入れたら親ノード（配列の先頭）を１つ削除する形にすれば、自然と幅優先探索になるので、思ったより実装は簡単でした。まだしっくりはきてないけど、流れはこんな感じ。
- 親ノードをキューに入れる
- 子ノードを全部キューに入れる
- キューに入れたばかりの子ノードを対象にif文などで答え探索
- 答えが無ければキュー先頭の親ノード１個削除
- 一番目の子ノードの孫ノードを全部キューに入れる
- キューに入れたばかりの孫ノードを対象にif文などで答え探索
- 答えが無ければキュー先頭の一番目の子ノード１個削除
- 二番目の子ノードの孫ノードを全部キューに入れる
- キューに入れたばかりの孫ノードを対象にif文などで答え探索
- 答えが無ければキュー先頭の二番目の子ノード１個削除
- …以下ループ
- キューが空になったら探索終了
一番最初の親ノードはあってもなくてもいいんだけど、仕組み的に2〜4、子ノード入れ〜親ノード削除をループさせる感じなので仕方なく入れてる感じ。そりゃーメモリだって圧迫されるわなーという１０歩進んで１歩下がる作りです。
メモ化再帰
DPの話 - aizuzia
深さ優先探索で、経路の重みなどがメモ用の配列に入ってreturnされるとメモ化再帰と呼ぶらしい。だから、定義する関数はvoid型ではなく、値を返すint型になる。枝落としをしない上記２つの解法と比べると、総当たりの癖にめちゃ早。
ただ、まだ慣れてないからだろうけど、すごい癖のある作りになって使いづらい。最短距離が出るからそこはいいんだけど、メモで返ってくるところが特に、途中の経路の出力とかの条件が操作しづらい。
