梵塔难题（汉诺塔问题）四种方法代码（递归、线性算法、启发式、盲目式）.rar

function hannuota %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%&&&&&&&& %加了启发函数value(m,n)m为每一个节点的父节点在G中的位置，n为节点状态， %返回值为权值，权值越小越好说明代价越小，且距离目标越近。 %即f（n）=g(n)+h(n),g(n)为每一个节点的深度，h(n)为节点状态与目标节点状态的差值 %盘子的数量,标号为1，2，。。。，n标号越大则盘子越大 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% n=3; open=[]; %open表 close=[]; %close表 G=[]; %存放节点 %S0初始节点 S0=ones(1,n); %编号表示：表示在第几个柱子上 %标号为1的盘在a1棍子上 open=[open;S0]; G=[G;S0]; %已经遍历过的节点 open_G=[1]; %open表与G的对应关系，即open表的这几个节点在总节点表G中第几个 G_parent=[0]; %G的父节点，初始点的父节点为0 fprintf('%d个盘子的移动步骤：\n',n) while ~isempty(open) n0=open(1,:); %取出open表中的第一个节点 open(1,:)=[]; %该节点剔除open表 n_num=open_G(1); %获取（open表中该点在G的）位置 open_G(1)=[]; close=[close;n0]; %将其放入close表中 %%%%%%% if all(n0==3*ones(1,n))%如果所有盘子都已经移动到第三根棍子，则结束，all为检验矩阵是否有非零元素 path=[n_num]; %显示路径 break %%%%%% end for i=1:3 index=find(n0==i); %i为第几个柱子，find函数为返回第一个非零元素序号，按列向量排，既找三个柱子分别有几个盘 if ~isempty(index) %每个柱子若为空，函数取反后结果为0，有圆盘才执行 for j=1:3 %j为下个要去的柱子 if j==i %没变化则跳过 continue end index_=find(n0==j); if ~isempty(index_) && index_(1)<index(1) %大盘不能在小盘之上 continue %（下一个柱子有盘子）&&（下一个柱子盘子大小）<（将移动的盘子大小） end tmp=n0; %当前节点 tmp(index(1))=j; %得到一个扩展点 ind=find(all(G==repmat(tmp,size(G,1),1),2));%寻找新的扩展点在G表中的位置，返回值为在节点表G的位置（有此节点时）或者0（无此节点是） %repmat(A,m,n)，将矩阵A 复制 m×n 块，得到的维数是 [size(A,1)*m, size(A,2)*n] 。 if isempty(ind)%未曾在G中出现过 open=[open;tmp]; %加入open表 G=[G;tmp];%加入存放节点的节点表G open_G=[open_G;size(G,1)]; %open与G的对应，size(G,1)返回G行数 G_parent=[G_parent;n_num]; else%在G中出现过，（已经遍历过，同一深度的已经遍历完） if sousuo(G_parent,ind)>=sousuo(G_parent,n_num)+1%更换父节点，（ind为新扩展点位置，num为当前扩展点位置） open=[open;G(ind,:)]; open_G=[open_G;ind]; G_parent(ind)=n_num; end end end end open_=open; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %open表各个节点按权值排序 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% open(:,4)=0; for f=1:size(open,1) %循环次数为节点个数 open(f,4)=value(n_num,open(f,1:3)); end %启发式函数value得到open表各个节点权值 a=sortrows(open,4); %调用函数排序 open(:,4)=0; open=a(1,1:3); %取open表权值最小的节点 open=open_; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% end end while G_parent(path(end)) path=[path,G_parent(path(end))]; %父节点不为0时添加到路径path表 end path=G(path,:); for i=size(path,1):-1:2 ind=find(path(i,:)~=path(i-1,:)); %指向有变化的柱子，即移动了的柱子 fprintf('从柱子%d---&gt柱子%d\n',path(i,ind),path(i-1,ind)) end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %子函数一,评价函数 function num=value(m,n) num=m; %父节点在G中深度 for k=1:3 num=num+abs(n(1,k)-3); %与目标节点（3,3,3）的差距 end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %子函数二，计算深度 function num=sousuo(G_pr,n) num=0; while G_parent(n) num=num+1; n=G_parent(n); end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% end