Python-分治アルゴリズム

MapReduce(分治アルゴリズムの応用)はGoogleビッグデータ処理の3つの馬車の1つであり、他の2つはGFSとBigtableである.逆インデックス、PageRankコンピューティング、Web分析などの検索エンジンに関する技術に多くの応用がある.
主な思想.
分治アルゴリズムの主な考え方は,サブ問題が境界条件を満たし,再帰を停止するまで,元の問題をいくつかのサブ問題に再帰的に分けることである.サブ問題を1つずつ破壊し(一般的には同じ方法)、解決したサブ問題を統合し、最後にアルゴリズムは元の問題の答えを積層して得る.
分治アルゴリズムの手順

点:再帰的に問題をそれぞれのサブ問題(性質が同じで、互いに独立したサブ問題)に分解する.

治:これらの規模の小さいサブ問題を一つ一つ打ち破る.

合:解決したサブ問題を層ごとに合併し、最終的に元の問題の解を導く.

 
分治法適用の場合

原問題の計算複雑度は問題の規模の増加とともに増加した.

原問題は、より小さなサブ問題に分解することができる.

サブ問題の構造と性質は元の問題と同様であり,互いに独立しており,サブ問題の間には共通のサブ問題は含まれていない.

原問題で分解されたサブ問題の解は、この問題の解に統合することができる.

ぎじふごう

def divide_conquer(problem, paraml, param2,...):
    #          
    if problem is None:
        print_result
        return
    #     
    data=prepare_data(problem)
    #           
    subproblems=split_problem(problem, data)
    #      ，     
    subresult1=self.divide_conquer(subproblems[0],p1,..…)
    subresult2=self.divide_conquer(subproblems[1],p1,...)
    subresult3=self.divide_conquer(subproblems[2],p1,.…)
    #                
    result=process_result(subresult1, subresult2, subresult3,...)