贪婪算法和分治法

贪婪算法是一个近似求解的算法,得到的结果不一定是最优的解,用来解决NP完全问题等。贪婪算法首先将问题划分成子问题,采用每一步得到最优解来估算得到一个全局最优解,这是一个近似解,怎么滴也是一个挺优秀的结果吧。衡量贪婪算法的优良,一是算法的执行速度,二是算法的计算结果和最优解的相近程度。

分治法是一个精确的算法,前提是问题的划分是均衡的,就是子问题的结果是确定的,那么得到的累计结果和原计算的结果也是一致的。两种算法都是通过划分子问题来减小问题的规模,从而更快的计算。

两种算法思想不同的是,一个得到的是最优解,不一定是最准确的结果。而分治法,是根据对问题的研究,划分子问题合成也可以变成主问题,结果是唯一的。


首页 我的博客
粤ICP备17103704号