怎样高效解决如下“寻找最大子块”的算法问题（已解决，代码已出，见答案区本人自答）
更新：巧妙的代码已出，见回答后半段。感谢我的同学：欧阳大锤=====================================================================我是本问题的提出者，我已经解决了2维的问题，但我搞不定3维的问题。我解决2维问题是用数据挖掘里比较经典的方法搞定的，方法本身很简单，只不过如果之前不了解相应概念及算法的话看起来比较花时间~ 我简单叙述下我解决2维问题的思路。这要求先要有频繁项集挖掘(frequent itemset minning)的概念，并且了解FP-Tree的概念。这些搜一下就有。 回到我们的矩阵问题上，首先，我将每一行看做频繁项挖掘中的一个transaction，也就是一个购物篮记录；每一列看做是一个商品。那么矩阵元素
为“1”的视为第i个人购买了第j样商品。至此，这个问题的表达形式就成为购物篮数据的表达形式了，故可以用相应领域的一些方法来处理。 针对我的目标：找出最大size的子块，我可以先找出所有的closed itemsets(相应算法在近10年的数据挖掘论文中已经发展成熟)，然后用其行数乘列数得到size，那么这些closed itemsets里，我轻松过一遍就找出最大值了。 但实际上找出所有的closed itemsets也是没有必要的，因为我只想要size最大的那个。故我用自己的启发式方法：(下面的细节就比较繁杂了，不感兴趣的同学就不用看细节啦~)=====================================================================首先建立FPtree
生成FP-tree后，最大size pattern的itemset分布一定是FP-tree的某个分支的连续的子串。且该连续子串的最下面一个节点的count*子串节点个数是全局最大的。如图中以a开头的分支中，patternsize最大的子串为”a-b-c”，size=3*4 = 12。
【怎样高效解决如下“寻找最大子块”的算法问题（已解决，代码已出，见答案区本人自答）】 然而全局的max size不一定在该分支上。如本例中“b-c”的size为2*7=14.此时就应当对FP-tree做一些处理，即嫁接步骤。其思想为考虑过a分支后，将节点a去除，a分支的子分支树将嫁接到null节点上。也就是去除包含a的transactions重新加入FP-tree，形成新的FP-tree树。此时null结点下b节点成为count最大的根节点。于是以b节点为根节点的分支将再次进行以上patternsearching的步骤。重复这个size计算与分支嫁接的过程直到null节点没有任何子结点。输出最大的maxsize与对应的行列集合。
由于在矩阵的pattern中，对pattern的行、列数目有所要求，我们不希望要太过“细长”或者太过“窄宽”的pattern，故对搜寻pattern的行列集合分别有一个数目下限：minrow和mincol。引入这两个量后，FP-tree上的size计算过程可以相应的简化。每次计算不用从根节点开始，而是从第level= mincol的层次节点开始。并且若该节点的count小于minrow时，就不必计算了，也不用继续向下递归（下面的节点count数单调不增），直接返回即可。
算法：1. 初始化全局变量maxsize = 0。设置minrow, mincol。初始化全局集合colset = {}，rowset = {}。设置根节点为从null结点向下的根节点中count最大的节点。2. 对于当前节点，首先判断其count是否小于minrow，是的话直接放弃计算该节点以及其子分支；否则再看其节点level是否大于等于mincol，若小于的话跳到4步。3. 用其节点的计数乘以层数可得size=count*level. 判断size\u0026gt;maxsize? 若是则有maxsize=size，且记录相应colset,rowset。4. 若该节点无子结点则返回。否则对所有子结点，分别递归调用步骤3、4，即size的计算步骤，根据size与maxsize的关系，保持或更新maxsize以及对应的colset，rowset。5. 至此得到null节点下一个分支遍历计算完成后的全局变量maxsize, colset, rowset。开始嫁接：将刚计算完的分支根节点减去，将其子分支嫁接到null节点上。取null节点下count最大的节点作为根节点。转到步骤2。
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 蟹爪兰叶子软塌，难复花，“根源”在这里，解决后开花一茬接一茬
- 贵州在建骨干水源工程达到465座有效解决工程性区域性缺水问题
- 长春社区开设助老餐厅探索解决老人“吃饭难”
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