导航:首页 > 源码编译 > 分治算法特点

分治算法特点

发布时间:2024-03-19 11:30:20

算法设计与分析|5个算法

1)分治法

对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小),则直接解决;否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

2)回溯法(深度优先)

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当搜索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。

3)贪心法

总是做出在当前来说是最好的选择,而并不从整体上加以考虑,它所做的每步选择只是当前步骤的局部最优选择,但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解,因此其耗费时间少,一般可以快速得到满意的解,但得不到最优解。

4)动态规划法

在求解问题中,对于每一步决策,列出各种可能的局部解,再依据某种判定条件,舍弃哪些肯定不能得到最优解的局部解,在每一步都经过筛选,以每一判瞎步都是最优解来保证全局是最优解。

5)分支限界法(广度优先)

分治算法求出的子问题是互相独立的。

动态规划算法具有最优子结构性质和重叠子问题性质。

贪心算法不追求最优解,只求可森早行解,因此不具备最优子结构的特性。

回溯算法把问题的解空间转化成图或者树结构,然后使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可此冲雀行解或者最优解。

分支限界算法类似于回溯算法,它以广度优先方式搜索解空间树。

㈡ 最通俗、简单的分治算法思想

分治算法的基本思想是将一个计算复杂的问题分为规模较小,计算简单的小问题求解 ,然后综合各个小问题,而得到最终问题的答案。分治算法的执行过程如下:
♦对于一个规模为N的问题,若该问题可以容易地解决(比如说规模N较小),则直接解决,否则执行下面的步骤。
♦将该分解为M个规模较小的子问题,这些子问题互相独立,并且与原问题形式相同。
♦递归地解这些子问题。
♦然后,将各子问题的解合并得到原问题的解。

问:一个袋子里有30个硬币,其中一枚是假币,并且假币和真币一模一样,肉眼很难分辨,目前只知道假币比真币重量轻一点。请问如何区分出假币呢? 可以采用递归分治的思想来求解这个问题:
♦首先为每个银币编号,然后可以将所有的银币等分为两分,放在天平的两边。这样就将区分30个硬币的问题,变为区别两堆硬币的问题。
♦因为假银币的分量较轻,因此天平较轻的一侧中一定包含假银币。
♦再将较轻的一侧中的硬银币等分为两分,重复上述的做法。郑念绝
♦直到剩下2枚高拆硬银币,可用天平直接找出假银币来。

运行结果
分治喊姿算法求解假的银币问题!
请输入硬币的数量:13
请输入每个硬币的质量:
第1个:2
第2个:2
第3个:2
第4个:2
第5个:2
第6个:2
第7个:2
第8个:2
第9个:2
第10个:1
第11个:2
第12个:2
第13个:2
第10个为假币!!

阅读全文

与分治算法特点相关的资料

热点内容
爬山算法相关题目 浏览:720
vc编程大全 浏览:114
excel表格单列数据加密 浏览:646
给同事的解压话语 浏览:990
linux关闭网卡命令行 浏览:452
史上最漂亮程序员 浏览:768
java实现excel的导入 浏览:758
光遇账号如何转移安卓 浏览:266
5分之13除以26的算法 浏览:342
兰州安宁区买解压包子 浏览:641
php接收图片代码 浏览:668
hci命令 浏览:662
福建服务器大区云空间 浏览:840
笔杆子程序员 浏览:745
手机软件易验证加密 浏览:589
文档加密只读模式也不能看到 浏览:431
把jpg转换成pdf的软件 浏览:874
linuxeth0mac 浏览:192
windows编程知乎 浏览:442
压缩工期超过40 浏览:249