ダイナミック企画の原理
20716 ワード
前の文章で二つの問題を述べました.鋼条切断問題:http://blog.csdn.net/ii1245712564/article/details/44464689 行列チェーン乗算の問題:http://blog.csdn.net/ii1245712564/article/details/44464689
この二つの問題を注意深く観察してみると、彼らは明らかな動的計画の二つの大きな特徴を持っていることが分かりました.
鋼板カット問題では、長さnの鋼条は第一カット後に得られた二個のサブ鋼板の最適解からなることを知っていますが、マトリックスチェーン乗算は、最初にマトリックスチェーンを二つのサイズより小さい行列チェーンに分割し、マトリックスチェーン乗算の最適解はこの二つのサブ行列チェーンの最適解からなることを知っています.実際には、問題を発掘する最適なサブ構造の過程で、以下のパターンに従うことができる.
例えば、スチールカットの中で、長さがnのスチールストリップは全部でn個のサブ問題があります.長さはそれぞれのスチールストリップに関連しています.長さはnのスチールストリップに対して、{1,n-1}、{2,n-2}、、、{n,0}種子問題の選択方法があります.最適な解を中から選びます.サブ問題の総数と各サブ問題のうち、どれぐらいの選択があるかによって、計算方法の運行時間を大まかに見積もることができます.例えば、スチールカットの問題の総数はO(n)であり、各サブ問題はO(n)種の選択があります.だから、スチールカットの運行時間はO(n^2)です.
次に、図G(V,E)と図上の二つの頂点u,vが与えられた最適なサブ構造を有するかどうかを見てみよう.問題1:無権最短経路:uからvまでの辺数が最も少ない簡単な経路(無環)を見つける.問題二:最長経路は無権です.uからvまでの一番多い簡単な経路(無ループ)を見つけます.
次に、権利のない最短経路が最適なサブ構造を有することを証明する.
上のu~wあるいはw~vのルートは必ず2点の間の最長ルートに対応しますか?次の図を見てみましょう.
qからtまでの一番長い簡単な経路はq->r->tであると知っていますが、q−rの経路はqからrまでの一番長い経路ですか?qからrまでの最長経路はq−s−t−rであり、元の問題を構成するqからrまでの経路はq−rであり、最も長い経路ではないことを知っているので、ここでは最適なサブ構造を満たしていない.なぜ一番長い簡単な経路問題のサブ構造と最短経路にはこんなに大きな違いがあるのですか?一番長い経路問題と一番短い経路問題は二つのサブ問題に分けられますが、一番長い経路問題のサブ問題は互いに関連しています.一番短いパスのサブ問題は互いに関係がないからです.ここで子問題に関係ないという意味は、同じ元問題の一つの子問題の解が他の子問題の解に影響しないということです.これはどうやって理解しますか?上の最長のパスの問題を見て、qからrまでの最長のパスはq->s-t>rを得ることができます.それなら、Rからtまでの最長のパスはr-q->s->tです.しかし、簡単なパスを保証するために、qからrまでのサブ問題にはs、tを使っています.これは二つの問題の間で相互に影響を与え、第一のサブ問題に使うノードは第二のサブ問題が使えなくなり、分析ができなくなります.なぜ一番短いパスのサブ問題は無関係ですか?まず、最短経路のサブ問題が関連していると仮定します.彼らの間には必ず共通点があります.ここでこの点をpとして設定します.u~w~vの二つのサブ問題はu~p~w、w~p~vと書いてもいいです.p~w~pの部分は重複しています.それでは、今は元の最短経路e-2より短い経路e-2(p~wの距離)を見つけられます.矛盾が生じます
重複子問題
動的計画に適用される第二の特徴は、サブ問題空間が十分に小さいこと、すなわち問題の再帰アルゴリズムは同じサブ問題を繰り返し解決し、常に新しいサブ問題を生成するのではなく、再帰アルゴリズムが繰り返し解決する場合、この性質を重複サブ問題として定義することである.同じ問題を解決している以上、私たちはむしろ既得の問題を解決して保存して、次の同じ問題が発生した時に、私たちは直接に計算された問題の解を返します.行列チェーン乗算のサブ問題の性質を見てみましょう.現在は「1…4」の行列チェーンがあると仮定して、括弧化された位置を選択し始めました.
上の図を見ると、暗い部分は重複したサブ問題があることが分かりました.もし私達が忘れないなら、力を入れて一つ一つの問題を解いたら、それはとても遅いです.動的計画では、同じ問題を繰り返し解決することを避ける二つの方法がある.
/** */
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
unsigned int dealLCS(std::vector<char> X , std::vector<char> Y ,
std::vector<std::vector<unsigned int> > & tempData);
/** * * @param X X * @param Y Y * @return */
size_t LCS(std::vector<char> &X , std::vector<char> &Y)
{
if(X.size() == 0 || Y.size() == 0)
return 0;
/** */
std::vector<std::vector<unsigned int> > tempData(X.size()+1 , std::vector<unsigned>());
for (int i = 0; i <= X.size(); ++i)
{
for (int j = 0; j <= Y.size(); ++j)
{
if(i == 0 || j == 0)
tempData[i].push_back(0);
else
tempData[i].push_back(UINT_MAX);
}
}
dealLCS(X , Y , tempData);//
return tempData[X.size()][Y.size()];
}
/** * LCS * @param X X * @param Y Y * @param tempData */
unsigned int dealLCS(std::vector<char> X , std::vector<char> Y ,
std::vector<std::vector<unsigned int> > & tempData)
{
if(X.size() == 0 || Y.size() == 0)
return 0;
for (unsigned int i = 0; i < X.size(); ++i)
{
for (unsigned int j = 0; j < Y.size(); ++j)
{
if(X[i] == Y[j])
{
tempData[i+1][j+1] = tempData[i][j]+1;
}
else
{
unsigned int temp1 = tempData[i+1][j];
unsigned int temp2 = tempData[i][j+1];
tempData[i+1][j+1] = temp1 > temp2 ? temp1 : temp2;
}
}
}
return tempData[X.size()][Y.size()];
}
int main(int argc, char const *argv[])
{
char array1[]={'A','B','C','B','D','A','B'};
char array2[]={'B','D','C','A','B','A'};
std::vector<char> X(array1 , array1+sizeof(array1));
std::vector<char> Y(array2 , array2+sizeof(array2));
cout<<"The Lcs length is :"<<LCS(X,Y)<<endl;
while(1);
return 0;
} 
では、それぞれの数字は初期化値INT＿_ではないことが分かりました.MAX、tempData[i][j]は[i.j]行列チェーンの解で、それぞれの問題が解かれていることが分かります.上から下への解法を見ます.
/** */
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
unsigned int dealLCS(std::vector<char> X , std::vector<char> Y ,
std::vector<std::vector<unsigned int> > & tempData);
/** * * @param X X * @param Y Y * @return */
size_t LCS(std::vector<char> &X , std::vector<char> &Y)
{
if(X.size() == 0 || Y.size() == 0)
return 0;
/** */
std::vector<std::vector<unsigned int> > tempData(X.size()+1 , std::vector<unsigned>());
for (int i = 0; i <= X.size(); ++i)
{
for (int j = 0; j <= Y.size(); ++j)
{
if(i == 0 || j == 0)
tempData[i].push_back(0);
else
tempData[i].push_back(UINT_MAX);
}
}
dealLCS(X , Y , tempData);//
return tempData[X.size()][Y.size()];
}
/** * LCS * @param X X * @param Y Y * @param tempData */
unsigned int dealLCS(std::vector<char> X , std::vector<char> Y ,
std::vector<std::vector<unsigned int> > & tempData)
{
if(X.size() == 0 || Y.size() == 0 )
return 0;
//
if(tempData[X.size()][Y.size()] != UINT_MAX)
return tempData[X.size()][Y.size()];
// ，
unsigned int maxLength = 0;
if(X[X.size()-1] == Y[Y.size()-1])//
{
maxLength = dealLCS(std::vector<char>(X.begin() , X.end()-1),\
std::vector<char>(Y.begin() , Y.end()-1),\
tempData)+1;
}
else//
{
unsigned int temp1 = dealLCS(std::vector<char>(X.begin() , X.end()-1),\
std::vector<char>(Y.begin() , Y.end()) , tempData);
unsigned int temp2 = dealLCS(std::vector<char>(X.begin() , X.end()),\
std::vector<char>(Y.begin() , Y.end()-1), tempData);
maxLength = temp1 > temp2 ? temp1 : temp2;
}
tempData[X.size()][Y.size()] = maxLength;
return maxLength;
}
int main(int argc, char const *argv[])
{
char array1[]={'A','B','C','B','D','A','B'};
char array2[]={'B','D','C','A','B','A'};
std::vector<char> X(array1 , array1+sizeof(array1));
std::vector<char> Y(array2 , array2+sizeof(array2));
cout<<"The Lcs length is :"<<LCS(X,Y)<<endl;
while(1);
return 0;
} 
はすべてのサブ問題が解決されたわけではなく、ただ部分子問題を解いただけで元の問題を計算しました.したがって、上から下へ行くか、下から上へ行くかを選択するときは、サブ問題の数と元の問題にどれぐらいの比重があるかを測定して、一番早い解法を選ぶべきです.
再構成の最適解
私達はすべての問題がまず直面するのが一つの選択であることを知っています.そしてこの選択は最適な選択です.私達は一つの配列で対応する選択案を保存します.最適解を保存します.