MATLAB—A*解决八数码问题

「爱情、让人受尽委屈。」 2022-06-15 04:06 221阅读 0赞

## 一、实验目的 ##

1、 熟悉和掌握启发式搜索的定义、估价函数和算法过程。  
2、 利用A\*算法求解N数码难题，理解求解流程和搜索顺序。

## 二、实验内容 ##

以八数码为例实现A或A\*算法 。

1、分析算法中的OPEN表和CLOSE表的生成过程。

2、分析估价函数对搜索算法的影响。

3、分析启发式搜索算法的特点。

## 三、程序实现    ##

up8.m

function B=up8(a)  %0向上移动
    [x,y]=find(a==0);
    if x==1            %如果0在矩阵的最上一层，则B=-1
        B=-1;         
        return 
    end
    B=a;               %否则交换两个位置的值
    B(x,y)=a(x-1,y);
    B(x-1,y)=0;
    return

down8.m

function B=down8(a)   %0向下移动
    [x,y]=find(a==0);
    if x==3               %如果0在矩阵的最下一层，则B=-1
        B=-1;    
        return 
    end
    B=a;                   %否则交换两个位置的值
    B(x,y)=a(x+1,y);
    B(x+1,y)=0;
    return

left8.m

function B=left8(a)     %0向左移动
    [x,y]=find(a==0);
    if y==1                 %如果0在矩阵的最左一层，则B=-1
        B=-1;
        return 
    end
    B=a;                    %否则交换两个位置的值
    B(x,y)=a(x,y-1);
    B(x,y-1)=0;
    return

right8.m

function B=right8(a)         %0向右移动
    [x,y]=find(a==0);
    if y==3                      %如果0在矩阵的最右一层，则B=-1
        B=-1;
        return 
    end
    B=a;                         %否则交换两个位置的值
    B(x,y)=a(x,y+1);
    B(x,y+1)=0;
    return

h1.m

function val=h1(A,T) 
    [i,j]=find(A==0);
    B=A-T;
    index=find(B~=0);     %找出A中不在位的个数，即B中非0的个数
    [k,l]=find(T==0);
    if i==k&&j==l        %除去目标矩阵中为0的位置，因为0不在位不计入
        val=length(index);
        return;
    end
    val=length(index)-1;

chushi8.m

function OPEN8=chushi8(A,T)
        OPEN8=cell(1);
        OPEN8{1,1}.g=0;
        OPEN8{1,1}.h=h1(A,T);
        OPEN8{1,1}.f=OPEN8{1,1}.g+OPEN8{1,1}.h;
        OPEN8{1,1}.S=A;  %当前节点的状态
        OPEN8{1,1}.fa=[]; %父节点的状态，这样的保留可以从找到的目标状态追踪到初始状态

tuozhan8.m

function [OPEN8,g,tail]=tuozhan8(g,c,tail,T,OPEN8,CLOSED8)
        flag=0;                     %设置是否可扩展的标志位
        flag2=0;
        if up8(OPEN8{1,1}.S)~=-1    %判断是否可以向某个方向移动
            for i=1:c-1             %判断是否在CLOSED8表中，如果在，则不能进行扩展
                if up8(OPEN8{1,1}.S)==CLOSED8{1,i}.S
                    flag=1;
                    break;
                end
            end 
            
            for j=1:tail             %判断是否在OPEN8表中，如果在，则不能进行扩展
                if up8(OPEN8{1,1}.S)==OPEN8{1,j}.S
                    flag2=1;
                    break;
                end
            end 
            
            if flag~=1&&flag2~=1
                tail=tail+1;
                OPEN8{1,tail}.g=g;
                B=up8(OPEN8{1,1}.S);
                OPEN8{1,tail}.h=h1(B,T);
                OPEN8{1,tail}.f=OPEN8{1,tail}.g+OPEN8{1,tail}.h;
                OPEN8{1,tail}.S=B;  %当前节点的状态 
                OPEN8{1,tail}.fa=OPEN8{1,1}.S; %父节点的状态，这样的保留可以从找到的目标状态追踪到初始状态
            end
        end 
        
        if down8(OPEN8{1,1}.S)~=-1
            for i=1:c-1
                if down8(OPEN8{1,1}.S)==CLOSED8{1,i}.S
                    flag=2;
                    break;
                end
            end 
            
            for j=1:tail             %判断是否在OPEN8表中，如果在，则不能进行扩展
                if down8(OPEN8{1,1}.S)==OPEN8{1,j}.S
                    flag2=2;
                    break;
                end
            end 
            
            if flag~=2&&flag2~=2
            tail=tail+1;
            OPEN8{1,tail}.g=g;
            B=down8(OPEN8{1,1}.S);
            OPEN8{1,tail}.h=h1(B,T);
            OPEN8{1,tail}.f=OPEN8{1,tail}.g+OPEN8{1,tail}.h;
            OPEN8{1,tail}.S=B;  %当前节点的状态
            OPEN8{1,tail}.fa=OPEN8{1,1}.S; %父节点的状态，这样的保留可以从找到的目标状态追踪到初始状态
            end
        end
        
        if left8(OPEN8{1,1}.S)~=-1
            for i=1:c-1
                if left8(OPEN8{1,1}.S)==CLOSED8{1,i}.S
                    flag=4;
                    break;
                end
            end 
            
            for j=1:tail             %判断是否在OPEN8表中，如果在，则不能进行扩展
                if left8(OPEN8{1,1}.S)==OPEN8{1,j}.S
                    flag2=4;
                    break;
                end
            end 
            
            if flag~=4&&flag2~=4
            tail=tail+1;
            OPEN8{1,tail}.g=g;
            B=left8(OPEN8{1,1}.S);
            OPEN8{1,tail}.h=h1(B,T);
            OPEN8{1,tail}.f=OPEN8{1,tail}.g+OPEN8{1,tail}.h;
            OPEN8{1,tail}.S=B;  %当前节点的状态
            OPEN8{1,tail}.fa=OPEN8{1,1}.S; %父节点的状态，这样的保留可以从找到的目标状态追踪到初始状态
            end
        end
        
        if right8(OPEN8{1,1}.S)~=-1
            for i=1:c-1
                if right8(OPEN8{1,1}.S)==CLOSED8{1,i}.S
                    flag=3;
                    break;
                end
            end 
            
            for j=1:tail             %判断是否在OPEN8表中，如果在，则不能进行扩展
                if right8(OPEN8{1,1}.S)==OPEN8{1,j}.S
                    flag2=3;
                    break;
                end
            end 
            
            if flag~=3&&flag2~=3
            tail=tail+1;
            OPEN8{1,tail}.g=g;
            B=right8(OPEN8{1,1}.S);
            OPEN8{1,tail}.h=h1(B,T);
            OPEN8{1,tail}.f=OPEN8{1,tail}.g+OPEN8{1,tail}.h;
            OPEN8{1,tail}.S=B;  %当前节点的状态
            OPEN8{1,tail}.fa=OPEN8{1,1}.S; %父节点的状态，这样的保留可以从找到的目标状态追踪到初始状态
            end
        end

