分治算法

一、分治法的基本思想
   任何一个可以用计算机求解的问题所需的计算时间都与其规模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();}
 }

运行结果：


源码下载：