分治法与回溯法的思考

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

共同的递归性质

在广义上来说,所有递归的算法都属于分治法。无非是将问题分解成一个规模更小的问题,还是将问题分解成若干个,甚至和输入规模多项式级别的子问题。那么对于前者,有些作者称作是减治法,后者称作分治法。

那么对于回溯法(以深度优先搜搜方式进行)来说,目前为止我见过的都是通过递归的形式来实现的,那么从这个意义上来讲,回溯算法就是分治法的一种。

回溯状态的有无

再说,之所以称作是回溯法,是因为在搜索的过程中需要回溯到问题的某个状态,所以这往往需要保存回溯时的一些状态属性。然而,分治法通常并不需要考虑回溯状态的保存。

分解问题的规模

分治法往往是将问题分解成若干个子问题的形式,然而回溯法往往是将问题分解成规模更小的一个子问题。由于分治法将问题分解成若干个子问题,故当前问题的解需要依赖于若干个子问题,也就是若干个搜索路径的解,所以重点在于如何合并子问题的解;而然回溯法问题规模就为1个,当前的搜索路径的问题触碰到边界条件时,即可得到当前搜索路径的问题的解,并不需要合并,或者说合并很简单。

分治法可变成复杂的回溯法

如果分治法保留了每个问题的可回溯的状态,并利用了这些状态,尽管这非常的不容易实现,因为某个问题的回溯的状态可能需要依赖很多其子问题的状态。如果成功保存了这些回溯状态,那么这个时候,分治法就成了复杂的回溯法。


文章来源:胡小旭 => 分治法与回溯法的思考


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: 技术, 算法 | 标签: , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。