`
128kj
  • 浏览: 604183 次
  • 来自: ...
社区版块
存档分类
最新评论

分治算法

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

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

    如果原问题可分割成k个子问题(1<k≤n),且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
 
  二、分治法的适用条件
分治法所能解决的问题一般具有以下几个特征:
(1)该问题的规模缩小到一定的程度就可以容易地解决;
(2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
(3)利用该问题分解出的子问题的解可以合并为该问题的解;
(4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

  上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

三、分治法的基本步骤
分治法在每一层递归上都有三个步骤:
(1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
(2)解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
(3)合并:将各个子问题的解合并为原问题的解。
    根据分治法的分割原则,原问题应该分为多少个子问题才较适宜?各个子问题的规模应该怎样才为适当?这些问题很难予以肯定的回答。 但人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。
换句话说,将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想,它几乎总是比子问题规模不等的做法要好。 分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显, 有些问题合并方法比较复杂,或者是有多种合并方案;或者是合并方案不明显。 究竟应该怎样合并,没有统一的模式,需要具体问题具体分析。

四、例二分检索查找最大值代码

/**   
 * 使用分治法的思想查找最大值   
 *    
 * @author Administrator   
 *    
 */   
public class FindMax {   
  
    // 返回最大值的方法   
    public int returnMax(int array[]) {   
        int length = array.length;   
        int first;   
        int second;   
        if (length == 1) {   
            return array[0];   
        } else if (length == 2) {   
            return Math.max(array[0], array[1]);   
        } else if (length < 1) {   
            return 0;   
        } else {   //这里将一个数组一分为二,然后各个求解   
            first = length / 2;   
            second = length - length / 2;   
            int firstArray[] = new int[first];   
            int secondArray[] = new int[second];   
            for (int i = 0; i < first; i++) {   
                firstArray[i] = array[i];   
            }   
            for (int j = first; j < length; j++) {   
                secondArray[j - first] = array[j];   
            }   
            return Math.max(returnMax(firstArray), returnMax(secondArray));   
        }   
    }   
  
    public static void main(String[] args) {   
  
        FindMax findMax = new FindMax();   
        int array[] = { 5, 12, 1, 36, 9, 2, 14, 30, 21, 56,80,12,33};   
        long start = System.currentTimeMillis();   
        int max = findMax.returnMax(array);   
        long end = System.currentTimeMillis();   
        System.out.println("这个数组中的最大值是:" + max);   
        System.out.println("本次查找耗时: " + (end - start) + " ms");   
    }   
  
}  


运行:
C:\java>java FindMax
这个数组中的最大值是:80
本次查找耗时: 0 ms

上面的程序使用二分法查找一个数组的最大值,这是一个简单的程序,已经能很好的解释分治法的思想了。

五、棋盘覆盖问题的分治解法
   在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何
   k≥0,有4^k种不同的特殊棋盘.
   下图中的特殊棋盘是当k=2时中的一种

棋盘中的特殊方格如图:

   使用以下四种L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖.如何覆盖?


思路分析:
   当k>0时,将2^k×2^k棋盘分割为4个2^k-1×2^k-1子棋盘,如下图所示:



   特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格.为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处。

如下图所示,这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而原问题转化为4个较小规模的棋盘覆盖问题.递归地使用这种分割,直至棋盘简化为1×1棋盘。


(1)特殊方格在左上区域,那么其他几个区域的特殊方格可定,用如下一个L型骨牌覆盖3个无特殊方格的子棋盘会合处。



(2)特殊方格在右上区域,那么其他几个区域的特殊方格可定,用如下一个L型骨牌覆盖3个无特殊方格的子棋盘会合处。


(3)特殊方格在左下区域,那么其他几个区域的特殊方格可定,用如下一个L型骨牌覆盖3个无特殊方格的子棋盘会合处。


(4)特殊方格在右下区域,那么其他几个区域的特殊方格可定,用如下一个L型骨牌覆盖3个无特殊方格的子棋盘会合处。


import java.util.Scanner;
public class chessBoard
{  
 private  int dr,dc,size; // size:棋盘规格
 private  int[][]board;
 public chessBoard(int size,int dc,int dr){
  this.size=size;
  this.dc=dc;
  this.dr=dr;
  board=new int[this.size][this.size];
  init();
 }
 private void init() {
  for(int i=0;i<size;i++)
   for(int j=0;j<size;j++) board[i][j]=0;
 }
 public void chessBoard(int tr,int tc,int dr,int dc,int size){
  if(size==1) return;
  int s=size/2;
     //特殊方格在左上角
  if(dr<tr+s&&dc<tc+s){//覆盖第四个L型骨牌
   board[tr+s-1][tc+s]=4; //右上
   board[tr+s][tc+s-1]=4;//左下
   board[tr+s][tc+s]=4;//右下
   chessBoard(tr,tc,dr,dc,s);//左上
   chessBoard(tr,tc+s,tr+s-1,tc+s,s);//右上
   chessBoard(tr+s,tc,tr+s,tc+s-1,s);//左下
   chessBoard(tr+s,tc+s,tr+s,tc+s,s);//右下
  }
     //特殊方格在右上角
  if(dr<tr+s&&dc>=tc+s){//覆盖第3个L型骨牌
   board[tr+s-1][tc+s-1]=3; //左上
   board[tr+s][tc+s-1]=3;//左下
   board[tr+s][tc+s]=3;//右下
   chessBoard(tr,tc,tr+s-1,tc+s-1,s);//左上
   chessBoard(tr,tc+s,dr,dc,s);   //右上
   chessBoard(tr+s,tc,tr+s,tc+s-1,s);//左下
   chessBoard(tr+s,tc+s,tr+s,tc+s,s);//右下
  }
     //特殊方格在左下角
  if(dr>=tr+s&&dc<tc+s){//覆盖第2个L型骨牌
   board[tr+s-1][tc+s-1]=2; //左上
   board[tr+s-1][tc+s]=2;//右上
   board[tr+s][tc+s]=2;//右下
   chessBoard(tr,tc,tr+s-1,tc+s-1,s);//左上
   chessBoard(tr,tc+s,tr+s-1,tc+s,s);//右上
   chessBoard(tr+s,tc,dr,dc,s);//左下
   chessBoard(tr+s,tc+s,tr+s,tc+s,s);//右下
   }
     //特殊方格在右下角
  if(dr>=tr+s&&dc>=tc+s){//覆盖第1个L型骨牌
   board[tr+s-1][tc+s-1]=1; //左上
   board[tr+s-1][tc+s]=1;//右上
   board[tr+s][tc+s-1]=1;//左下
   chessBoard(tr,tc,tr+s-1,tc+s-1,s);//左上
   chessBoard(tr,tc+s,tr+s-1,tc+s,s);//右上
   chessBoard(tr+s,tc,tr+s,tc+s-1,s);//左下
   chessBoard(tr+s,tc+s,dr,dc,s);//右下
  }
 }

 public void showChess(){
  for (int i = 0; i < size; i++) {
   for (int j = 0; j < size; j++)
   { System.out.print(board[i][j]+" ");}
   System.out.println();       }
 }

 public static void main(String[] args) {
  int size,dr,dc;
  System.out.println("请输入棋盘的边长 ");
  Scanner reader= new Scanner(System.in);
  size=reader.nextInt(); //边长(4的倍数)
  System.out.println("请输入棋盘特殊方格的具体位置(排号    列号):");
  dr=reader.nextInt()-1; //排号
  dc=reader.nextInt()-1; //列号
  chessBoard chess=new chessBoard(size,dr,dc);
  chess.chessBoard(0, 0, dr, dc, size);
  chess.showChess();}
 }


运行结果:


源码下载:




  • 大小: 4.9 KB
  • 大小: 7.3 KB
  • 大小: 3.7 KB
  • 大小: 3.8 KB
  • 大小: 3.1 KB
  • 大小: 3.1 KB
  • 大小: 3.3 KB
  • 大小: 3.3 KB
  • 大小: 81.6 KB
分享到:
评论

相关推荐

    分治算法的实现

    **分治算法详解** 分治算法是计算机科学中一种重要的问题解决策略,它将一个大问题分解成若干个规模较小的相同或相似的子问题,然后递归地解决这些子问题,最后将子问题的解合并得到原问题的解。这种方法能够有效地...

    动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法

    本篇文章将深入探讨标题和描述中提到的一些核心算法,包括动态规划、分治算法、概率算法、模拟退火算法、搜索算法、贪婪算法、在线MATLAB应用、遗传算法以及组合算法。 1. **动态规划**:动态规划是一种解决具有...

    分治算法实验报告

    【分治算法】是一种重要的计算机科学中的算法设计策略,它将复杂的问题分解成若干个规模较小的相同问题,再将这些小问题的解合并得到原问题的解。这个过程可以递归地应用到子问题上,直至子问题足够简单可以直接求解...

    算法实习:分治算法求n个数的数组中找出第二个最大元素

    ### 分治算法求解数组中第二大的元素 #### 背景介绍 在计算机科学领域,寻找数组中的最大或次大元素是常见的问题之一。这类问题不仅有助于理解数据结构的基本概念,也是评估算法效率和复杂度的良好案例。本文将探讨...

    计算机算法-分治算法

    分治算法是计算机科学中的一个核心概念,它是一种解决问题的策略,通过将复杂问题分解为较小的、相同或相似的子问题来解决。这个过程通常涉及三个主要步骤:分解、解决和合并。分治法充分利用了问题的结构特性,使得...

    Java基于分治算法实现的棋盘覆盖问题示例

    Java基于分治算法实现的棋盘覆盖问题示例 本文主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了Java基于分治算法实现棋盘覆盖问题的相关操作技巧。 知识点一:...

    从键盘输入一组整数,通过分治算法求第二大的数

    ### 分治算法求第二大的数 #### 背景与目的 在计算机科学领域,分治算法是一种重要的问题解决策略,被广泛应用于多种算法设计之中。分治算法的基本思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题,...

    数学建模十大算法之分治算法

    ### 数学建模十大算法之分治算法:深入解析与应用 #### 分治算法概览 在数学建模与计算机科学领域,分治算法(Divide and Conquer)是一种核心的解决问题策略,广泛应用于各种复杂问题的求解过程中。其基本思想是...

    信息学奥赛一本通-教程PPT课件(第五版)算法部分 第七章 分治算法.pdf

    分治算法是计算机科学中的一种重要算法思想,其核心是将一个难以直接解决的大问题分解成一些规模较小的相同问题,递归地解决这些子问题,然后再将子问题的解合并以得到原来问题的解。本部分介绍的信息学奥赛教程PPT...

    分治算法详解

    分治算法是一种重要的算法设计思想,其核心在于将一个难以直接解决的大问题划分成若干个小问题,递归地解决这些小问题,最后再将小问题的解合并以解决原来的大问题。在本课程件中,将从多个方面对分治算法进行详细...

    贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf

    贪心算法、分治算法和动态规划的区别 贪心算法、分治算法和动态规划是三种常用的算法设计策略,每种算法都有其特点和应用场景。下面我们将对这三种算法进行详细的比较和分析。 分治算法 分治算法是一种将原问题...

    低买高卖分治算法

    - 分治算法是一种解决复杂问题的有效方法,它将大问题分解为若干个规模较小的相同或相似的子问题,递归地解决子问题,最后将子问题的解组合得到原问题的解。 - 在低买高卖问题中,分治算法的应用可能并不直观,但...

    分治算法在循环赛赛程分配中的应用

    分治算法是一种有效的算法设计策略,其核心思想是将一个难以直接解决的大问题分解成一系列规模较小的相同问题,递归地解决这些子问题,然后将子问题的解合并以得到原问题的解。分治算法广泛应用于计算机科学和信息...

    邮局最佳选址问题分治算法python实现

    在这个场景中,我们采用分治算法来解决。分治算法是一种将复杂问题分解为多个较小规模的子问题,然后逐个解决的策略。在邮局选址问题中,可能的目标是找到一个位置,使得所有客户的平均距离最小。 首先,我们需要...

    基础算法 第7章 分治算法(C++版)-2021.02.04.pdf

    分治算法是一种解决复杂问题的策略,其核心思想是将大问题划分成若干个小问题,递归地解决这些小问题,然后合并这些小问题的解以得到原来大问题的解。分治算法的基本步骤通常包括分解、解决、合并三个阶段。 在描述...

    算法——分治算法原理

    **分治算法**是一种在计算机科学中广泛应用的解决问题的策略,尤其在算法设计领域具有重要地位。它的核心理念是将复杂的问题分解成多个相似的、更小规模的子问题,然后对子问题进行求解,最后将子问题的解合并以获得...

    分治算法(最近点对问题的C++实现)

    在计算机科学中,分治算法是一种重要的解决问题的策略,它将一个大问题分解为若干个相同或相似的小问题,然后分别解决这些小问题,最后再将这些小问题的解组合成原问题的解。这种算法通常应用于数据结构、排序、搜索...

    分治算法-求一个数组中的最大值和最小值

    ### 分治算法在求解最大值与最小值问题中的应用 #### 一、分治算法原理及背景 分治算法是一种高效的问题解决策略,它通过将一个复杂的问题分解成若干个相同或相似的小问题来逐步求解。这些小问题彼此独立且与原...

    棋盘覆盖算法(分治算法)

    ### 棋盘覆盖算法(分治算法) #### 背景与定义 在计算机科学领域,特别是算法设计中,“棋盘覆盖”问题是一个经典的题目,它涉及到如何使用特定形状的多米诺骨牌(通常为 L 形)来覆盖一个有缺陷的棋盘。这里所谓的...

Global site tag (gtag.js) - Google Analytics