分治法解决残缺棋盘的规划

2744557306

1. board=zeros(100,100);% P0 H5 |  Z/ M# _$ R; \
   
2. n=4;5 V1 F) X\" q* Q* E) B
   
3. size=2^n;\" M, s4 o+ `* a2 Z: C: F& s* J
   
4. amount=0;. _0 Q0 v4 b& ?2 B7 f, u( c  k. ?
   
5. [board,amount]=cover(1,1,2,5,board,size,amount);
   6 Z* v3 V  s/ X2 H3 I6 c
6. board(1:size,1:size)
   + J$ l- m. Q6 K# m, G0 P
7. 4 g& p7 a\" w. z/ i; L: I
   

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数* N  w2 C& L  _+ a2 K0 y
   
2. \" B/ _; w$ d% W* H0 C& {4 p8 V8 ?
   
3. if size==13 I, C9 t4 y; v: P2 j/ r
   
4. return
   9 q: u* h' [) Z% W
5. end: }2 `, d8 a4 t2 @1 M# r! {
   
6. amount=amount+1;  G$ R! a, K4 B% _) u) W5 ]6 w
   
7. size=size/2;( Y0 ]9 b& @. C' e7 u  k# P\" u
   
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘) {0 X! ?9 @, u2 a! e. Q) q! j
   
9. 
   0 f! ^\" C\" V( E8 f
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置
    , v: [, [* R7 t
11. [board,amount]=cover(i,j,k,l,board,size,amount);[board,amount]=cover(i,j+size,size+i-1,j+size,board,size,amount);$ D* _$ w7 o8 j3 a  l& {& y. T7 E
    
12. [board,amount]=cover(size+i,size+j,size+i,size+j,board,size,amount);[board,amount]=cover(i+size,j,i+size,j+size-1,board,size,amount);
    ( J5 z5 G$ p% U; U
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘
    - }7 d- l- i: w; c/ g. L7 u7 U
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置- N  O% y, [7 ?/ K
    
15. [board,amount]=cover(i+size,j,k,l,board,size,amount);[board,amount]=cover(i,j+size,size+i-1,j+size,board,size,amount);* N# n1 t7 Z3 a+ M5 A( u' Y
    
16. [board,amount]=cover(size+i,size+j,size+i,size+j,board,size,amount);[board,amount]=cover(i,j,i+size-1,j+size-1,board,size,amount);
    * c0 N' x. g( |. z
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘* x# B2 E) h$ P3 F; W7 y- }1 J
    
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    & A3 S( }8 M1 C; L& }/ |; O6 S+ t
19. [board,amount]=cover(i,j+size,k,l,board,size,amount);[board,amount]=cover(i,j,i+size-1,j+size-1,board,size,amount);+ Z$ O3 U# E1 m  }6 _4 h1 p
    
20. [board,amount]=cover(size+i,size+j,size+i,size+j,board,size,amount);[board,amount]=cover(i+size,j,i+size,j+size-1,board,size,amount);& ]/ W3 ]5 H. k& h. ~0 a' e1 x
    
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘
    2 p3 _7 |5 h+ U
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置0 N\" ~% t6 ]' o6 U( f2 G
    
23. [board,amount]=cover(size+i,size+j,k,l,board,size,amount);[board,amount]=cover(i,j+size,size+i-1,j+size,board,size,amount);4 J$ ?- u- Y+ D3 h. c0 l
    
24. [board,amount]=cover(i,j,i+size-1,j+size-1,board,size,amount);[board,amount]=cover(i+size,j,i+size,j+size-1,board,size,amount);8 t* r* ^8 g5 a3 I7 u
    
25. end
    6 T% I0 E1 w8 B) w. H
26. 
    3 g5 o- F- c+ F$ ^8 X
27. end

复制代码

这段代码实现了一个递归算法，用于在一个二维棋盘上填充缺失的部分，其中棋盘大小为100x100。下面是对代码的详细解释：1.初始化：2.board 是一个100x100的矩阵，初始化为全零。这个矩阵表示棋盘，其中的元素将被填充。3.n 表示棋盘的2的幂次方边长，这里设置为4，所以 size = 2^n 就是棋盘的边长。4.amount 用于计数已经填充的片数，初始化为0。5.调用 cover 函数：6.cover 函数是一个递归函数，用于填充缺失的部分。它接受左上角坐标 (i, j) 和残缺区域的左上角坐标 (k, l)，以及当前棋盘的大小 size 和已填充的片数 amount。7.函数首先检查 size 是否为1，如果是，表示当前棋盘已经缩小到最小规模，不再分割，直接返回。8.递归填充：9.然后，函数增加 amount，表示填充了一个片。10.接下来，根据缺失区域的位置，分别在左上、左下、右上、右下四个棋盘中的合适位置填充片，然后递归调用 cover 函数。11.递归终止条件：12.递归的终止条件是 size 变为1，此时直接返回。13.输出结果：14.最后，输出已经填充的棋盘的左上角大小为 size 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。

1 r' |$ H% b8 c' G7 X3 N