新郑市网站建设小程,织梦上网站次导航怎么做,最近国际军事军情要闻,泰安网络优化公司当一个问题的规模很大时#xff0c;直接求解往往比较困难。对于这类问题#xff0c;很大一部分是可以采取分而治之的思想来处理的。 分治法是把问题划分成多个子问题来进行处理。这些子问题#xff0c;在结构上跟原来的问题一样#xff0c;但是规模比原来的问题要小。如果得… 当一个问题的规模很大时直接求解往往比较困难。对于这类问题很大一部分是可以采取分而治之的思想来处理的。 分治法是把问题划分成多个子问题来进行处理。这些子问题在结构上跟原来的问题一样但是规模比原来的问题要小。如果得到的子问题还是比较大那么可以接着细分一直细分到可以接受的程度为止。这样就可以用迭代的方法分别求解这些子问题最后再将子问题的解组合起来就可以得到原问题的解。 分治法的设计原理 对于一个规模为n的问题P(n)可以将它分解成k个规模较小的子问题这些子问题互相独立且结构跟原问题的结构相同。在解这些问题的时候又可以对每一个子问题进行进一步的分解直到某一个阈值n0时为止。递归地解这些子问题再把各个子问题的解结合起来就得到原问题的解。这就是分而治之的思想。 分治法的设计步骤 其中n0是一个阈值当问题规模小于等于n0时就不需要再对问题进行分解而直接调用adhoc求解。adhoc是用来直接求解规模最小问题p的子算法。merge用来把所有子问题的解合并成原问题的真正解。 从上面的图中可以看出分支思想的实现有三个步骤 1划分步把输入的问题划分成k个子问题。一般使这k个问题的规模大致相同。 2治理步当问题的规模大于预定义的n0时治理步由k个递归调用组成。 3组合步组合步主要用来将各子问题的解合并成原问题的解。这一步对分治法的实际性能很重要。 转载于:https://www.cnblogs.com/superhuake/archive/2012/07/17/2595751.html
