算法->分治法-电子工程世界

分享到: 微博; QQ; 微信; LinkedIn

一、基本概念

   在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

    任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

二、基本思想及策略

   分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

   分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

   如果原问题可分割成k个子问题，1
三、分治法适用的情况

   分治法所能解决的问题一般具有以下几个特征：

    1) 该问题的规模缩小到一定的程度就可以容易地解决

    2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

    3) 利用该问题分解出的子问题的解可以合并为该问题的解；

    4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

四、分治法的基本步骤

分治法在每一层递归上都有三个步骤：

   step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

   step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

   step3 合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：

    Divide-and-Conquer(P)

    1. if |P|≤n0

    2. then return(ADHOC(P))

    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk

    4. for i←1 to k

    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题

    7. return(T)

    其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。

五、分治法的复杂性分析

    一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为 k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：

T（n）= k T(n/m)+f(n)

    通过迭代法求得方程的解：

   递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当 mi≤n 六、可使用分治法求解的一些经典问题

（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择

（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
七、依据分治法设计程序时的思维过程

   实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
1、一定是先找到最小问题规模时的求解方法
2、然后考虑随着问题规模增大时的求解方法
3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

关键字：算法分治法引用地址：算法->分治法

上一篇：数据结构->队列（JAVA实现）
下一篇：算法—>回溯法

推荐阅读最新更新时间：2024-03-16 14:02

仿人足球机器人目标定位技术与追踪算法改进

　　对于仿人足球机器人来说，视觉功能是极其重要的。在足球机器人的各种关键技术中，是应用范围最广，最为基本的技术之一。移动机器人视觉的研究主要集中在颜色模型建立、目标识别、定位以及跟踪等方面。仿人机器人视觉系统的识别与定位算法也是目前的研究热点，目标的实时识别与定位是足球机器人在足球赛中精确踢球的前提。文章主要是针对目前足球机器人在视觉系统上所存在的问题进行了颜色模型建立及目标定位算法的改进，加入了目标追踪算法，确保目标识别与定位的准确。在ｉＫｉｄ足球机器人上进行试验并调试，试验结果具有较好的实时性和准确性。　　引言　　在RoboCup仿人足球机器人比赛中，视觉是其获得外界信息的主要途径，机器人通过摄像头去采集周围环境

[机器人]

用汇编语言实现BCH解码校验算法

摘要：介绍数据传输中BCH解码校验用汇编语言实现的算法。算法包含BCH码的差错检验、差错位查找和差错纠正，同时列出相关主要子程序清单并予说明。关键词：BCH解码校验算法汇编语言数据传输通信中，常常因传输差错造成误码错码，尤其在无线通信中，空中的突发或随机干扰噪声会造成编码差错。为了提高传输的正确率，往往采用一些校验方法，以检验纠正传输差错。通信中校验的方法很多，其中的BCH编码有其独特的优点：不仅可以检纠突发差错，还能检纠随机差错，被广泛地采用在微机级的通信中。但对更低层的单片机级的数据传输通信纠错，往往采用奇偶校验等简单的校验方法。BCH校验因其算法复杂，尤其是动态实时的无线通信中，单片机的通信往往无法采用BCH解

[应用]

移动机器人3种常见视觉算法

算法一：深度信息提取其原理是使用两个平行的相机，对空间中的每个点三角定位。通过匹配左右两个相机中成像点的位置，来计算对应三维点在空间中的距离。机器人想要通过若干幅图像来获取目标的三维坐标，双目视觉技术中更为重要的工作是对图像执行匹配，首先明确物体在左右图像的相互匹配的点，然后获得每一点视差以及深度信息。双目立体视觉有设备简单且价格低廉,精度高且速度快,无需接触物体即可计算距离和深度信息等优点,其在无人机电力线巡检以及工业建筑机器人中都有重要的应用。算法二：定位导航机器人导航是一个比较复杂的系统，涉及技术如下：视觉里程计VO；建图，利用VO和深度图；重定位，从已知地图中识别当前的位置；闭环检测，

[嵌入式]

可用于单片机的DES加密算法

