アルゴリズムを学んでみるⅠ

目的

algorithmをやるぞい
勉強の進め方：text参照→著者のコード参照→実装→言語化→改造の順で進めていく．

参考文献・サイト

問題解決力を鍛える!アルゴリズムとデータ構造（4章）
著者のgithubページ

結論

再帰関数は影分身

動的計画法は数学の大問

内容

再帰関数

　再帰関数は簡単に言おうとそのまま自分自身を呼びす方法. 注意点としてif文である程度のところで終わる処理を入れないと，永久ループになることである．

動的計画法

　大きなタスクを小さいタスクに分割し，それぞれのタスクを重複しないように探索する方法．
listや辞書を用いて記録処理できるまでタスクを小さく設定し，得られた値を記録する．
数学問題で置き換えると，受験問題の１つの大問をベクトルや図形，数列などのいくつかのタスクに分解しそれぞれを逐次的に解くやり方に近い．

以下章末の最も苦戦した最後の問題を例にとてDPと再帰関数について実践した結果だ．

章末4.9

問題は再帰関数とメモ化を用いてlistで与えられてあ数値群の中に整数Ｗが存在するかを全探索で求める問題．テキストに記載されている著者の引用コード(githhubより)を下記に示します.
またここでは説明のために

n=4 w=11
a=[3 1 4 5]

という入力を用いて説明するものとする.

#include <iostream>
#include <vector>
using namespace std;

bool func(int i, int w, const vector<int> &a) {
    // ベースケース
    if (i == 0) {
        if (w == 0) return true;
        else return false;
    }

    // a[i - 1] を選ばない場合
    if (func(i - 1, w, a)) return true;

    // a[i - 1] をぶ場合
    if (func(i - 1, w - a[i - 1], a)) return true;

    // どちらも false の場合は false
    return false;
}

int main() {
    // 入力
    int N, W;
    cin >> N >> W;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // 再帰的に解く
    if (func(N, W, a)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

最初何を意味するのか全く分からなかったが，時間をかけて勉強すると少しずつ分かってきた.
端的に述べるとlistを最後の要素から排除して，減らした各リストの値の合計がWであるか求めているだである．分かりずらければ，探索範囲を少しづつ小さくしながら解を求めているとだけ頭にとどめてほしい.
まずこのコードで着目すべきは以下の部分だ．

    // a[i - 1] を選ばない場合
 ①  if (func(i - 1, w, a)) return true;

   // a[i - 1] をぶ場合
 ②  if (func(i - 1, w - a[i - 1], a)) return true;

これは部分問題にするためのコードで

\displaylines{①\alpha_{0\sim N-1}  \\ ②\alpha_{0\sim N} }

の二つに分けらる. （①、②は分り易くするためにおいてるだけです）
　まず②に関してlistのサイズを１減らす，つまり[3 1 4 5]から[3 1 4]とする。またWの値をA[-1]だけ減らす，つまりWを11から6として扱い，func()に対して値を再代入する。つまり最初の条件がn=3,W=6,A=[3 1 4]をfunc()に代入した問題へと変化した. この変化が大切である. もしここで後ろから順に減らして例えば0番目と2番目の要素の和がWとなったらどうするんだと思った方，鋭い.それは次にお答えします.
　①の方に戻って考えると，これはi(n==i)の値をただ減らしている．何気にここがポイントだ。
例で例えると，上の操作を思い出して答えを求める道だけ考えてみる.つまり
if (func(i - 1, w - a[i - 1], a)) → if (func(i - 1, w, a))→ if (func(i - 1, w - a[i - 1], a))→
（一番最初のif文） if (i == 0) {
if (w == 0) return true;｝
に繋がるのだ. ここで注目ポイントはi=1番目の要素を飛ばしている点だ．
まめると①，②の二つのif文でWの値を減らしつつlistのどの要素でWを求めるのかを全探索で行っているのだ．

メモ化して改造

def func(N, W, a):
    memo = {}

    def judge(N, W):
        # ベースケース
        if W == 0:
            return True
        if N < 0 or W < 0:
            return False

        # メモ化されている場合
        if (N, W) in memo:
            return memo[(N, W)]

        # 再帰的に探索
        # a[N] を選ばない場合、選ぶ場合をチェック
        if judge(N - 1, W) or judge(N - 1, W - a[N]):
            memo[(N, W)] = True
            return True

        memo[(N, W)] = False
        return False
    judge(N - 1, W)
    ans = True in memo.values()
    return ans

方針：メモは辞書を用いた.
読み方としては元のコードに探索用記録用の辞書を追加した.

結論

　教科書を読んでみて，再帰関数や動的計画法を分かったつもりであっても，実際にコードを記述する段階になると，再帰をどうやって行い，それを上手い事探索に持ってくるかという点が難しかった．
　けれど着実に成長していることが分かる．

今後の方針

　とりあえず，テキストを１２月までには１周したい