前言 分治思想自古就有,在《孙子兵法》中有这么一句话:凡治众如治寡,分数是也:斗众如斗寡,形名是也。 问题描述 今天我们讲的是分治法,首先来了解一下分治法的定义:把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并,这就是分治法。 解决方案 简单来说,分治法的基本思想就是:把一个大的问题分解成若干个小问题,求出若干个小问题的解并将其合并,得到的就是大问题的解。但是,并不是所有的问题都可以用分治法来解决,从它的基本思想我们就可以看出,能用分治法解决的问题一定具有以下特征: 就是说子问题之间不包含公共的子问题,如果包含了公共的子问题,那么求出的解就有部分是重复的,合并之后的解肯定是不正确的。 结语 我们简单介绍了分治法,通过以上讲解我们可以看到分治和递归宛如一对孪生兄弟,有分治法的地方就有递归的身影。因此要想运用好分治法一定要先理解运用好递归,遇到问题方能分而治之,逐个击破。 作者:唐雷清 实习编辑:衡辉 稿件来源:深度学习与文旅应用实验室(DLETA) |
|