1. 前言

智能控制基础的课后题，开始以为没什么，但是不写复杂的算法好久动手写起来还是漏洞百出
主要参考了这篇博客的内容
英文描述此问题可参见[此处](http://www.aiai.ed.ac.uk/gwickler/-inf.html)

2. 实现

2.1 定义一个图的节点类

class VertexOfGraph {       //定义图的节点类
public:
    int vertex[3][3];
    int h,g;
    int x,y;
    string hashValue;

public:
    VertexOfGraph() {       //构造函数将成员变量初始化为0和空
        x = 0;
        y = 0;
        h = 0;
        g = 0;
        hashValue = "";
    };
    bool isValid() {        //判断当前状态是否有效,如果超出边界范围则无效
        if(x >= 0 && x < 3 && y >= 0 && y < 3) {
            return true;
        }
        return false;
    }
    void newStatus(int oldX, int oldY) {    //将现在存储的空位位置x,y与oldX,oldY对应的位置交换数值,得到新状态
        int temp = vertex[x][y];
        vertex[x][y] = vertex[oldX][oldY];
        vertex[oldX][oldY] = temp;
    }
};

为了方便将类的成员变量都定义为public类型，省去了set、get方法，类中的h、g并没有用到，初始化都置0了，作为以后扩展用，主要是用于启发式搜索中的估价函数，搜索得到比较常用的启发式搜索方法有A*搜索，目前的算法都没有用到~

2.2 输入功能

输入功能必须要有,就控制台输入了, 可以把代码移到C#上，用Winform做一个GUI界面~

int origin[3][3],target[3][3];

定义3*3的数组表示九宫格的九个数字, origin分别为初始状态和目标状态, 循环读入即可. 至于为何不使用1*9的一维数组, 照顾要是考虑到后续搜索路径的问题, 3*3的路径比较容易设计, 其中一个数组下标变化1即可, 而对于1*9, 感觉有点复杂(后来发现其实并不是, 将下标分别+-3和+-1就得到了四个路径, 再判断新状态是否有效即可, 好像还比3*3简单点)

2.3 状态判重

对于每个状态必须判重，也要判断是否与目标状态相同，如果是将9个元素逐个比较，太耗时，肯定是得用到hash，hash方法http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html中的境界二有提到，但是我没看懂“逆序值”这个词写的不清楚，感觉应该是排列组合中的一个名词，但是搜出来的都不对，于是自己设计个不能称之为hash的hash函数, 因为这个方法的信息量没有压缩, 是可逆的
对于每种状态只需要唯一对应一个值即可，于是想着把每种状态的数字串成字符串当作hash值，这肯定不是好方法，至少本来只需要9!=362880个int型元素就能存下所有状态，而现在对于每种状态都是一个9位长的字符串不过有一个好处就是存储的信息相对而言多了, 对于最后输出所有路径有所帮助。

string getHash(int v[3][3]) {                           //将状态的数字排序转换为字符串,作为hash值
    string hashString = "";
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            stringstream sstream;
            string str;
            sstream << v[i][j];                          //注意sstream输入是<<而不是iostream的>>
            sstream >> str;
            hashString += str;
        }
    }
    return hashString;
}

2.4 建立初始表结构

根据给定初始状态建立初始的表结构，找到0的位置即为可移动的空格位置并记录，找到得到hash值并记录

VertexOfGraph createGraph(int vertex[3][3]) {
    VertexOfGraph returnGraph;
    for(int i=0; i < 3; i++) {
        for(int j = 0; j <3; j++) {
            returnGraph.vertex[i][j] = vertex[i][j];
            if(vertex[i][j] == 0) {
                returnGraph.x = i;
                returnGraph.y = j;
            }
        }
    }
    returnGraph.hashValue = getHash(vertex);

    return returnGraph;
}

2.5 bfs广度搜索

搜索结果返回一个map表，将每一状态转换之后的状态作为key值，原状态作为value，一一对应保存起来，最后通过此表可得到实际路径

map<string,string> bfsSearch(VertexOfGraph graph,string targetHash,map<string,bool> visited) {
    int direction[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} };
    queue<VertexOfGraph> que;
    que.push(graph);
    map<string,string> route;

    while(!que.empty()) {
        VertexOfGraph movingVertex = que.front();
        //cout << movingVertex.hashValue << endl;       //测试遍历结果
        VertexOfGraph savingVertex = movingVertex;
        que.pop();

        for(int i = 0; i < 4; i++) {
            movingVertex = savingVertex;
            movingVertex.x = savingVertex.x + direction[i][0];
            movingVertex.y = savingVertex.y + direction[i][1];
            if(!movingVertex.isValid()) {
                continue;
            } else {
                movingVertex.newStatus(savingVertex.x, savingVertex.y);
                movingVertex.hashValue = getHash(movingVertex.vertex);
                if(visited.find(movingVertex.hashValue)==visited.end()) {
                    visited[movingVertex.hashValue] = true;
                    route[movingVertex.hashValue] = savingVertex.hashValue;

                    que.push(movingVertex);
                }
                if(movingVertex.hashValue == targetHash) {
                    return route;
                }
            }
        }
    }
    return route;
}

bfs的想法是，从第一个状态开始遍历可能的所有状态，对于当前状态，找出其可以转换的状态，将他们全部放入队列的尾部，保存route，并判断他们是否是目标状态，若是，返回route退出，否则不停取出队列的头元素，执行相同操作

2.6 找回实际路径

从route和目标hash值中找回实际路径，并输出

void display(map<string,string> searchRoute,string targetHash) {
    stack<string> shortestRoute;
    shortestRoute.push(targetHash);

    string nextWay = targetHash;
    while( searchRoute.find(nextWay) != searchRoute.end() ) {
        nextWay = searchRoute[nextWay];
        shortestRoute.push(nextWay);
    }

    cout << endl;
    int counts = 0;
    while( !shortestRoute.empty() ) {
        string displayString = shortestRoute.top();
        shortestRoute.pop();

        if( (counts == 0) && (displayString == targetHash) ) {       //如果堆栈内只有一个字符串元素,且等于targetHash,那么说明遍历了所有的状态也无法达到目标状态
            cout << "Sorry, but you can not reach the target status, and you can try another status instead." << endl;
            break;
        }

        cout << "Step " << counts << " :";
        counts++;
        for(unsigned int i = 0; i < displayString.length(); i++) {
            if( i % 3 == 0 ) {
                cout << endl;
            }
            cout << displayString.substr(i,1) << ' ';
        }
        cout << endl;
    }
    if( counts > 1 ) {
        cout << "Totally, you used " << counts-1 << " steps to the target status." << endl;
    }
}

源码

源码可以在这里看到