yunxing.m

%A=[2 8 3;1 6 4;7 0 5]
    %T=[1 2 3;8 0 4;7 6 5]
    
    %A=[7 5 3;1 6 4;2 8 0]
    %T=[1 2 3;8 0 4;7 6 5]
    
    %A=[1 2 3;7 8 4;0 6 5]
    %T=[1 2 3;8 0 4;7 6 5]
    
    %A=[2 3 0;1 5 6;8 4 7]
    %T=[1 2 3;4 5 6;7 8 0]     %运行时要修改h1函数中的if语句，因为0的位置不计入不在位个数
    function [CLOSED8]= yunxing(A,T)
        OPEN8=chushi8(A,T);        %初始化OPEN8表，即将待扩展的第一个节点放入
        c=1;                       %CLOSED8表中的指针
        g=1;
        tail=1;
        CLOSED8=cell(1);
        k=1;                       %设置扩展了多少个的标志
    while 1    
        if h1(OPEN8{1,1}.S,T)==0&&k<=1000  %当找到最终的目标时则输出，并跳出while循环
            disp(OPEN8{1,1}.S);
            break;
        end
        if k>=1000                   %如果扩展了的节点个数大于某个数则跳出并显示
            disp(k);
            break;
        end
        [OPEN8,g,tail]=tuozhan8(g,c,tail,T,OPEN8,CLOSED8);  %对OPEN8表中的第一个点扩展
        CLOSED8{1,c}=OPEN8{1,1};         %将已扩展的节点放入CLOSED8表中
        c=c+1;
        
        b=10000;
        index=1;
        for i=2:tail                     %找出OPEN8表中f值最小的元素
            if OPEN8{1,i}.f<=b         
                b=OPEN8{1,i}.f;
                g=OPEN8{1,i}.g;
                index=i;
            end
        end
        
        g=g+1;
        OPEN8{1,1}=OPEN8{1,index};       %将OPEN8表中的最小f的元素给OPEN8{1,1}
        OPEN8{1,index}=OPEN8{1,tail};    %将OPEN表尾元素赋给最小f值的位置
        tail=tail-1;
        k=k+1;
     end
    
    %输出矩阵
    d=length(CLOSED8);   
    i=g-1;               %i表示输出的个数
    t=CLOSED8{1,d};      %t为CLOSED表里最后一个元素
    while i>0
        disp(t.S);       %输出此节点
        t=t.fa;          %令其等于其父节点
        if isempty(t)    %判断其父节点是否为空，为空则结束
            break;
        end
        
        for j=1:length(CLOSED8)   %判断其父节点在CLOSED表中的位置
            if CLOSED8{1,j}.S==t
                t=CLOSED8{1,j};   %如果有的话，将其位置赋给t
                break;
            end 
        end
        
        i=i-1;
    end

## 四、运行结果 ##

![Center][]

![Center 1][]

![Center 2][]

## 五、实验分析 ##

首先从上向下扩展节点

结果从下向上输出，依次查找其父节点。

[Center]: /images/20220615/8a2d17c118764565b7135c20217bf222.png
[Center 1]: /images/20220615/8707765c5d4a4a80ab642d710e89fb4d.png
[Center 2]: /images/20220615/28ab694ee2be45c68fd6455b527cf258.png