在写设计文档，突然被提起传输的数据最好还是加密！惶恐！你知道吗？单片机算DES，不是我疯掉就是单片机疯掉！然后搜了下，感谢各位神仙~居然有这么多实现过的，下面是一例。据说是已经测试通过的，最早为8位单片设计的，我也还没测，先找来放着，看着也心安。 //以下是des.c文件全部： //密钥： B4 31 5B 86 9D 7D FA A2 //数据： 1F AD 61 A5 F7 19 77 14 //DES加密结果：4C 78 E9 1A F2 DA 9C D3 const uint8_t initial_tr = { 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35,

[单片机]

Waymo合作DeepMind 将自动驾驶AI算法开发速度提升1至2倍

据外媒报道，谷歌母公司Alphabet 旗下自动驾驶子公司 Waymo 的自动驾驶汽车与引导普通汽车的“大脑”有一些共同之处：其智能都由进化推动发展。目前，Waymo的工程师就正与DeepMind（也是Alphabet旗下子公司，专注于AI）的研究人员合作，寻找一种更加高效的方法，培训和调整Waymo的自动驾驶算法。（图片来源：Waymo官网）研究人员们采用了一种称为“基于群体进行训练”（PBT）的技术，此前DeepMind研发了该技术，以提升视频游戏的算法。PBT技术的灵感来自于生物进化，通过让候选代码从算法群中抽取“最合适”的样本（最有效执行给定任务的样本），加速选出特定任务中用到的机器学习算法和参数。以

[汽车电子]

Waymo合作DeepMind 将自动驾驶AI<font color='red'>算法</font>开发速度提升1至2倍

图像自适应分段线性拉伸算法的FPGA设计

0 引言由于红外图像的成像机理以及红外成像自身的原因，红外图像有对比度低、图像较模糊、噪声大等特点。因此抑止噪声，提高图像信噪比，以及调整红外图像对比度，以利于后续图像分析、目标识别或跟踪，必须对红外图像进行增强处理。另外，在其他场合，若采用人机交互方式，则必须对原始图像进行预处理，改善图像视觉效果，使其更适合人机进一步的分析和处理。图像增强从作用域出发，分为空间域增强和频率域增强两种。频率域是一种间接增强的方法，由于存在域之间的变换和反变换，计算复杂，难以满足实时性要求。自适应分段线性拉伸算法是一种空间域图像增强方法，直接对图像像素灰度进行操作，由于运算过程简单、实现方便，目前的图像增强预处理电路大多选用这种算法

[嵌入式]

前馈-改进PID算法在智能车控制上的应用

1 引言智能车系统是一个时变且非线性的系统，采用传统PID算法的单一的反馈控制会使系统存在不同程度的超调和振荡现象，无法得到理想的控制效果。本文将前馈控制引入到了智能车系统的控制中，有效地改善了系统的实时性，提高了系统的反应速度；并且根据智能车系统的特点，对数字PID算法进行了改进，引入了微分先行和不完全微分环节，改善了系统的动态特性；同时，利用模糊控制具有对参数变化不敏感和鲁棒性强的特点，本文将模糊算法与PID算法相结合，有效地提高了智能车的适应性和鲁棒性，改善了系统的控制性能。 2 改进PID算法智能车的控制是由飞思卡尔公司的S12芯片完成，所以对智能车的控制要采用计算机控制方法。本文针对

[嵌入式]

相位干涉仪测向算法及其在TMS320C6711上的实现

摘要：对实施被动无源测向定位的主要工具之一的相位干涉仪进行了较为详细和系统的研究，给出了一维相位干涉仪的基本关系式，分析了五通道相位干涉仪测向定位算法及其性能指标?熏对解相位模糊问题进行了探讨。最后，在高速浮点数字信号处理器TMS320C6711系统上实现了五通道相位干涉仪测向定位算法，达到了性能指标及实时实现。关键词：相位干涉仪测向定位相位模糊定位误差实时处理相位干涉仪测向技术广泛应用于天文、雷达、声纳等领域。将干涉仪原理用于无线电测向始于上世纪五十年代和六十年代，随着数字信号处理器的出现，通过数字信号处理器来实现高精度实时测向成为可能。本文在对一维和二维相位干涉仪进行研究的基础上给出了五通道相位干涉仪的基本

[嵌入式]