matlab madian,马踏棋盘——贪心算法
原来一直认为算法没啥难的，前几天无意间在网上看到了马踏棋盘的问题，就尝试的做了做。这才发现之前上的课真是白上了，什么回溯、递归、贪心，就记得点名字，其他全都通通忘了(其实，当时就没学明白，嘿嘿)。正好借着这个机会，从新学习一遍，鉴于估计以后还得忘(记性不好)，特此写一篇博文记录一下。
-----------------------------我是分割线(怕自己看不懂，嘿嘿)--------------------------
首先，对问题描述一下。马踏棋盘问题就是在一个8X8的棋盘上，马按照日字形规则在棋盘上欢快的跳跃，如何才能将每个格子都走到，而且每个格子只能跳一次。(不知道这个问题谁想的，一定是闲的蛋疼。。。)抽象来看，就是一个搜索问题，如果用二叉树来表示，就是一个深度为64，每个树杈有不多于7种分支的树(自行脑补，懒得画图了)。那么最直观的方法就是用遍历的方法，也就是所谓的深度搜索(听着好牛)，但是这样的效率据说比较低(我也没验证，有时间再说)，还有比较常用的就是贪心算法，也就是本文所用方法。
这里大概说一下贪心算法的内涵，就是在每次决策的时候选取局部最优(就是这么简单)。对于马踏棋盘的问题来说，每次选取出口最少的路径。至于为什么这么选择，我看到有人说是因为出口少就代表选择性小，遍历的也就会快，也就越容易先排除，这样就增加了算法速度。但是，如果按照这个理论也就意味着，在决策的时候要去找局部最差，显然这个解释不太合理(不过，我目前也没想明白)。先不管为啥了，就这么做吧。
再说说这里面要用到的回溯和递归算法，这两个算法的意思我就不解释了。我要说的是在设计递归的时候，要把任务拆分成循环任务。同时，要设计出成功通道，也就是什么情况下递归结束。对于该问题，递归函数要完成的有以下几点：1.查找可用的子节点；2.记录当前结点位置；3.进入一个子节点；4.判定递归成功，并从成功通道跳出递归。
对于回溯算法，就是如果不成功，要从子节点回到父节点。对于本问题，其实并不需要设置回到父节点的程序，只需要将已经记录的位置清零(也就是相当于没走这条路)，并且不再进行下一步的递归，跳出当前程序，也就是回溯了。
在编程的时候，为了调代码方便，看到有人用5X5的棋盘做实验，我也就照猫画虎。但是，要注意的是5X5的棋盘并不是所有点都有解(就没人说过！！导致我还老以为我的代码出问题了，8X8的棋盘是所有点都有解的)。
都说无图无真相，先放两张图，一张5X5，一张8X8
5X5解法
8X8解法
程序用文字描述如下：
【输出棋盘号，标志位】=查找路径【节点位置，输入棋盘号】
if 是否走完了所有位置
标志位置1；；
end
查找所有可能子节点
将子节点按照贪心算法排序
for 每个可能节点
递归查找路径函数
if 标志位为1
记录当前棋盘号；
给该曾函数标识1；；
else
给当前棋盘号置0；%这就是回溯
end
end
标识0；
end
程序如下：
[ ] = (
%HORSE 马踏棋盘-贪心算法
%时间:
%-----------初始化棋盘以及初始位置------------------
=5;
%棋盘横向长度
=5;
%棋盘纵向高度
x=1;%();
y=1;%();
=zeros(,);
Path=[x,y];
%记录马的路径
(x,y)=1;
%标记棋盘第一步位置
count=2;
%标记后从2开始
%-----------开始计算路径----------------------------
=clock;
[,mark]=track(x,y,count,);
%计算解集，输出标志位，以及棋盘标号
=etime(clock,);
%------------判断是否获得可用路径-------------------
if(mark==1)
%------------将中标号转换到Path中路径---------
for k=2:size(,1)*size(,2)
mpos=find(==k);
r=rem(mpos,size(,1));
if(r==0)
r=size(,1);
end
Path=[Path;r (mpos-r)/size(,1)+1];
end
%------------绘制棋盘以及马走过的路径----------------
hold on
plot(Path(1,1)+0.5,Path(1,2)+0.5,'or');
plot(Path(:,1)+0.5,Path(:,2)+0.5,'*');
plot(Path(:,1)+0.5,Path(:,2)+0.5,'g');
plot(Path(size(Path,1),1)+0.5,Path(size(Path,1),2)+0.5,'ob');
for j=1:+1
plot(j*ones(1,+1),1:+1,'r');
plot(1:+1,j*ones(1,+1),'r');
end
hold off
disp(['计算所需时间为： ' ()
's']);
else
disp(['当x=' (x) ',y=' (y) '
无解！']);
end
end
[,mark]=track(x,y,count,)
%查找当前子节点，并进入代价最小的子节点
%---------------设置节点初始条件--------------------------------
mx1=x;
my1=y;
pCost=[];
=size(,1)*size(,2);
%--------------找出有效子节点-----------------------------------
=(mx1,my1,);
%找出周围不超过边界的点
=(,);
%找出还未走过的店
=size(,1);
if(count>5)
y=1;
end
%--------------判断是否存在子节点--------------------------------
if(~=0)
%----------如过存在子节点，且当前标号为，那么就得到最终解，返回标志位1--
if(count==)
((1,1),(1,2))=count;
mark=1;
=;
;
end
%-------------否则，计算各子节点代价函数,即每个节点出口数量---------------
for j=1:
=((j,1),(j,2),);
pCost=[pCost,];
end
%-------------将子节点按照出口数量递增排序，以便进行局部最优搜索-------------------
[,]=sort(pCost);
=(,:);
%-------------依次搜索每个子节点，并给当前结点标号----------------------------------
for m=1:
tx=(m,1);
ty=(m,2);
(tx,ty)=count;
[borad,]=track(tx,ty,count+1,);
%-------------如果找到了最终路径，那么得到=1，继续返回成功标志位1--------------
if(==1)
mark=1;
=borad;
;
else
%------------如果不成功，就将当前结点置0，结束当前结点搜索，程序就相当于回溯到上一状态继续------
(tx,ty)=0;
end
end
end
%------------如果没有，则代表不成功，那么返回标志位0--------------------------
mark=0;
=;
end
Pos=(pos,)
%检查点是否走过,即已经被标注过
Pos=[];
for
i=1:size(pos,1)
if((pos(i,1),pos(i,2))==0)
Pos=[Pos;pos(i,:)];
end
end
end
Pos= (,,)
%找到在棋盘边界内的子节点
[ny,nx]=size();
%ny是y轴长度，nx是x轴长度
=[-2,-1,1,2,2,1,-1,-2]';
%横向偏差，坐标为x
=[1,2,2,1,-1,-2,-2,-1]';
%纵向偏差，坐标为y
x1=+;
y1=+;
=[x1 y1];
=find(((:,1)>0)&((:,1)0)&((:,2)
