分治法解决残缺棋盘的规划 - 数学建模社区-数学中国

function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数
0 n- Y p) {1 ^: D# D* A" d9 c
6 _2 a* J8 B$ R4 _% Z& G- t3 g
if size==10 `6 R. y& e5 O2 {' g2 g; E% X3 u
return) f+ j- s( Y9 w. e+ ]& n
end9 I+ B3 _3 z) f- X& \
amount=amount+1;. P3 ?, N; d; a) ?$ b. K
size=size/2; A S( e7 [3 O9 G) U
if (k<size+i)&(l<size+j)%残缺位于左上棋盘$ n% @7 P, q4 k- z; C: V
1 |2 N) h, q# I( D6 L2 F w* [
board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置- D- c9 R# l( S
[board,amount]=cover(i,j,k,l,board,size,amount);[board,amount]=cover(i,j+size,size+i-1,j+size,board,size,amount);( s+ v W: \' ]/ _- z
[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);0 j! u. u. t5 k! y! n( F
elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘
6 W* K) U* n) W# {2 @# q
board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
6 p$ _ V* B# o. ~! i6 j3 X
[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);
. o x3 n, @( d2 A. w& l H# _
[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);
8 S* F$ b+ `- [# O8 F. R
elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘
; H T2 g! ?6 g) {
board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置: H" ?" Q/ i R* ?
[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);
* R+ B( E! H7 v
[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);7 E% i" X. e5 ]* G5 v
elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘4 j( r; g; N6 y4 x
board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
: m7 S6 c, \+ u6 v; W5 p
[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);
0 z N& r# t. _5 m! T
[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);
( s6 |8 ]8 s) p5 k4 B a
end
# m `5 Z3 w ?4 r1 b
9 n* ~! h- i7 V$ w, U) [! a) P5 o
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 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。