0x01 前言

昨天遇到八数码问题，瞬间想到小时候玩的拼图游戏，大概长这样

（图片来源于百度图片）
看似简单但是印象中就没成功过……，不过，利用启发式搜索，这个问题就是秒解了，接下来介绍两种解决八数码问题的方法，本人认为这是启发式搜索的两种实现方式。

0x01 启发式搜索0

第一种方法较简单，步骤如下：
1.计算初始评估值，这里评估值是不在正确位置的点的数量。
2.利用队列搜索，从四个方向移动空格获得新节点，计算新节点的评估值。
3.如果新节点评估值小于等于父节点评估值+1，就是优秀节点，加入队列。
4.直到找到评估值为0的节点，就是结果。
代码如下：
//代码来源于blog.csdn.net/wangqiuyun/article/details/7840771
加入了少许注释。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define N 3 //数码组大小
#define Max_Step 50 //最大搜索深度
#define MAX 50
    typedef struct node//八数码结构体
    {
        int form[N][N];//数码组
        int evalue;//评估值
        int udirect;//所屏蔽方向，防止往回推到上已状态，1上2下3左4右
        struct node *parent;//父节点
    }Graph;
    Graph *Qu[MAX];//队列
    Graph *St[MAX];//堆栈
    /////////打印数码组
    void Print(Graph *The_graph)
    {
        int i,j;
        if(The_graph==NULL)
            printf("图为空\n");
        else
        {
            printf("---------------------\n");
            for(i=0;i<N;i++)
            {
                printf("|\t");
                for(j=0;j<N;j++)
                {
                    printf("%d\t",The_graph->form[i][j]);//遍历打印
                }
                printf("\t|\n");
            }
            printf("|\t\t\t差距:%d\t|\n",The_graph->evalue);//差距显示
            printf("---------------------\n");
        }
    }
    /////////评价函数
    int Evaluate(Graph *The_graph,Graph *End_graph)
    {
        int valute=0;//差距数
        int i,j;
        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++)
            {
                if(The_graph->form[i][j]!=End_graph->form[i][j])   //if num is not in right site,valute++
                {
                    valute++;
                }
            }
        }
        The_graph->evalue=valute;
        return valute;
    }
    /////////移动数码组
    Graph *Move(Graph *The_graph,int Direct,int CreatNew_graph)
    {
        Graph *New_graph;//
        int HasGetBlank=0;//是否获取空格位置
        int AbleMove=1;//是否可移动
        int i,j,t_i,t_j,x,y;
        for(i=0;i<N;i++)//获取空格坐标i,j
        {
            for(j=0;j<N;j++)
            {
                if(The_graph->form[i][j]==0)
                {
                    HasGetBlank=1;
                    break;
                }
            }
            if(HasGetBlank==1)
                break;
        }
        //printf("空格位置:%d,%d\n",i,j);
        t_i=i;
        t_j=j;
        //移动空格
        switch(Direct)
        {
            case 1://上
                t_i--;
                if(t_i<0)
                    AbleMove=0;
                break;
            case 2://下
                t_i++;
                if(t_i>=N)
                    AbleMove=0;
                break;
            case 3://左
                t_j--;
                if(t_j<0)
                    AbleMove=0;
                break;
            case 4://右
                t_j++;
                if(t_j>=N)
                    AbleMove=0;
                break;
        }
        if(AbleMove==0)//不能移动则返回原节点
        {
            return The_graph;
        }
        if(CreatNew_graph==1)
        {
            New_graph=(Graph *)malloc(sizeof(Graph));//生成节点
            for(x=0;x<N;x++)
            {
                for(y=0;y<N;y++)
                {
                    New_graph->form[x][y]=The_graph->form[x][y];//复制数码组,save every statuses.
                }
            }
        }
        else
        {
            New_graph=The_graph;
        }
        //移动后
        New_graph->form[i][j]=New_graph->form[t_i][t_j];   //0 change to num
        New_graph->form[t_i][t_j]=0;   //num change to 0
        //printf("移动产生的新图:\n");
        //Print(New_graph);
        return New_graph;
    }
    /////////搜索函数
    Graph *Search(Graph *Begin,Graph *End)
    {
        Graph *g1,*g2,*g;
        int Step=0;//深度
        int Direct=0;//方向
        int i;
        int front,rear;
        front=rear=-1;//队列初始化
        g=NULL;
        rear++;//入队
        Qu[rear]=Begin;
        while(rear!=front)//队列不空
        {
            front++;//出队
            g1=Qu[front];
            //printf("开始第%d个图:\n",front);
            //Print(g1);
            for(i=1;i<=4;i++)//分别从四个方向推导出新子节点
            {
                Direct=i;
                if(Direct==g1->udirect)//跳过屏蔽方向
                    continue;
                g2=Move(g1, Direct, 1);//移动数码组
                if(g2!=g1)//数码组是否可以移动
                {
                    //可以移动
                    Evaluate(g2, End);//评价新的节点
                    //printf("开始产生的第%d个图:\n",i);
                    //Print(g2);
                    if(g2->evalue<=g1->evalue+1)
                    {
                        //是优越节点
                        g2->parent=g1;
                        //移动空格
                        switch(Direct)//设置屏蔽方向，防止往回推
                        {
                            case 1://上
                                g2->udirect=2;
                                break;
                            case 2://下
                                g2->udirect=1;
                                break;
                            case 3://左
                                g2->udirect=4;
                                break;
                            case 4://右
                                g2->udirect=3;
                                break;
                        }
                        rear++;
                        Qu[rear]=g2;//存储节点到待处理队列
                        if(g2->evalue==0)//为0则搜索完成
                        {
                            g=g2;
                            //i=5;
                            break;
                        }
                    }
                    else
                    {
                        free(g2);//抛弃劣质节点
                        g2=NULL;
                    }
                }
            }
            if(g!=NULL)//为0则搜索完成
            {
                if(g->evalue==0)
                {
                    break;
                }
            }
            Step++;//统计深度
            if(Step>Max_Step)
            {
                break;
            }
        }
        return g;
    }
    /////////初始化一个八数码结构体
    Graph *CR_BeginGraph(Graph *The_graph)
    {
        srand((unsigned)time(0));
        int M=10;//随机移动步数
        int Direct;
        int i,x,y;
        Graph *New_graph;
        New_graph=(Graph *)malloc(sizeof(Graph));
        for(x=0;x<N;x++)
        {
            for(y=0;y<N;y++)
            {
                New_graph->form[x][y]=The_graph->form[x][y];   //init as end graph
            }
        }
        for(i=0;i<M;i++)
        {
            Direct=rand()%4+1;//产生1－4随机数
            //printf("Direct:%d\n",Direct);
            New_graph=Move(New_graph, Direct, 0);
            //Print(New_graph);
        }
        New_graph->evalue=0;
        New_graph->udirect=0;
        New_graph->parent=NULL;
        return New_graph;
    }
    int main (int argc, const char * argv[])
    {
        // insert code here...
        /*
        Graph Begin_graph={
            {{2,8,3},{1,6,4},{0,7,5}},0,0,NULL
        };
        Graph Begin_graph={
            {{2,8,3},{1,0,4},{7,6,5}},0,0,NULL
        };
        Graph Begin_graph={
            {{2,0,1},{4,6,5},{3,7,8}},0,0,NULL
        };
        */
        //目标数码组
        Graph End_graph={
            {{1,2,3},{8,0,4},{7,6,5}},0,0,NULL
        };
        //初始数码组
        Graph *Begin_graph;
        Begin_graph=CR_BeginGraph(&End_graph);//随机产生初始数码组
        Evaluate(Begin_graph, &End_graph);//对初始的数码组评价
        printf("初始数码组:\n");
        Print(Begin_graph);
        printf("目标数码组:\n");
        Print(&End_graph);
        Graph *G,*P;
        int top=-1;
        //图搜索
        G=Search(Begin_graph, &End_graph);
        //打印
        if(G)
        {
            //把路径倒序
            P=G;
            //压栈
            while(P!=NULL)
            {
                top++;
                St[top]=P;
                P=P->parent;
            }
            printf("<<<<<<<<<<<<<<<搜索结果>>>>>>>>>>>>>>>>\n");
            //弹栈打印
            while(top>-1)
            {
                P=St[top];
                top--;
                Print(P);
            }
            printf("<<<<<<<<<<<<<<<<<完成>>>>>>>>>>>>>>>>>>\n");
        }
        else
        {
            printf("搜索不到结果，深度为%d\n",Max_Step);
            //设计搜索深度范围主要是防止队列内存越界
        }
        return 0;
    }

