[LeetCode]并行与问题分解技术

问题描述

把n个数分为k个非空子集，有多少种分法?

思路分析

这里提供基于加法原理的分析，要解决一个原问题，可以把这个原问题分解成n个独立不相交且完备的小问题，则原问题的解是小问题解的和。在该问题中，可以依据第一个集合中放多少个数将原问题分解成小问题。

代码实现

问题分析

1.递归原理

针对main函数中的调用group(4,3),可以得到下列递归调用过程。这里用(n-i,k-1)(一个元组)代替表示group(n-i,k-1)，用j(一个数)代替表示c(n,i),则

(4,3)

<-(3,2)*4+(2,2)*6

<-(2,1)*3+(1,1)*3+(1,1)*2

<-(1,0)*2+(0,0)*1+(0,0)*1+(0,0)*1=0+1+1+1

代码中的16,17解决的是上述过程的最后一步，21,22解决的是上述过程中的展开操作，24解决的是箭头。考虑到递归调用栈，每个箭头表示一个函数地址。使用mem的目的是为了记住运算过程中间结果，同时可以解决递归过程重复计算的问题。注意上述代码中，整个过程的计算点在16，17行非常简单的两行代码！问题的求解是按照自顶向下问题分解后自底向上问题计算的过程。递归本身的优点是考虑问题的方式可以很简单，写出的代码很简洁，但是缺点是函数占用空间大，函数功能受栈空间限制，而且如果不采取额外的措施，会导致重复计算的问题，这里是一个例子，类似在斐波那契数列的计算问题中同样存在。

2.并行思考

结合上述分析，我们换个角度思考问题。

(4,3)=(3,2)*4+(2,2)*6

(3,2)和(2,2)并行求解。

又因为(3,2)=(2,1)*3+(1,1)*3,故(2,1)和(1,1)并行求解

这样是否是一个递归分解并行呢?而且具有现实意义。(太遗憾了，早上写到这里，下午就看到其实递归并行化已经有很多工作了！也能说得通，大二的时候就想到过说并行化，不过没有思考下去。)注意，这里并行的子问题规模不尽相同。

参考文献：

1.递归，加法原理，如何分解问题?

这篇博客是针对该文章中提出的一道题目的深入分析，同时该博客可以作为想要进一步刷题的参考资料。

2.Python基础–排列组合的实现

代码的实现需要排列组合的基础数学知识，这里给出了一个用python实现的排列组合代码，简单优雅。

3.Parallelization of Neural Network Training using Model Averaging and Butterfly Mixing