`
fehly
  • 浏览: 248448 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

分治法的基本思想

阅读更多

       分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同,递归地解这些子问题,然后将各个子问题的解合并得到原问题的解。它的一般算法设计模式如下:

                  

divide-and-conquer(P)
{
         if(|P|<=n0)adhoc(P);
        divide P into smaller subinstances P1,P2,...Pk;
         for(i=1,i<=k,i++)
             yi=divide-and-conquer(Pi);
         return merge(y1,...yk);
}

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

       根据分执法的分割原则,应把原问题分为多少个子问题才比较适宜?每个子问题是否规模相同或怎样才为适当?这些问题很难给予肯定的回答,但人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同,即将一个问题分成大小相等的k个子问题的处理方法是行之有效地,或许问题可以取k=2,这种使子问题规模大致相等的做法是出自一种平衡子问题的思想,它几乎总是比子问题规模不等的做法要好。

       从分治法的一般设计模式可以看出,用它设计出的算法一般是递归算法,因此分治法的计算效率通常可以用递归方程式进行分析。一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。为方便起见,设分解阈值n0=1,且adhoc解规模为1的问题耗费1个单位时间.另外,再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需要用f(n)个单位时间,如果用T(n)表示该分治法divide-and-conquer(P)解规模为  |P|=n的问题所需的计算时间则有

                                                  O(1)                    n=1

                                      T(n)=   kT(n/m)+f(n)        n>1

 

分享到:
评论

相关推荐

    矩阵乘法(分治法)内附实验报告

    通过这样的实验,我们不仅可以理解分治法的基本思想,还能深入掌握矩阵乘法的优化技术,这对于提高计算密集型任务的效率至关重要。同时,C++的编程实践有助于提升我们的编程能力和问题解决能力。在未来的学习和工作...

    java编程实现分治法归并排序

    #### 分治法基本思想 分治法是一种将大问题分解成小问题,并通过解决这些小问题来解决原始问题的方法。这种方法的基本步骤包括: 1. **分解**:将一个问题分解为若干个规模较小的相同问题。 2. **解决**:如果子...

    分治法求两个大整数相乘

    ### 分治法求两个大整数相乘 #### 一、问题背景及描述 在计算机科学领域,处理大整数的运算是一项常见的...本文介绍了分治法的基本思想,并给出了具体的实现过程,希望能够帮助读者更好地理解并应用这一算法策略。

    分治法的应用

    #### 二、分治法的基本思想 对于任何可以用计算机求解的问题,其计算时间通常与问题的规模成正比。当问题规模较小时,可以直接解决;而当问题规模较大时,直接解决可能变得非常困难。这时,分治法的设计思路就是将...

    java 快速排序 折半查找的界面实现 (递归与分治法)

    它的主要思想是分治法,即将大问题分解为小问题来解决。在快速排序中,我们选择一个基准值(pivot),然后将数组分为两部分:一部分包含所有小于基准的元素,另一部分包含所有大于或等于基准的元素。这个过程通过...

    实验4 分治法1

    1. **深刻理解分治法的设计思想**:分治法的基本思想是将一个复杂问题划分为两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。通常涉及三个步骤:分解、解决和...

    分治法求最近点对

    1. **分治策略**:理解分治法的基本思想,包括分解、解决、合并这三个步骤。学习如何将最近点对问题划分为子问题,如矩形区域内的最近点对查找。 2. **最近点对算法**:研究不同的算法,如线性扫描、排序后扫描、...

    分治法求最大值的C++实现

    分治法的基本思想是将原问题划分为两个或更多的相同或相似的子问题,递归地求解子问题,然后将子问题的解合并得到原问题的解。这一过程可以被概括为三个步骤: 1. **分解**:将问题分解成两个或更多更小的子问题。 ...

    最近对问题 分治法 ——C语言代码

    分治法是计算机科学中一种重要的算法设计策略,它的核心思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。在C语言中实现分治法,...

    分治法求01背包问题c语言

    在01背包问题中,分治法的应用并不直接,但可以通过动态规划来实现一种“局部分治”的思想。 C语言是一种广泛应用的高级编程语言,具有简洁、高效的特点,适合实现各种算法。在C语言中实现01背包问题,需要理解并...

    分治法求二叉树的同构问题

    分治法是一种递归的算法设计策略,其基本思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。对于二叉树的同构问题,我们同样可以采用...

    分治法求最近点对问题

    - 实际运行时间与理论预测基本一致,表明分治法的效率显著优于蛮力法。 #### 性能对比 - **蛮力法**:随着点数增加,运行时间呈平方增长趋势。 - **分治法**:随着点数增加,运行时间的增长远低于蛮力法。 #### ...

    分治法选讲=课件

    ### 分治法选讲知识点详解 #### 一、分治法概述 - **定义**: 分治法是一种重要的算法思想,其核心在于将一个大问题分解为若干个子问题,通过解决这些子问题来最终解决原始问题。这种方法尤其适用于那些可以通过...

    分治法求最值

    首先,让我们理解分治法的基本步骤: 1. **分解**:将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。 2. **解决**:若子问题足够小,可以直接求解,否则递归地解各个子问题。 3. **合并**:将...

    最大字段和问题 分治法.cpp.rar

    分治法的基本思想是将一个复杂的问题分解为两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。对于最大子序列和问题,我们可以按照以下步骤进行: 1. **分割**:...

    分治法求大整数乘法(可运行)

    “分治法”是算法设计的一种基本思想,其主要步骤包括分解、解决和合并。对于大整数乘法,分治法首先将两个大数各自拆分为较小的部分,然后递归地计算这些部分的乘积,最后将所有部分的乘积组合起来得到最终结果。...

    分治法大整数乘法课件

    分治法的基本步骤** - **分解(Divide)**:将原问题分解为若干个规模较小但结构与原问题相同的子问题。 - **求解(Conquer)**:递归地解决这些子问题,通常子问题的规模小到可以直接求解。 - **合并(Combine)**...

    修正的分治法求最近点对

    在求解最近点对时,分治法的基本思想是通过划分空间来减少搜索的范围。 首先,我们对所有点按照x坐标进行排序,这样可以确保处理的每个子区间内的点x坐标都是有序的。接着,选择一个中间点,将其作为分割线,将点集...

    算法设计策略 - 05-2 分治法.pdf

    分治法的基本思想、分析技术、降低复杂度的途径、数据结构以及应用都是本篇文档讲述的重点内容。 首先,分治法的基本思想可以概括为三点:把问题分成若干个小问题、递归解决这些小问题、合并小问题的解以得到原问题...

    分治法解方程_分治法_

    这种策略的基本思想是将一个大问题分解成若干个规模较小、相互独立、与原问题形式相同的子问题,然后分别解决子问题,最后将子问题的解合并得到原问题的解。分治法通常包括三个主要步骤:**分解、解决和合并**。 在...

Global site tag (gtag.js) - Google Analytics