分治（詳解殘缺棋盤 —— Java代碼實現）

分治

總體思想

將要求解的較大規模的問題分割成k個更小規模的子問題

對這k個子問題分別求解。如果子問題的規模仍然不夠小，則再劃分為k為子問題，如此遞歸進行下去，直到問題規模足夠小，很容易求出其解為止

將求出的小規模的問題的解合并為一個更大規模的問題的解，自底向上逐步求出原來的問題的解

使用條件

該問題的規模縮小到一定的程度就可以容易地解決

該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質

利用該問題分解出的子問題的解可以合并為該問題的解

該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題

能否利用分治法完全取決于子問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態規劃

基本步驟

divide-and-conquer(P) { if (|P| <= n0) abhoc(P); // 解決小規模的問題 divide P into smaller subinstances P1, P2 ,... ,Pk // 分解問題 for (i = 1; i <= k; i++) { yi = divide-and-conquer(Pi); // 遞歸的解各子問題 return merge(y1, ... ,yk) // 將各子問題的解合并為原問題的解 } }

案例

覆蓋殘缺棋盤

在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。

用 (n2) / 3個三重格放置在 n × n 的缺陷棋盤上，正好能夠覆蓋所有方格

具體步驟：

劃分為四個小棋盤

其中一個是 4 × 4 缺陷棋盤

在其他三個 4 × 4 棋盤都都相鄰的拐角上放一個三格板，使它們也成為缺陷棋盤

遞歸地覆蓋四個4×4缺陷棋盤

在其它三個 4 × 4 棋盤都相鄰的拐角上放一個三格板，使它們也成為缺陷棋盤。

Java代碼實現

package Chess; public class Chess { // 表示棋盤 private int[][] board; // 表示棋盤的大小為2的多少次方 private int boardSize; // 棋盤中特殊方格的位置（行號，列號） private int dr, dc; private int tile = 1; public Chess() { board = new int[1][1]; dr = 0; dc = 0; boardSize = 0; } public Chess(int r, int c, int s) { int n; n = (int) Math.pow(2, s); if (n <= r || n <= c) System.out.println("初始化參數錯誤！"); else { board = new int[n][n]; dr = r; dc = c; boardSize = s; } } public void Print() { for (int i = 0; i < Math.pow(2, this.boardSize); i++) { for (int j = 0; j < Math.pow(2, this.boardSize); j++) { System.out.printf("%3d|", this.board[i][j]); } System.out.println(); } } public static void main(String[] args) { // 2^2*2^2棋盤, 假設特殊方格位置為（3, 3） Chess c1 = new Chess(3, 3, 2); c1.chessBoard(0, 0, c1.dr, c1.dc, (int)Math.pow(2, c1.boardSize)); c1.Print(); } /** * @param tr：棋盤左上角方格的行號 * @param tc：棋盤左上角方格的列號 * @param dr：特殊方格所在的行號 * @param dc：特殊棋盤所在的列號 * @param size：2^k, 棋盤的規格為 2^k*2^k **/ public void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; // t: L型骨牌號，s分割棋盤 int t = tile++; int s = size / 2; // 覆蓋左上角棋盤 if (dr < tr + s && dc < tc + s) { // 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s); } else { // 此棋盤中無特殊方格則用t號L型骨牌覆蓋右下角 board[tr + s - 1][tc + s - 1] = t; // 覆蓋其余方格 chessBoard(tr, tc, tr + s - 1, tc + s - 1, s); } // 覆蓋右上角子棋盤 if (dr < tr + s && dc >= tc + s) { // 特殊方格在此棋盤中 chessBoard(tr, tc + s, dr, dc, s); } else { // 無特殊方格，用t號骨牌覆蓋左下角 board[tr + s - 1][tc + s] = t; chessBoard(tr, tc + s, tr + s - 1, tc + s, s); } // 覆蓋左下角棋盤 if (dr >= tr + s && dc < tc + s) { chessBoard(tr + s, tc, dr, dc, s); } else { // 無特殊方格，用t號骨牌覆蓋右上角 board[tr + s][tc + s - 1] = t; chessBoard(tr + s, tc, tr + s, tc + s - 1, s); } // 覆蓋右下角棋盤 if (dr >= tr + s && dc >= tc + s) { // 特殊方格在此棋盤中 chessBoard(tr + s, tc + s, dr, dc, s); } else { // 無特殊方格，用t號骨牌覆蓋左上角 board[tr + s][tc + s] = t; chessBoard(tr + s, tc + s, tr + s, tc + s, s); } } }

2| 2| 3| 3| 2| 1| 1| 3| 4| 1| 5| 5| 4| 4| 5| 0|

大整數的乘法

小學的方法：效率太低 O(n2)

分治法：

X = A × 2n/2 + B

Y = C × 2n/2 + D

XY = (A × 2n/2 + B)(C × 2n/2 + D)

=AC × 2n + (AD + CB) × 2n/2 + BD

實質上沒有改進

再次進行改進：

XY = AC × 2n + (AD + CB) × 2n/2 + BD

=AC × 2n + ((A - B)(D - C) + AC + BD) × 2n/2 + BD

這樣只需進行3次 n/2 位乘法

T(n) = O(nlog3) = O(n1.59) （有了較大的改進）

如果將大整數分成更多段，用更復雜的方式把它們組合起來，將有可能得到更優的算法

Strassen矩陣乘法

易知，時間復雜度為 O(n3)

分治法：

將矩陣A、B和C中每一矩陣都分成4個大小相等的子矩陣，則 C = AB 可寫為：

由此可得：

實際復雜度還是沒有變，仍然為 O(n3)

為了降低時間復雜度，要減少乘法的次數

這樣，復雜度得到了改進

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。