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--->柱子%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
