最近我研究了一下八数码问题,采用迭代深入A*搜索(IDA*)和递归深入优先搜索.实现八数码难题.IDA*即迭代加深的A*搜索，实现代码是最简练的，无须状态判重，无需估价排序。那么就用不到哈希表，堆上也不必应用，空间需求变的超级少。效率上，应用了曼哈顿距离。同时可以根据深度和h值，在找最优解的时候，对超过目前最优解的地方进行剪枝，这可以导致搜索深度的急剧减少，所以，这，是一个致命的剪枝！因此，IDA*大部分时候比A*还要快，可以说是A*的一个优化版本！IDA*算法跟典型的迭代深入算法的差别在于IDA*采用耗散值而不是树的深度来减支的.以下是这个程序的；递归最佳优先搜索是动态调整迭代截断值值的一种方法， 优势在于可以在搜索过程中更加灵

活得选择最优路径，算法伪代码参照<<人工智能一种现代化方法>>。


代码编译环境采用的是vs2012，移植到g++编译器，可能会不兼容，需要酌情修改。

启发函数：

启发函数采用曼哈顿距离。

例如在平面上，坐标（x1, y1）的i点与坐标（x2, y2）的j点的曼哈顿距离为：

d(i,j)=|X1-X2|+|Y1-Y2|.

代码见功能中的f和dist函数


int dist(int p1,int p2){
    int dx=abs(p1%3-p2%3+0.0);
    int dy=abs(p1/3-p2/3+0.0);
    return dx+dy;
}
int f(int g,int* arr){
    int i,s = 0,hn=0;
    for(i=0;i<9;i++){
        s=s*9+arr[i];
    }
    for(i=8;i>=0;i--)
    {
        switch(s%9)
        {
            case 0: hn+=dist(i,8); break;
            case 1: hn+=dist(i,0); break;
            case 2: hn+=dist(i,3); break;
            case 3: hn+=dist(i,6); break;
            case 4: hn+=dist(i,1); break;
            case 5: hn+=dist(i,4); break;
            case 6: hn+=dist(i,7); break;
            case 7: hn+=dist(i,2); break;
            case 8: hn+=dist(i,5); break;
            default: break;
        }
        s/=9;
    }
    return g+hn;
}


IDA*的伪代码如下：

八数码的问题


IDA*函数代码：

char* idas(int* s, int* g){
    char* path = new char[200];     //保存路径
    stack<Node *> stk;
    Node * p;
    p->deepth = 0;
    limit = f(p->deepth,s);
    stk.push(new Node(s));
    while(limit<200){
        next_limit = 200;
        while(!stk.empty()){
            p = stk.top();
            stk.pop();
            if(p->deepth!=0){
                path[p->deepth-1] = p->action;
            }
            if(f(p->deepth,p->arr) > limit){
                next_limit = ((f(p->deepth,p->arr) > next_limit)?next_limit:f(p->deepth,p->arr));
            }
            else{
                if(true == p->isGoal()){
                    path[p->deepth] = '\0';
                    return path;
                }
                vector<Node*> v = p->getSons();
                for(int i=0;i<v.size();i++){
                    v[i]->deepth = p->deepth+1;
                    stk.push(v[i]);
                }
            }
        }
        limit = next_limit;
    }
    return NULL;
}

递归最佳优先搜索是一个模仿标准的递归算法，不沿当前不确定路径继续下去，而是记录从当前节点的祖先可得到的最佳可替换路径的f值。如果当前节点超过了这个限制，递归将转回到替换路径上去。当递归回溯后，对回溯前的当前路径上的每个节点。RBFS用其子节点的最佳f值替换其f值。这样在下一次判断时方便我们确定是否再次扩展此值。

char* rbfs(int* s, int* g){
    char * path = new char[100];
    Node * node = new Node(s);  //初始化起始节点
    node->cost = f(0,s);       
    rbfs(node,1000,path);       //递归递归优先搜索
    return path;
}
Node* rbfs(Node *node,int limit,char * path){
    if(node->isGoal(targetArr)){
        path[node->deepth] = '\0';
        return node;
    }
    vector<Node *> vt = node->getSons();
    if(vt.empty()){
        node->cost = MAXVALUE;  //1000代表无穷大
        return NULL;
    }
    for(int i=0;i<vt.size();i++){
        vt[i]->cost = Max(f(vt[i]->deepth,vt[i]->arr),f(node->deepth,node->arr));
    }
    while(true){
        //排序方便求最大最小
        sort(vt.begin(),vt.end(),cmp);
        Node* best = vt[0];
        path[best->deepth-1] = best->action;
        if(best->cost > limit){ //如果扩展的子节点们的最小值比之前的节点的次大值大，返回NULL，把当前的代价赋为扩展子节点的最小值，方便以后判断是否扩展该节点，这是一个重要的剪枝
            node->cost = best->cost;
            return NULL;
        }
        //Min((vt.size()==1 ? MAXVALUE:vt[1]->cost),limit)是求次大节点的耗散值与上层所有节点的次大值的最小者
        Node * result = rbfs(best,Min((vt.size()==1 ? MAXVALUE:vt[1]->cost),limit),path);
        if(NULL != result) return result;  //找到目标  一层一层往上返回
    }
}