算法的 MATLAB 实现
首先特殊方格在棋盘中的位置可以用一个1 2 的数组 sp 表示；对于图 2 所 示的 4 种 L 型骨牌，可用数字 1,2,3,4 表示；对于特殊棋盘的骨牌覆盖表示，只 须注意到图 4 所示的关键点，对每个关键点，给定一种 L 型骨牌，就能覆盖整个 棋盘，所以对于 2k 2k 的特殊棋盘的骨牌覆盖，可用一个 (2k 1) (2k 1) 的矩阵 表示。按照这种思想，图 4 的矩阵表示为：
1 2 3
图 3 棋盘分割
图 4 关键结点
特殊方格必位于 4 个较小子棋盘之一中，其余 3 个子棋盘中无特殊方格。为 了将这 3 个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个 L 型骨牌覆盖
7
v1.0 可编辑可修改
这 3 个较小棋盘的会合处，如图 4 中央 L 型骨牌所示，这 3 个子棋盘上被 L 型骨 牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为 4 个较小规模的 棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为11棋盘。
5
v1.0 可编辑可修改
2 5 6 8 8 9 10 12 12 12 14 15 15 16 16 0 将该结果表示为图，即为图 1 粗线所示。
棋盘覆盖问题
问题的提出
在一个 2k 2k 个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称 该方格为一特殊方格，且称该棋盘为一特殊的棋盘。如图 1 就是当 k 3时的特 殊棋盘。棋盘覆盖问题中，我们要用图 2 所示 4 种不同形态的 L 形骨牌覆盖一个 特殊棋盘，且任何 2 个 L 型不得重叠覆盖。
⑤ S S {vi1} ， S S {vi1} ， i i 1，转②；
实际上，Dijkstra 算法也是最优化原理的应用：如果 v1v2 vn1vn 是从 v1 到 vn 的最短路径，则 v1v2 vn1 也必然是从 v1 到 vn1 的最优路径。
在下面的 MATLAB 实现代码中，我们用到了距离矩阵，矩阵第 i 行第 j 行元 素表示顶点 vi 到 v j 的权 wij ，若 vi 到 v j 无边，则 wij realmax ，其中 realmax 是 MATLAB 常量，表示最大的实数+308)。
在算法中，我们用数组六元数组 ss 表示中间车站的个数(A1 也作为中间车 站)，用距离矩阵 path 表示该图。为简便起见，把该图看作有向图，各边的方向 均为从左到右，则 path 不是对称矩阵，如 path(12,14)=5，而 path(14,12)=0(用 0 表示不通道路)。用 3´ 16 矩阵 spath 表示算法结果，第一行表示结点序号， 第二行表示该结点到终点的最短距离，第三行表示该结点到终点的最短路径上的 下一结点序号。下面给出 MATLAB 实现算法。
v1.0 可编辑可修改
单源最短路径问题 Dijkstra 算法
图论实验三个案例
Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置 一个顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且 仅当从源到该顶点的最短路径长度已知。设 v 是图中的一个顶点，记 l(v) 为顶点 v 到源点 v1 的最短距离， vi , v j V ，若 (vi , v j ) E ，记 vi 到 v j 的权 wij 。
end
2
v1.0 可编辑可修改
end
s(1,t)=0;%找到最小的顶点加入集合 S
end
re=r;
动态规划求解最短路径 动态规划是美国数学家 Richard Bellman 在 1951 年提出来的分析一类多阶
段决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控 制工程等方面均有着广泛的应用。动态规划应用了最佳原理：假设为了解决某一 优化问题，需要依次作出 n 个决策 D1, D2, , Dn ，如若这个决策是最优的，对于 任何一个整数 k，1<k<n，不论前面 k 个决策是怎样的，以后的最优决策只取决 于由前面决策所确定的当前状态，即 Dk1, Dk2 , , Dn 也是最优的。
mm=realmax; for j=find(s==0);%集合 S 中的顶点
for k=find(s==1);%集合 S 补中的顶点 if(r(2,j)+ma(j,k)<r(2,k)) r(2,k)=r(2,j)+ma(j,k);r(3,k)=j; end if(mm>r(2,k)) mm=r(2,k);t=k; end
global covermatrix if k==1
switch tp(1,3) case 1 covermatrix(tp(1,1),tp(1,2))=3; case 2
9
v1.0 可编辑可修改
covermatrix(tp(1,1),tp(1,2))=4; case 3
covermatrix(tp(1,1),tp(1,2))=1; case 4
图 1 当 k=3 时的特殊棋盘
(a)
(b)
(c)
(d)
图 2 4 种不同形态的 L 型骨牌
6
v1.0 可编辑可修改
问题的分析
易知，用到的 L 型骨牌个数恰为 (4k 1) / 3 。利用分治策略，我们可以设计出 解棋盘覆盖问题的一个简捷的算法。
当 k>0 时，我们将 2k 2k 棋盘分割为 4 个 2k1 2k1 子棋盘如图 3 两粗实线所 示。
%解决棋盘的覆盖问题
%棋盘为 2^k*2^k，sp 为特殊方格的棋盘位置
global covermatrix
covermatrix=zeros(2^k-1,2^k-1);
8
v1.0 可编辑可修改
even1=floor(sp(1,1)/2)*2==sp(1,1);%判断水平位置是否是偶数 even2=floor(sp(1,2)/2)*2==sp(1,2);%判断竖直位置是否是偶数 if even1==1&&even2==0%找出找出特殊方格相对关键结点的位置
end k=k-ss(i);移入下一阶段 end 先在 MATLAB 命令窗口中构造距离矩阵 path，再输入： >> ShortestPath(path,ss) 得到以下结果： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 13 16 13 10 9 12 7 6 8 7 5 9 4 3 0
i=4; else
i=even1+even2+1; end tempfun(1,1,k,[sp(1,1)-even1,sp(1,2)-even2,i]); re=covermatrix;
function tempfun(top,left,k,tp)%子函数,tp 为转换后特殊方格在棋盘网 络的相对位置
5
A4 1
6
A2
3 A5
6
8
A8
3
5
2 2
A11
3 5 5 A14
4
A1 3
8 7
A6
3 3
A9 1 2
A12 2
A3
6
8 4
A7
3
A10
3
6 6
A13
A15
ห้องสมุดไป่ตู้A16 3
图 1 可选择的管道图
3
v1.0 可编辑可修改
解决此问题可以用穷举法，从 A1 到 A16 有 48 条路径，只须比较 47 次，就可 得到最短路径为：A1→A2→A5→A8→A12→A15→A16，最短距离为 18。
Dijkstra 算法：
① S {v1}, l(v1) 0 ； v V {v1} , l(v) , i 1, S V {v1} ；
② S ，停止，否则转③；
③ l(v) min{l(v), d (v j , v)} ， v j S ， v S ；
④ 存在 vi1 ，使 l(vi1) min{l(v)} ， v S ；
function [scheme] = ShortestPath(path,ss) %利用动态规划求最短路径 %path 是距离矩阵,ss 是车站个数 n=size(path,1);%结点个数 scheme=zeros(3,n);%构造结果矩阵 scheme(1,:)=1:n;%设置结点序号
4
v1.0 可编辑可修改
1 0 4 0 1 0 2
0 4 0 0 0 2 0
4 0 3 0 2 0 3
0 0 0 3 0 0 0
1 0 4 0 3 0 2
0 4 0 0 0 3 0
k=4，特殊方格位置为：[1,4]，覆盖矩阵为： 4 0 3 0 4 0 3
下面是在 MATLAB 中的棋盘覆盖实现程序。
function re = chesscover(k,sp)
也可以使用 Dijkstra 算法。这里，我们动态规划解决此问题。注意到最短 路径有这样一个特性，即如果最短路径的第 k 站通过 Pk，则这一最短路径在由 Pk 出发到达终点的那一部分路径，对于始点为 Pk 到终点的所有可能的路径来说， 必定也是距离最短的。根据最短路径这一特性，启发我们计算时从最后一段开始， 从后向前逐步递推的方法，求出各点到 A16 的最短路径。
covermatrix(tp(1,1),tp(1,2))=2; end else half=2^(k-1);i=top+half-1;j=left+half-1; if tp(1,1)<i
if tp(1,2)<j%特殊方格在左上 covermatrix(i,j)=3; %添加类型为 3 的 L 型骨牌 tempfun(top,left,k-1,tp); tempfun(top,left+half,k-1,[i-1,j+1,4]); tempfun(top+half,left+half,k-1,[i+1,j+1,1]