用A*算法解决八数码问题 MATLAB

代码：

bashuma.m

function []=bashuma
global e;  %open表计数
global i;  %close表计数
global m;  %循环次数计数
a=0;b=0;n=0;i=0;
e=1;m=0;%初始化
dis=[1 2 3;8 0 4;7 6 5]; %目标节点
f.prev=zeros(3);
f.con=[7 5 3;1 6 4;2 8 0]; %初始节点
f.num=1;
f.fuc=valuefuc(f,dis);
y=dis;
open(1)=f; %初始化Open表
k=f;while a==0m=m+1;%设置循环次数if m>=10000disp('error!!');break;end%  寻找代价最小值for j=1:eif k.fuc>open(j).fuck=open(j);endend%%添CLOSE表i=i+1;j=k.num;close(i)=k;close(i).num=i;%%删OPEN表open(j).con=zeros(3);open(j).fuc=inf;%%是否找到目的节点a=getit(close,dis);if a==1disp('success!!');break;end%%扩展节点open=opera(open,close,k,dis);k.fuc=inf; 
end
%输出路径
while 1for j=1:iif y==zeros(3)b=1;break;endif close(j).con==yt=close(j).num;n=n+1;show(n)=t;y=close(j).prev;endendif b==1break;end
end
for j=1:nclose(show(n+1-j)).con
endend%查询是否找到目标节点
function a=getit(close,dis)
global i;for j=1:iif close(j).con==disa=1;break;elsea=0;endend
end

open.m

%上下左右移动操作
function open=opera(op,cl,f,dis)
global i;[x,y]=find(f.con==0);
if x==1&&y==1open=rt(f,op,cl,dis);open=dn(f,open,cl,dis);
elseif x==1&&y==2open=lt(f,op,cl,dis);open=rt(f,open,cl,dis);open=dn(f,open,cl,dis);
elseif x==1&&y==3open=lt(f,op,cl,dis);open=dn(f,open,cl,dis);
elseif x==2&&y==1open=up(f,op,cl,dis);open=rt(f,open,cl,dis);open=dn(f,open,cl,dis);
elseif x==2&&y==2open=lt(f,op,cl,dis);open=up(f,open,cl,dis);open=rt(f,open,cl,dis);open=dn(f,open,cl,dis);
elseif x==2&&y==3open=lt(f,op,cl,dis);open=up(f,open,cl,dis);open=dn(f,open,cl,dis);
elseif x==3&&y==1open=up(f,op,cl,dis);open=rt(f,open,cl,dis);
elseif x==3&&y==2open=lt(f,op,cl,dis);open=up(f,open,cl,dis);open=rt(f,open,cl,dis);
elseif x==3&&y==3open=lt(f,op,cl,dis);open=up(f,open,cl,dis);
end
endfunction open=rt(f,op,cl,dis)
global e;e=e+1;
s=f;[x,y]=find(s.con==0);
t=s.con(x,y+1);
s.con(x,y+1)=0;
s.con(x,y)=t;
s.num=e;op(e).con=s.con;
op(e).prev=f.con;
op(e).num=e;
op(e).fuc=valuefuc(s,dis);search(s,op,cl);
open=op;
endfunction open=up(f,op,cl,dis)
global e;e=e+1;
s=f;[x,y]=find(s.con==0);
t=s.con(x-1,y);
s.con(x-1,y)=0;
s.con(x,y)=t;
s.num=e;op(e).con=s.con;
op(e).prev=f.con;
op(e).num=e;
op(e).fuc=valuefuc(s,dis);search(s,op,cl);
open=op;
endfunction open=lt(f,op,cl,dis)
global e;e=e+1;
s=f;[x,y]=find(s.con==0);
t=s.con(x,y-1);
s.con(x,y-1)=0;
s.con(x,y)=t;
s.num=e;op(e).con=s.con;
op(e).prev=f.con;
op(e).num=e;
op(e).fuc=valuefuc(s,dis);search(s,op,cl);
open=op;
endfunction open=dn(f,op,cl,dis)
global e;e=e+1;
s=f;[x,y]=find(s.con==0);
t=s.con(x+1,y);
s.con(x+1,y)=0;
s.con(x,y)=t;
s.num=e;op(e).con=s.con;
op(e).prev=f.con;
op(e).num=e;
op(e).fuc=valuefuc(s,dis);search(s,op,cl);
open=op;
endfunction fuc=valuefuc(f,dis)s1=0;[x,y]=find(f.con==1);s1=s1+abs(x-1)+abs(y-1); [x,y]=find(f.con==2);s1=s1+abs(x-1)+abs(y-2);[x,y]=find(f.con==3);s1=s1+abs(x-1)+abs(y-3);[x,y]=find(f.con==4);s1=s1+abs(x-2)+abs(y-3);[x,y]=find(f.con==5);s1=s1+abs(x-3)+abs(y-3);[x,y]=find(f.con==6);s1=s1+abs(x-3)+abs(y-2);[x,y]=find(f.con==7);s1=s1+abs(x-3)+abs(y-1);[x,y]=find(f.con==8);s1=s1+abs(x-2)+abs(y-1);fuc=s1;
end

search.m

% 查询重复操作
function []=search(f,op,cl)
global e;
global i;
%e
%open(e-1).con
for j=1:e-1if  op(j).con==f.cone=e-1;breakend
endfor j=1:i-1if cl(j).con==f.cone=e-1;break;end
end
end

valuefuc.m

function fuc=valuefuc(f,dis)s1=0;[x,y]=find(f.con==1);[x1,y1]=find(dis==1);s1=s1+abs(x-x1)+abs(y-y1); [x,y]=find(f.con==2);[x1,y1]=find(dis==2);s1=s1+abs(x-x1)+abs(y-y1); [x,y]=find(f.con==3);[x1,y1]=find(dis==3);s1=s1+abs(x-x1)+abs(y-y1); [x,y]=find(f.con==4);[x1,y1]=find(dis==4);s1=s1+abs(x-x1)+abs(y-y1); [x,y]=find(f.con==5);[x1,y1]=find(dis==5);s1=s1+abs(x-x1)+abs(y-y1); [x,y]=find(f.con==6);[x1,y1]=find(dis==6);s1=s1+abs(x-x1)+abs(y-y1); [x,y]=find(f.con==7);[x1,y1]=find(dis==7);s1=s1+abs(x-x1)+abs(y-y1); [x,y]=find(f.con==8);[x1,y1]=find(dis==8);s1=s1+abs(x-x1)+abs(y-y1); fuc=s1
end

运行结果：

思路：代码很复杂。。人工智能老师说要自己敲。。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！