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

2744557306

1. board=zeros(100,100);
   # t' `( u; K7 m% K
2. n=4;
   & D1 [0 d0 q9 Y
3. size=2^n;1 u) V! [8 o  F& f3 o9 i& h1 Z( Z+ |
   
4. amount=0;5 P, _  y* B$ M  G4 |3 u2 p& h; |
   
5. [board,amount]=cover(1,1,2,5,board,size,amount);+ a6 \9 |8 H\" N
   
6. board(1:size,1:size)
   8 u0 O* S\" A% u- Y
7. 
   . k0 _% H6 o1 I9 M6 l: b# x

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数
   / A; K& u8 Q. s2 I# ], M& G' d) I
2. ) W8 c% S5 z! z5 @7 M3 P% ?- _5 h
   
3. if size==19 O3 Y- A6 ~! S+ p- `
   
4. return% _/ c1 T( q3 l; {( L, G
   
5. end7 {$ A! ?6 C& Y3 _/ M& \
   
6. amount=amount+1;; f- ^+ j7 B: {/ x
   
7. size=size/2;
   \" Y: W9 `1 W! b0 _; g
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘
   ! z7 N; d+ L5 w# `! d
9. 
   5 F\" o. M  p; _1 ]2 |; q- J# H
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置
    8 q5 X+ x5 r1 U1 X. d1 Q
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);
    - J& P7 Z3 }9 A8 F0 _/ ?) v' ~3 t3 a
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);' }! q8 C* N$ }, N# T
    
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘
    6 m& @9 c0 Q$ A- t5 \1 j
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    \" C6 e\" M! L! C9 ?1 N% p& n. 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);
    7 h8 W6 V\" S\" f' T& I+ ?
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 b. @& T! C# i. _' e/ \% }9 ]
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘
    ( L8 R/ e8 q. r, h
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置3 O$ a\" R7 Y: s  u& d
    
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);
    / w6 I; O# e2 u7 V
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);
    6 ]2 Z8 y7 Q5 N, x- O! o
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘
    4 C' Q\" g5 G4 p( o5 D( m; o
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置7 a) u+ c$ G6 R3 }# {# 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);
    + l' k) G! r9 [& |) E
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);4 P2 A4 S, a9 I
    
25. end! M; b8 Z8 U$ [$ B$ r. G
    
26. 
    ( v) }. X7 ?6 S! a
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 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。

; H. ?% M, g! D' X; ~# j0 C
. \+ @" @: A+ \' Q" f7 g