0x02 启发式搜索-A*算法

这个方法利用评估函数判断最优解，评估函数f = g + h
g是当前节点距离初始节点的值，h是不在正确位置的点数量（同0x01评估值），其实h只要保证递减收敛即可，这里评估值就是f。
这里我在原代码基础上增加了判断是否有解的代码，判断代码也是用别人的，但是感觉有bug，有解也有时输出无解，利用的是奇偶性，逆序数，奇数无解，偶数有解，不大懂……。
这里需要用到open,close表，open存放待扩展节点，close存已扩展节点。
步骤如下：
1.将初始节点放入open表。
2.在open表中选出评估值f最小的节点，放入close表，同时删除open表中的该节点。
3.不断移动空格的位置扩展新节点，若不和close表的节点重复，则加入到open表中。
4.直到找到h为0的节点。
代码如下：
//代码来源于blog.sina.com.cn/s/blog_5be64cb70100lyx5.html
增加了少许注释。
判断代码Check()函数来源于blog.csdn.net/qq_32400847/article/details/51816685

//启发规则：评价函数是f(n)=d(n)+w(n)
//其中d(n)是结点深度，w（n）是将牌不在位数
//实现自输入初态：从左至右，从上到下输入
//目标棋局定为：1 2 3
//              8   4
//              7 6 5
//本程序中以0作为空格结点的值
#include<iostream>
#include<vector>
using namespace std;
struct point
{
 int a[3][3];   //graph
 int w;//the num about not in right site
 int d;//depth
 int f;//评价函数
};
vector<point*> close;//已扩展节点
vector<point*> open;//待扩展节点
int aim[3][3]={1,2,3,8,0,4,7,6,5};//目标棋局
int check(point *cs)   //check if it has solution
{
    int i,j,k;
    int s[20];
    int cnt=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            s[3*i+j]=cs->a[i][j];
            if(s[3*i+j]=='x') continue;
            for(k=3*i+j-1;k>=0;k--)
            {
                if(s[k]=='x') continue;
                if(s[k]>s[3*i+j]) cnt++;
            }
        }
    }
    if(cnt%2) return 0;
    return 1;
}
int Cout(point *&s)   //count the num about not in right site
{
 s->w=0;
 for(int i=0;i<3;i++)
 {
  for(int j=0;j<3;j++)
  {
   if(s->a[i][j]!=aim[i][j])
    s->w++;
  }
 }
 return s->w;
}
bool init(point * &s)//初始化接点
{
 s=(point *)malloc(sizeof(point));
 if(!s)
  return false;
 s->d=1;
 s->w=0;
 cout<<"请输入初始化接点：";
 for(int i=0;i<3;i++)
 {
  for(int j=0;j<3;j++)
  {
   int a;
   cin>>a;
            s->a[i][j]=a;
  }
 }
 Cout(s);
 s->f=s->d+s->w;   //f
 return true;
}
int sort()//将open表中接点按评价函数排序,返回评价函数值最小的节点在队列中的位置
{
 if(open.size()!=0)
 {
  int min=0;
  int temp=open.at(0)->f;
  for(int i=0;i<open.size();i++)
  {
   if(open[i]->f<temp)
   {
    temp=open[i]->f;
    min=i;
   }
  }
  return min;
 }
 return -1;
}
bool compare(point *s)//比较可扩展接点与colse表中接点是否重复,true:不重复 false:重复
{
 vector<point*>::iterator it;
 for(it=close.begin();it!=close.end();it++)
 {
  int n=0;
  for(int i=0;i<3;i++)
  {
   for(int j=0;j<3;j++)
   {
    if(s->a[i][j]!=(*it)->a[i][j])
    {
     n++;
     break;
    }
   }
  }
  if(n==0)
   return false;
 }
 return true;
}
void expand(point *s)//扩展接点
{
 int a,b;
 for(int i=0;i<3;i++)   //get 0 site
 {
  for(int j=0;j<3;j++)
  {
   if(s->a[i][j]==0)
   {
    a=i;b=j;
    break;
   }
  }
 }//确定空格位置
 for(int i=0;i<4;i++)//四个方向探测--0:上 1：下 2：左 3：右
 {
  int n=0;
  point *p=(point *)malloc (sizeof(point));
  for(int c=0;c<3;c++)
  {
   for(int z=0;z<3;z++)
    p->a[c][z]=s->a[c][z];
  }
  if(i==0&&b-1>=0)//左可行，交换
  {
   int temp=p->a[a][b-1];
   p->a[a][b-1]=p->a[a][b];
   p->a[a][b]=temp;
   n++;
  }
  else if(i==1&&a+1<=3)//下可行，交换
  {
   int temp=p->a[a+1][b];
   p->a[a+1][b]=p->a[a][b];
   p->a[a][b]=temp;
   n++;
  }
  else if(i==2&&a-1>=0)//上可行，交换
  {
   int temp=p->a[a-1][b];
   p->a[a-1][b]=p->a[a][b];
   p->a[a][b]=temp;
   n++;
  }
  else if(i==3&&b+1<=3)//右可行，交换
  {
   int temp=p->a[a][b+1];
   p->a[a][b+1]=p->a[a][b];
   p->a[a][b]=temp;
   n++;
  }
  if(n==0)//此方向不可行，试探下一个方向
   continue;
  p->d=s->d+1;
  p->w=0;
  Cout(p);
  p->f=p->d+p->w;
  if(compare(p))//与已扩展节点相比无重复则加入open表
   open.insert(open.begin(),p);
 }
}
void print()//输出搜索路径
{
 vector<point*>::iterator it;
 for(it=close.begin();it!=close.end();it++)
 {
  for(int i=0;i<3;i++)
  {
   cout<<endl;
   cout<<(*it)->a[i][0]<<" "<<(*it)->a[i][1]<<" "<<(*it)->a[i][2]<<endl;
  }
  if(it!=close.end()-1)
  {
   cout<<" |"<<endl;
   cout<<" |"<<endl;
   cout<<"<>"<<endl;
  }
 }
}
void Num()
{
 point *s;
 init(s);
 if(!check(s)){
    printf("no solution!\n");
    return;
 }
 open.push_back(s);
 while(open.size()!=0)
 {
  int min=sort();
  point *ex=open.at(min);
  if(min!=-1)
  {
   if(close.size()!=0)//若open表中评价函数最小值节点的层数小于close表中层数,说明该路径非最优，
   {       //退回，删除close表中与最小值节点同层和下层节点
    vector<point*>::iterator it=close.end()-1;
    while(open.at(min)->d<=(*it)->d)
    {
     close.pop_back();
    }
   }
   close.push_back(open.at(min));//最小值节点入close
   open.erase(open.begin()+min);//同时删除open表中相应节点
   if(Cout(ex)==0)//若不在位节点数为0，则打印输出最优路径
   {
    print();
    return;
   }
   expand(ex);//若非目标棋局，则扩展节点
  }
 }
}
int main()
{
 Num();
 return 0;
}

好像有bug，有时没输出……
运行结果：

 

0x03 结语

晕乎乎，有空再仔细研究一下。
 

0x04 参考资料

blog.csdn.net/qq_32400847/article/details/51816685
blog.csdn.net/wangqiuyun/article/details/7840771
blog.csdn.net/zuzubo/article/details/1540280
blog.sina.com.cn/s/blog_4e0c21cc0102wvd3.html
blog.sina.com.cn/s/blog_5be64cb70100lyx5.html