路径寻找问题（状态空间搜索）

ACM学习笔记 DAY 18

路径寻找问题（状态空间搜索）和上一小节的回溯法有很大的不同：回溯法有明确的限制条件，只需找出满足条件下的一个解/所有解，也就是说这个相对明确的限制条件是回溯法得以“终止深究而回溯”的判定标准；而状态空间搜索就要模糊的多，一般是要找到一个从初始状态到终止状态的最优路径，而不是像回溯法一样找一个符合要求的解，而且“最优”是同类间的比较而非某些限制条件所规定。

八数码问题（核心代码剖析）

八数码问题讲的是编号为1~8的8个正方形块被放在3*3的矩阵中（一个空格），一次移动只可以移动空格旁边的来填补空格。给定初始样式和最终状态，计算移动的最小步数（如果无法达到目标输出-1）。

这道题的本质其实是图上的最短路问题，从空格开始以移动周围4个方格为一层，然后逐层操作延伸出众多子树。所以最直接的思路就是BFS广度优先（常用于找最小路径），这里可以使用数组模拟队列，只需定义队列首front指针和末尾指针rear即可，且返回目标完成时的首指针作为完成状态。可以通过一张图较为清晰的理解：

代码如下：

typedef int State[9];        //定义“状态”类型，方便后续定义数据
const int maxstate=1000000;  //解答树最多可以有maxstate个结点
State st[maxstate],goal;     //状态数组，保存每一个结点的3*3状态
int dist[maxstate];          //存放每一个结点到原点的距离
//如果需要打印整个过程，添加一个父亲编号数组（构成完整链表以便输出）
const int dx[]={-1,1,0,0};   //控制上移/下移/左移/右移
const int dy[]={0,0,-1,1};
//BFS，返回目标状态在st中的下标
int bfs(){
    init_lookup_table();     //初始化查找表
    int front=1,rear=2;      //初始化队列首元素下标和尾元素下标
    //这里front不能初始化为0，因为0表示不存在路径，而如果初状态和目标重合返回也是0
    while(front<rear){
        State& s=st[front];  //取出队首元素（引用可以简化代码）
        if(memcmp(goal,s,sizeof(s))==0)
            return front;    //找到目标，返回front首地址
        //还不是目标，则还需继续行动
        int z;
        for(z=0;z<9;z++) if(!s[z]) break; //找到空格位置（空格处值为0）
        int x=z/3,y=z%3;                  //求出空格行列
        for(int d=0;d<4;d++){             //前面4个移动数组的作用👈
            //开始模拟向4个方向移动
            int newx=x+dx[d];
            int newy=y+dy[d];
            int newz=newx*3+newy;         //求出新空格的一维坐标
            if(newx>=0&&newx<3&&newy>=0&&newy<3){
                //移动合法判断
                State& t=st[rear];
                mamcpy(&t,&s,sizeof(s));  //拷贝一份进新节点，下面进行数值改变
                t[newz]=s[z];             //空格和周围的交换
                t[z]=s[newz];
                dist[rear]=dist[front]+1; //记录更新结点的路径长度
                if(try_to_insert(rear)) rear++;  //成功插入查找表，就修改队尾指针
            }
        }
        front++;     //拓展完毕后修改队首指针
    }
    return 0;        //如果找不到，就失败
}

以上就是八数码问题核心函数的代码，其中使用了cstring中的memcmp进行整块内存的比较、mamcpy进行整块内存的拷贝（类似于strcmp/strcpy函数）。