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

2744557306

1. board=zeros(100,100);
   ( t9 [! {: k. w2 d# a
2. n=4;
   & L\" G7 u8 W) v* g, d0 m' H
3. size=2^n;/ [5 Z9 q7 @. `
   
4. amount=0;
   & ]! N8 J7 B3 l. o! s# u
5. [board,amount]=cover(1,1,2,5,board,size,amount);
   \" g, i+ p# {* x( S
6. board(1:size,1:size)
   , r* b* L0 l% y0 M8 _
7. 
   / ?' u8 }4 e- S3 F6 O, J! W0 h( J

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数
   7 i7 x6 W6 N( F1 R0 L6 x. l- P5 v
2. 
   ( e8 v3 ?( c+ e: T* `1 y
3. if size==1, Y3 U! o% w6 z# ^\" I1 y4 [
   
4. return9 i4 a2 \9 g* Z; Z
   
5. end
   ; B; \  Z  ^# |9 N, o7 I
6. amount=amount+1;8 b& \4 U; ?& h8 U- L
   
7. size=size/2;
   ! ?& U+ z, B- g& C\" N9 g- H2 s) t
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘
   2 _, P' N* X1 G  W1 h
9. + s6 R  I7 s/ P$ j5 i% ~9 I
   
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置
    / |) `; P  k/ R0 n- j, o0 U
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);/ M$ ?. ]- R* T1 u8 }
    
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);
      C& R6 _2 m; @
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘
    1 h/ T7 o6 d1 z/ w3 D
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    9 ]# X' {( R( I* ?6 c
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);\" a\" ]. ^+ [+ M  r( M, W
    
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);
    3 X; E& g2 Z+ _; d3 {& r$ a
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘
    + Q! o+ G! l2 p/ v: w# r3 U3 K1 P* L
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置7 \7 z. W0 U9 X1 i3 Y0 e8 L, i
    
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);* e4 ~+ s9 t9 n9 x! V1 G
    
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);; O) M6 }0 e0 O% ]\" w! D% b
    
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘5 l; A! r( J. a
    
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置( x+ |) ?( R# h8 Y: E7 o5 @
    
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);2 B7 P, N6 Z$ K9 V, f. {* ]
    
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);
    $ K6 l4 z* v  ]\" `4 Y, G' F7 Y
25. end
    ) L* ^\" }+ r3 u/ t
26. 6 w- {: |9 r6 j$ s) p* S
    
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 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。