分治的逻辑学描述

分治的逻辑学描述

https://bigdata.oden.utexas.edu/project/divide-conquer-methods-for-big-data-analytics/

问题分解：

P = P1 + P2 +..PN

问题求解：

F(P) = 

F(P1 + P2 +..PN)=

F1(P1) + F2(P2) +..Fn(PN);

设问题的解决方案为 Y=F(X)，其中 X 为问题的输入集合，F是问题的处理方法，Y是问题的解。将X拆分成多个子集以后，设这些子集的集合为 X={Xi ∣i≥1,i>n}，则 X 满足以下条件：

X1 ++X2 ++...++Xn =X

在拆分以后，分治法对每个子集独立处理，即 Yi =F(Xi )，其中 Xi ∈X，则最终结果为：

Y=Marge(Y1 ,Y2 ,...,Yn )

其中，Merge函数用于将所有的子结果 Yi 进行合并的函数。

 https://blog.csdn.net/weixin_43145361/article/details/89510447

分治策略一般性描述

把上面的设计思想加以归纳,可以得到分治算法的一般描述.设P是待求解的问题,|P|代表问题的输入规模,一般的分治算法Divide-and-Conquer伪码描述如下:

算法 Divide-and-Conquer(P)

1. if |P| < c or |P| = c then S(P)

2. divide P into P1,P2,P3,...,Pk

3. for i = 1 to k do

4. yi ← Divide-and-Conquer(Pi)

5.Return Merge(y1,y2,y3,....,yk)