野次馬エンジニア道

野次馬な気持ちでプログラミングをあれこれと綴ります

動的計画法とトポロジカルソート

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

を本屋で見て買おうか迷っていたところ、アルゴリズムの図解ということでふと思い出したのが、 アルゴリズムイントロダクション15章 動的計画法のスライド。ここで登場する最長共通部分列の図は目から鱗だった。

そういえば電子書籍

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

を持っていたままあまり読んでいなかったので久々にアルゴリズムの勉強でもしてみる。 本を片手に自分で実装してみたものをそのままメモ。

なんとか理解できそうなものをかいつまみ。

DP: Longest Common Subsequence problem: LCS

動的計画法の有名な問題らしい。最長共通部分列とは、X = {a, b, c, b, d, a, b},Y = {b, d, c, a, b, a}があるとすると{b, c, b, a}。

// O(NM)
// dp[i][j] = dp[i-1][j-1]+1 //X[i]==Y[j]
//          = max(dp[i-1][j], dp[i][j-1]) //X[i]!=Y[j]
// getLCSLength("abcbdab","bdcaba") // 4
int 
getLCSLength(string x, string y){
  int M = x.size();
  int N = y.size();
  int maxVal = INT_MIN;
  vector<vector<int>> dp;
  dp.resize(M,vector<int>(N,0));
  if(x[0]==y[0]){ dp[0][0] = 1; } else { dp[0][0] = 0; }
  if(x[0]==y[1]){ dp[0][1] = 1; } else { dp[0][1] = 0; }
  if(x[1]==y[0]){ dp[1][0] = 1; } else { dp[1][0] = 0; }
  for( int i = 1; i < M; i++ ){
    for( int j = 1; j < N; j++ ){
      if(x[i]==y[j]){
        dp[i][j] = dp[i-1][j-1]+1;
      } else {
        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
      }
      maxVal = max(maxVal, dp[i][j]);
    }
  }
  return maxVal;
}

DP: Coin Changing Problem

これも有名。最小のコインの枚数を調べる問題。

// O(NM)
// i is index of coin [0...5]
// j is amount [0...15]
// dp[i][j] = min(dp[i-1][j], dp[i][j-c[i]]+1);
// getMinimumCoinCount(15, 6, vector<int>{1, 2, 7, 8, 12, 50}) // 2
int getMinimumCoinCount(int total, int N, vector<int> c){
    vector<vector<int>> dp;
    int minVal = total;
    dp.resize(N,vector<int>(total+1,INT_MAX));
    for( int i = 0; i < N; i++ ){
        dp[i][0] = 0;
        dp[i][1] = 1;
    }
    for( int j = 2; j <= total; j++ ){
        for( int i = 0 ; i < N; i++ ){
            dp[i][j] = (i > 0) ?  dp[i-1][j] : INT_MAX;

            if( (j - c[i]) >= 0 ) {
                dp[i][j] = min(dp[i][j], dp[i][j - c[i]] + 1);
            }
        }
    }
    for( int i = 0; i < N; i++ ){
        minVal = min(minVal, dp[i][total]);
    }
    return minVal;
}

DP: Knapsack Problem

名前は辛うじて聞いたことがあるナップザック問題。ナップザックに入る重さで価値が最大になるようなものを調べる。

// O(NW)
// i - item index
// v - item value
// w - total weight
// dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
// getMaximumValue(vector<int>{2,2,1,3},vector<int>{4,5,2,8},5)
int getMaximumValue( vector<int> w, vector<int> v, int napSize ){
    vector<vector<int>> dp;
    int N = w.size();
    dp.resize(N,vector<int>(napSize+1,0));

    for( int j = 0; j <= napSize; j++ ){
        dp[0][j]= (w[0] <= j) ? v[0] : 0;
        if(j-w[0]>=0){
            dp[0][j] = max(dp[0][j], dp[0][j-w[0]]+v[0]);
        }
    }
    for( int i = 1; i < N; i++ ){
        for( int j = 1; j <= napSize; j++ ){
            dp[i][j] = dp[i-1][j];
            if( j-w[i] >= 0 ){
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    return dp[N-1][napSize];
}

DP: Longest Increasing Subsequence

今度は最長増加部分列という問題。最初に自分で考えて書いたときは

// O(N*N)
// getLISLength(vector<int>{5,5,1,3,2,4}) // 3
int getLISLength(vector<int> input){  
  vector<int> dp(input.size(),1);
  for( int i = 1; i < input.size(); i++ ){
    for( int j = i-1; j >= 0; j-- ){
      if( input[j] < input[i] ){
        dp[i]=max(dp[i], dp[j]+1);
      }
    }    
  }
  return *max_element(dp.begin(),dp.end());
}

こんな感じ。これを本に登場するより良い方法で実装すると

// O(N*logN)
// getLISLength(vector<int>{4, 1, 6, 2, 8, 5, 7, 3}) // 4
int getLISLength(vector<int> input){
    vector<int> L(input.size(),0);
    L[0]=input[0];
    int length = 1;

    for( int i = 1; i < input.size(); i++ ){
        if(L[length-1] < input[i]){
            L[length++] = input[i];
        } else {
            *lower_bound( L.begin(), L.begin()+length, input[i] ) = input[i];
        }
    }
    return length;
}

lower_boundは中で二分探索。指定した値以上の最初の要素の位置(つまり値を挿入できる位置)をイテレータで返してくれる。

Graph Topological Sort

ビルド順を考えたりする際によい(そんな仕事はしていないけど)よい方法。 以前に書いた幅優先探索

データ構造 - 計算量・グラフの走査 - 野次馬エンジニア道

がそのまま使われている。

// O(|V |+|E |)
//     vector<pair<int,int>> v{
//        make_pair(0,1),
//        make_pair(1,2),
//        make_pair(3,1),
//        make_pair(3,4),
//        make_pair(4,5),
//        make_pair(5,2)
//    };
//    getSortedNode(v, 6); // {0,3,1,4,5,2}
struct Node {
    int value;
    vector<Node*> next;
    int count;
    bool added;
    Node():value(-1),count(0),added(false){}
};

void traverseBFS( vector<int>& ret, Node* root ){
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
        Node* n = q.front();
        q.pop();
        ret.push_back(n->value);
        n->added = true;
        auto it = n->next.begin();
        while( it != n->next.end()){
            Node *next = *it;
            next->count--;
            if(next->count == 0 && !next->added ){
                q.push(next);
            }
            ++it;
        }
    }
}

vector<int> getSortedNode( vector<pair<int,int>> v, int N){
    vector<Node> node(N);
    vector<int>  ret;
    for( int i = 0; i < N; i++ ){ node[i].value=i; }
    for( pair<int,int> p : v ){
        node[p.first].next.push_back(&node[p.second]);
        node[p.second].count++;
    }
    for( int i = 0; i < N; i++ ){
        if( node[i].count == 0 && !node[i].added ){
            traverseBFS(ret, &node[i]);
        }
    }
    return ret;
}