MITアルゴリズムの導論--第三講.The Divide-and-Conquer
このコラム(Algorithms)のMITアルゴリズム導論テーマは、ネット易公開課MITアルゴリズム導論に対する個人の学習心得とメモです.すべての内容はMIT公開課Introduction to AlgorithmsのCharles E.LeisersonとErik Demaine先生の説明から来ています.(http://v.163.com/special/opencourse/algorithms.html)
第三節------分治法The Divide-and-Conquer
この授業の主な内容は分治法の思想を紹介し、いくつかの分治法思想を応用するアルゴリズムの例を紹介し、前の授業の主な定理方法と結びつけてアルゴリズムの性能を分析することである.
分治法とは、分を分けて治し、それぞれを撃破することである.一般的なアルゴリズムの設計手順は次のとおりです.
1、Divide.すなわち、問題をいくつかのサブ問題に分割する.
2、Conquer.すなわち、再帰的な方法によって、第1段階の中性子問題をそれぞれ解決する.
3、Combine.すなわち,各サブ問題の結果を統合すると,問題全体の解決策が得られる.
一、集計ソート
下図に示すように集計ソートにおける分治法思想であり,設計思想に基づいて集計ソートの効率再帰式が容易に得られる.再帰式が得られると,主定理法を満たすCase 2が容易に発見されるため,帰着並べ替えの複雑さはΘ(nlgn).
二、二分検索
下図に示すように二分探索における分治法の考え方であり,同理的に再帰式が得られると,主定理法を満たすCase 2が容易に発見されるため,集計ソートの複雑さはΘ(lgn).
三、乗方a^n乗数a^nを計算するために、
従来のやり方(Naive algorithmという)はループにn回乗算し,アルゴリズム効率はΘ(n).でも採用すれば
分治法の思想、アルゴリズムの効率はΘ(lgn)を下図に示します.
四、フィボナッチ数列の計算
Fibonacci数列もよく知られているはずで、その再帰定義は上図に示すようになっています.フィボナッチ数列を解く方法も多く、主に以下のようなものがある.
1.単純再帰アルゴリズム(Naive recursive algorithm)
このときのアルゴリズム効率はΩ(φ^n)、指数レベル.内φ = (1 + 5^½)/2、すなわち黄金分割比率.
2.素朴再帰二乗アルゴリズム(Naive recursive squaring)
このアルゴリズムは主にフィボナッチ数列の数学的性質に基づいている.この性質は,フィボナッチ数列F(n)がφ^n/ 5^½下向きに整える.このように,問題の解は乗を求める問題になるので,アルゴリズムの効率はΘ(lgn).
しかし,この方法はあまり頼りにならないが,主にnが大きい場合,ハードウェアの制限計算機における浮動小数点演算により得られた結果が実際の値と誤差を生じる.
3.ボトムアップアルゴリズム(Bottom-up)
1における単純な再帰アルゴリズムを考慮すると,F(n)を解くためには,F(n−1)とF(n−2)を同時に再帰的に解く必要があり,これは明らかに大量の繰返し作業を行った.このような冗長性は、下から上へのアルゴリズムを用いることで回避できる.F(n)を計算するには、F 0、F 1、F 2の順に計算します...Fn,このときFnを計算するには,最初の2つの結果を利用すればよいので,アルゴリズム効率が向上する.Θ(n).
4.再帰二乗アルゴリズム(Recursive squaring)
このアルゴリズムも定理,定理および証明過程に基づいて下図に示す.このように,問題の解は行列の乗方問題となり,アルゴリズム効率が向上する.Θ(lgn).
五、行列乗算
上の図に示すようにマトリクス乗算問題の説明であり、マトリクスの乗算に関する現在の主な方法は以下の通りである.
1.一般的なアルゴリズム(Standard algorithm)
行列の乗算は,まず次のようなアルゴリズムが考えられるが,このアルゴリズムの効率はΘ(n^3).
2.分治法アルゴリズム(Divide-and-conquer algorithm)
マトリクス乗算には分治法が用いられ,第一感覚的にアルゴリズムの効率を効果的に向上させることができるはずである.下図に示すように,分治法スキームと,このアルゴリズムの効率解析を行う.図から分かるように、アルゴリズム効率はΘ(n^3).アルゴリズムの効率は向上しなかった.
3.Strassenアルゴリズム(Strassen's algorithm)
2の分治法案ではアルゴリズムの効率を効果的に高めることができないことから,アルゴリズムの効率を高めるには,主定理法から2の再帰式における係数8を減らす方法が必要であることが分かる.Strassenは係数を7に減らす分治法を提案し,下図に示す.
Strassenがどのようにこの案を考え出したのか想像するのは難しいが,元の再帰式の係数を8から7に減らしたのは確かだ.次の図は、アルゴリズムのアルゴリズム効率分析です.
これによりStrassenアルゴリズムは行列の乗算効率をΘ(n^2.81).この2.81は数値的にそれほど向上していないように見えるが,アルゴリズム効率自体が指数関数的であるため,nが比較的大きい場合(n≧30が現代の機械上)Strassenアルゴリズムの優位性は明らかである.
もちろん,マトリクス演算に関する最適化アルゴリズムはたくさんある.理論的に行列乗算の効率が最も優れているのは、Θ(n^2.376…).しかし、この多くの最適化アルゴリズムの中で、Strassenアルゴリズムは最も簡単です.
Introduction to Algorithmsのより多くの学習資料が更新されますので、このブログと新浪微博Sheridanに注目してください.
第三節------分治法The Divide-and-Conquer
この授業の主な内容は分治法の思想を紹介し、いくつかの分治法思想を応用するアルゴリズムの例を紹介し、前の授業の主な定理方法と結びつけてアルゴリズムの性能を分析することである.
分治法とは、分を分けて治し、それぞれを撃破することである.一般的なアルゴリズムの設計手順は次のとおりです.
1、Divide.すなわち、問題をいくつかのサブ問題に分割する.
2、Conquer.すなわち、再帰的な方法によって、第1段階の中性子問題をそれぞれ解決する.
3、Combine.すなわち,各サブ問題の結果を統合すると,問題全体の解決策が得られる.
一、集計ソート
下図に示すように集計ソートにおける分治法思想であり,設計思想に基づいて集計ソートの効率再帰式が容易に得られる.再帰式が得られると,主定理法を満たすCase 2が容易に発見されるため,帰着並べ替えの複雑さはΘ(nlgn).
二、二分検索
下図に示すように二分探索における分治法の考え方であり,同理的に再帰式が得られると,主定理法を満たすCase 2が容易に発見されるため,集計ソートの複雑さはΘ(lgn).
三、乗方a^n乗数a^nを計算するために、
従来のやり方(Naive algorithmという)はループにn回乗算し,アルゴリズム効率はΘ(n).でも採用すれば
分治法の思想、アルゴリズムの効率はΘ(lgn)を下図に示します.
四、フィボナッチ数列の計算
Fibonacci数列もよく知られているはずで、その再帰定義は上図に示すようになっています.フィボナッチ数列を解く方法も多く、主に以下のようなものがある.
1.単純再帰アルゴリズム(Naive recursive algorithm)
このときのアルゴリズム効率はΩ(φ^n)、指数レベル.内φ = (1 + 5^½)/2、すなわち黄金分割比率.
2.素朴再帰二乗アルゴリズム(Naive recursive squaring)
このアルゴリズムは主にフィボナッチ数列の数学的性質に基づいている.この性質は,フィボナッチ数列F(n)がφ^n/ 5^½下向きに整える.このように,問題の解は乗を求める問題になるので,アルゴリズムの効率はΘ(lgn).
しかし,この方法はあまり頼りにならないが,主にnが大きい場合,ハードウェアの制限計算機における浮動小数点演算により得られた結果が実際の値と誤差を生じる.
3.ボトムアップアルゴリズム(Bottom-up)
1における単純な再帰アルゴリズムを考慮すると,F(n)を解くためには,F(n−1)とF(n−2)を同時に再帰的に解く必要があり,これは明らかに大量の繰返し作業を行った.このような冗長性は、下から上へのアルゴリズムを用いることで回避できる.F(n)を計算するには、F 0、F 1、F 2の順に計算します...Fn,このときFnを計算するには,最初の2つの結果を利用すればよいので,アルゴリズム効率が向上する.Θ(n).
4.再帰二乗アルゴリズム(Recursive squaring)
このアルゴリズムも定理,定理および証明過程に基づいて下図に示す.このように,問題の解は行列の乗方問題となり,アルゴリズム効率が向上する.Θ(lgn).
五、行列乗算
上の図に示すようにマトリクス乗算問題の説明であり、マトリクスの乗算に関する現在の主な方法は以下の通りである.
1.一般的なアルゴリズム(Standard algorithm)
行列の乗算は,まず次のようなアルゴリズムが考えられるが,このアルゴリズムの効率はΘ(n^3).
for i ← 1 to n
do for j ← 1 to n
do c[i][j] ← 0
for k ← 1 to n
do c[i][j] ← c[i][j] + a[i][k]⋅ b[k][j]2.分治法アルゴリズム(Divide-and-conquer algorithm)
マトリクス乗算には分治法が用いられ,第一感覚的にアルゴリズムの効率を効果的に向上させることができるはずである.下図に示すように,分治法スキームと,このアルゴリズムの効率解析を行う.図から分かるように、アルゴリズム効率はΘ(n^3).アルゴリズムの効率は向上しなかった.
3.Strassenアルゴリズム(Strassen's algorithm)
2の分治法案ではアルゴリズムの効率を効果的に高めることができないことから,アルゴリズムの効率を高めるには,主定理法から2の再帰式における係数8を減らす方法が必要であることが分かる.Strassenは係数を7に減らす分治法を提案し,下図に示す.
Strassenがどのようにこの案を考え出したのか想像するのは難しいが,元の再帰式の係数を8から7に減らしたのは確かだ.次の図は、アルゴリズムのアルゴリズム効率分析です.
これによりStrassenアルゴリズムは行列の乗算効率をΘ(n^2.81).この2.81は数値的にそれほど向上していないように見えるが,アルゴリズム効率自体が指数関数的であるため,nが比較的大きい場合(n≧30が現代の機械上)Strassenアルゴリズムの優位性は明らかである.
もちろん,マトリクス演算に関する最適化アルゴリズムはたくさんある.理論的に行列乗算の効率が最も優れているのは、Θ(n^2.376…).しかし、この多くの最適化アルゴリズムの中で、Strassenアルゴリズムは最も簡単です.
Introduction to Algorithmsのより多くの学習資料が更新されますので、このブログと新浪微博Sheridanに注目してください.