分治算法

柔光的暖阳◎ 2022-06-05 06:06 180阅读 0赞

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

### 基本思想 ###

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

### 解题步骤 ###

分治法解题的一般步骤：  
（1）分解，将要解决的问题划分成若干规模较小的同类问题；  
（2）求解，当子问题划分得足够小时，用较简单的方法解决；  
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

### 棋盘覆盖 ###

题目：在一个(2^k)\*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘。我们要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角，方向随意），且任何两个L型方块不能重叠覆盖。L型方块的形态如下：  
题目的解法使用分治法，即子问题和整体问题具有相同的形式。我们对棋盘做一个分割，切割一次后的棋盘如图1所示，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个。假设如图1所示，特殊方格位于右上角，我们把一个L型方块（灰色填充）放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，直到子棋盘的大小为1为止。

### 解题思路 ###

分析：当k>0时，将2k×2k棋盘分割为4个2^k-1×2^k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

### 实现： ###

每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角（top left coner）方格的行列坐标，然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。在递归函数里，还要有一个变量s来记录边的方格数，每次对方块进行划分时，边的方格数都会减半，这个变量是为了方便判断特殊方格的位置。其次还要有一个变nCount来记录L型骨牌的数量。  
![这里写图片描述][SouthEast]

public class ChessBoradProblem { 
        private int[][] board;//棋盘
        private int specialRow;//特殊点的行下标
        private int specialCol;//特殊点的列下标
        private int size;
        private int type = 0;
        public ChessBoradProblem(int specialRow, int specialCol, int size) {
            super();
            this.specialRow = specialRow;
            this.specialCol = specialCol;
            this.size = size;
            board = new int[size][size];
        }
        /** * * @param specialRow 特殊点的行下标 * @param specialCol 特殊点的列下标 * @param leftRow 矩阵的左边起点行下标 * @param leftCol 矩阵左边起点的列下标 * @param size 矩阵的宽或者高 */
        private void ChessBoard(int specialRow,int specialCol,int leftRow,int leftCol,int size){
            if(size == 1){
                return;
            }
            int subSize = size/2;
            type = type%4 + 1;
            int n = type;
            //假设特殊点在左上角区域
            if(specialRow<leftRow+subSize&&specialCol<leftCol+subSize){
                ChessBoard(specialRow, specialCol, leftRow, leftCol, subSize);
            }else{
                //不在左上角，左上角矩阵的右下角就是特殊点
                board[leftRow+subSize-1][leftCol+subSize-1] = n;
                ChessBoard(leftRow+subSize-1, leftCol+subSize-1, leftRow, leftCol, subSize);
            }
            //特殊点在右上方
            if(specialRow<leftRow+subSize&&specialCol>=leftCol+subSize){
                ChessBoard(specialRow, specialCol, leftRow, leftCol+subSize, subSize);
            }else{
                board[leftRow+subSize-1][leftCol+subSize] = n;
                ChessBoard(leftRow+subSize-1, leftCol+subSize, leftRow, leftCol+subSize, subSize);
            }
            //特殊点在左下方
            if(specialRow>=leftRow+subSize&&specialCol<leftCol+subSize){
                ChessBoard(specialRow, specialCol, leftRow+subSize, leftCol, subSize);
            }else{
                board[leftRow+subSize][leftCol+subSize-1] = n;
                ChessBoard(leftRow+subSize, leftCol+subSize-1, leftRow+subSize, leftCol, subSize);
            }
    
            //特殊点在右下角
            if(specialRow>=leftRow+subSize&&specialCol>=leftCol+subSize){
                ChessBoard(specialRow, specialCol, leftRow+subSize, leftCol+subSize, subSize);
            }else{
                board[leftRow+subSize][leftCol+subSize] = n;
                ChessBoard(leftRow+subSize, leftCol+subSize, leftRow+subSize, leftCol+subSize, subSize);
            }
        }
    
        public void printBoard(int specialRow,int specialCol,int size){
            ChessBoard(specialRow, specialCol, 0, 0, size);
            printResult();
        }
    
        private void printResult() {
            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 N = 8;
            int specialRow = 0;
            int specialCol = 1;
            ChessBoradProblem boradProblem = new ChessBoradProblem(specialRow, specialCol, N);
            boradProblem.printBoard(specialRow, specialCol, N);
        }
    }

[SouthEast]: /images/20220605/483c32ade7a94fcea1f457941f75a804.png