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

2744557306

1. board=zeros(100,100);) @' D, T6 F5 A7 y' ^7 ]
   
2. n=4;\" V$ ]5 ?, e9 V) {
   
3. size=2^n;8 ~( l4 |2 ~. W+ T  o\" Q2 _$ S4 C% v
   
4. amount=0;  v: G. K+ D0 S4 {( m3 Y
   
5. [board,amount]=cover(1,1,2,5,board,size,amount);
   2 t7 s4 m; E& J! Q
6. board(1:size,1:size); V5 {5 @' f! s) X9 r) b8 s
   
7. 
     a5 ^0 R5 R! a7 O- s+ _0 W0 J

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数4 M' x* s: l1 A5 l- N& o7 J5 R1 ~7 S
   
2. 
   3 U! n: T' I' o$ `8 k
3. if size==1, P) \4 ?+ M- Z7 A
   
4. return\" x+ n0 M# E4 t& c4 ~7 B
   
5. end3 O: w4 }' Y( g
   
6. amount=amount+1;\" q9 F! q5 x$ \7 v/ ?, g
   
7. size=size/2;
   # U+ l) T/ W+ h5 w: B2 c0 u' [
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘
   - X9 C! Y& K9 r* ~8 Q1 j
9. : ]9 ?7 y( C: @: ?/ r
   
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置1 _/ @7 E! F' P, H2 r3 N# P
    
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);\" z- ~9 B3 D: E0 a  D
    
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);\" T+ p2 G7 K7 t$ m2 {% R6 z6 p- Z
    
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘# q+ r- x5 _% X& ]
    
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置0 X: ?6 L& R: |; J2 n6 o
    
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);$ f& Q& z' c% v
    
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);, Y' X0 m- O+ j+ S, a0 }: e) E6 E
    
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘7 ^4 \# [% n0 {$ u) C4 S\" N. Z7 `
    
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    . ?\" o6 M; l) g1 A  Y
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);% T2 t  A* |8 x6 H& ~' k
    
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);
    $ H& v2 _1 o! g$ r. y
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘+ x; _. {! o! x  ]
    
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置\" H& e* t/ L& A. D
    
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);, g9 r/ T8 z6 L0 A
    
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);$ A0 s* D% v' }; s5 |1 T) S
    
25. end5 y! ^- V& P' G: D' x6 T: b\" R
    
26. 
    4 Q6 I2 d( s1 g; p& d2 D  q
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 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。

% T! g9 o6 P% D4 u2 x# |
! B, |4 c, V- C- y