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

2744557306

1. board=zeros(100,100);
   ' R$ w( x0 t* w* D0 _
2. n=4;/ p  G0 `0 ?1 X. h
   
3. size=2^n;, v+ Y; S: B% V# A) M
   
4. amount=0;3 t* R) x6 o9 c- O: ~\" Q
   
5. [board,amount]=cover(1,1,2,5,board,size,amount);
   # ]9 I: m7 t: l3 [  \7 f
6. board(1:size,1:size)
   7 T3 F9 B+ P- u, s  W2 q3 W
7. % A1 ^) ^0 Y* E7 @
   

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数/ t6 m- d  ?\" a
   
2. ; `3 V\" e9 Q; Z, \$ m! r: f! ~) e7 f
   
3. if size==1
   9 A5 D$ R; g0 M/ v: ~1 X% L+ \
4. return8 R; E$ }: C& e5 n; s, z
   
5. end
   & T\" S/ Z0 v3 E; V; W. k
6. amount=amount+1;% k2 b' y4 S1 s+ H) M
   
7. size=size/2;
   4 b+ U+ Q: P6 k1 M2 O6 E
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘\" y7 X0 J4 Z: l6 K# k
   
9. 
   # {. d5 u& G6 p5 E3 L8 y( \
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置
    $ E6 l2 x2 d2 [\" V0 k9 O
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);
    ( P. g6 D# W6 \+ X* E, Q
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);
    8 C* Y& y\" u, W/ K3 l2 N
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘
    & d/ h- B5 ^4 O. G  K- }
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    ; K- b) f2 ~2 P
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);
    0 W, V\" u/ J) h0 U0 c4 |' G7 h
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);2 ^! X5 v8 ^0 D0 ]0 a( H7 O
    
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘; h4 }3 C/ @- a\" p. |( N
    
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    % P# \\" U' Q* l* y: s: {
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);: Q! W! s+ L$ E6 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);
    \" f3 e; B6 h0 l* z
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘
    2 X$ y* ~) d4 `8 b4 m* O8 O
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    \" [( h: |. T& |2 L( j+ B( P
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);
    & ?* v/ N$ |0 m& H  s& m( O& z2 s
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);7 ]0 o9 [9 E! L- x% H8 U- J
    
25. end
    \" b& x! D$ }) s# D3 z
26. 8 o' ?: m8 I: v( g. i% t
    
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 N( ?/ w" X; j; n1 S1 f6 i. o% [
- H7 |) p+ ^" {