2 cloris cy Cloris_CY 于 2016.03.04 14:18 提问

用分支限界法解决8数码问题,它的限界函数应该是什么?求各位大神解答! 2C

一个8数码问题是将如图所示的初始格局中的小格子的数字经过若干步移动后(只能水平和垂直移动到一个空白处)形成如图所示的目标格局。
例:
2 8 3 1 2 3
1 0 4 ---->8 0 4
7 6 5 7 6 5
利用分支限界法解决
在线等待各位大神指教,急!

1个回答

u013596119
u013596119   Rxr 2016.03.04 22:40

不知道你说的分支界限法师什么。。。全给你放上来吧,很早以前做过的
ids,bfs,A*有两个
ids:

 #include <iostream>
#include <list>
#include <queue>
using namespace std;

int all[3][3];
int goal[3][3];
int curX, curY;

class state{
public:
    int allState[3][3];
    state* parent = NULL;
    bool checkVisited(){
        if (parent == NULL){
            return false;
        }
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (all[i][j] != (*parent).allState[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    void copyState(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                allState[i][j] = all[i][j];
            }

        }
    }
    void changeAll(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                all[i][j] = allState[i][j];
            }

        }
    }
    void printState(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                cout << allState[i][j];
            }
            cout << endl;
        }
    }
    bool checkSame(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (allState[i][j] != all[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    bool checkGoal(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (allState[i][j] != goal[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
};


list<state> visited;
queue<state> tree;



void printAll(){
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cout << all[i][j];
        }
        cout << endl;
    }
}

void input(){
    cout << "Iterative Deepening Search for 8-puzzle" << endl;
    cout << "Input Format: 7 2 4 5 0 6 8 3 1" << endl;
    cout << endl;
    cout << "Please input the initial state:" << endl;
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cin >> all[i][j];
        }
    }
    cout << "Please input the goal state:" << endl;
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cin >> goal[i][j];
        }
    }
}

void getCurPo(){
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            if (all[i][j] == 0){
                curX = i;
                curY = j;
                return;
            }
        }
    }
}

void moveUp(){
    getCurPo();
    all[curX][curY] = all[curX - 1][curY];
    all[curX - 1][curY] = 0;
}

void moveDown(){
    getCurPo();
    all[curX][curY] = all[curX + 1][curY];
    all[curX + 1][curY] = 0;
}

void moveLeft(){
    getCurPo();
    all[curX][curY] = all[curX][curY - 1];
    all[curX][curY - 1] = 0;
}

void moveRight(){
    getCurPo();
    all[curX][curY] = all[curX][curY + 1];
    all[curX][curY + 1] = 0;
}

bool checkVisited(){
    if (visited.empty()){
        return false;
    }
    else{
        list<state>::iterator listi;
        for (listi = visited.begin(); listi != visited.end(); listi++){
            if ((*listi).checkSame()){
                return true;
            }
        }
    }
    return false;
}
state finalstate;
int totalmove = 0;
bool dfs(state s,int l,int limit){
    visited.push_back(s);
    state newup;
    newup.parent = &visited.back();
    state newRight;
    newRight.parent = &visited.back();
    state newDown;
    newDown.parent = &visited.back();
    state newleft;
    newleft.parent = &visited.back();
    if (s.checkGoal()){
        finalstate = s;
        return true;
    }
    if (l==limit){
        return false;
    }
    s.changeAll();
    getCurPo();
    if (curX != 0){
        moveUp();
        if (!s.checkVisited()){

            newup.copyState();
            totalmove++;
            //newup.printState();
            //cout << endl;
            if (dfs(newup, l + 1, limit)){
                return true;
            }
        }
        moveDown();
    }
    getCurPo();
    if (curX != 2){
        moveDown();
        if (!s.checkVisited()){

            newDown.copyState();
            totalmove++;

            //newDown.printState();
            //cout << endl;
            if (dfs(newDown, l + 1, limit)){
                return true;
            }
        }
        moveUp();
    }
    getCurPo();
    if (curY != 0){
        moveLeft();
        if (!s.checkVisited()){

            newleft.copyState();
            totalmove++;

            //newleft.printState();
            //cout << endl;
            if (dfs(newleft, l + 1, limit)){
                return true;
            }
        }
        moveRight();
    }
    getCurPo();
    if (curY != 2){
        moveRight();
        if (!s.checkVisited()){

            newRight.copyState();
            totalmove++;

            //newRight.printState();
            //cout << endl;
            if (dfs(newRight, l + 1, limit)){
                return true;
            }
        }
        moveLeft();
    }
    return false;
}

int main(){
    input();

    state initState;
    initState.copyState();
    int limit = 1;

    while (dfs(initState,0,limit)==false){
        limit++;
        visited.clear();
    }

    list<state> procedure;
    state temp = finalstate;
    procedure.push_front(temp);
    //s.printState();
    cout << endl;
    while ((temp.parent) != NULL){
        state* thisparent = temp.parent;
        procedure.push_front(*(temp.parent));
        temp = *(temp.parent);
    }
    list<state>::iterator listi2;
    for (listi2 = procedure.begin(); listi2 != procedure.end(); listi2++){
        (*listi2).printState();
        cout << endl;
    }
    cout << "Total Steps: " << procedure.size() - 1 << endl;
    cout << "Total Search Moves: " << totalmove << endl;


    system("PAUSE");

}

bfs:

 #include <iostream>
#include <list>
#include <queue>
using namespace std;

int all[3][3];
int goal[3][3];
int curX, curY;

class state{
public:
    int height = 0;
    int allState[3][3];
    state* parent = NULL;
    bool checkVisited(){
        if (parent==NULL){
            return false;
        }
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (all[i][j]!=(*parent).allState[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    void copyState(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                allState[i][j] = all[i][j];
            }

        }
    }
    void changeAll(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                all[i][j] = allState[i][j];
            }

        }
    }
    void printState(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                cout << allState[i][j];
            }
            cout << endl;
        }
    }
    bool checkSame(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (allState[i][j]!=all[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    bool checkGoal(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (allState[i][j] != goal[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
};


list<state> visited;
list<state> tempvisited;
queue<state> tree;



void printAll(){
     for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
             cout<<all[i][j];
        }
        cout<<endl;
    }
}

void input(){
    cout<<"BFS for 8-puzzle"<<endl;
    cout << "Input Format: 7 2 4 5 0 6 8 3 1" << endl;
    cout << endl;
    cout<<"Please input the initial state:"<<endl;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
             cin>>all[i][j];
        }
    }
    cout << "Please input the goal state:" << endl;
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cin >> goal[i][j];
        }
    }

}

void getCurPo(){
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(all[i][j]==0){
                curX=i;
                curY=j;
                return;
            }
        }
    }
}

void moveUp(){
    getCurPo();
    all[curX][curY]=all[curX-1][curY];
    all[curX-1][curY]=0;
}

void moveDown(){
    getCurPo();
    all[curX][curY]=all[curX+1][curY];
    all[curX+1][curY]=0;
}

void moveLeft(){
    getCurPo();
    all[curX][curY]=all[curX][curY-1];
    all[curX][curY-1]=0;
}

void moveRight(){
    getCurPo();
    all[curX][curY]=all[curX][curY+1];
    all[curX][curY+1]=0;
}

bool checkVisited(){
    if (visited.empty()){
        return false;
    }
    else{
        list<state>::iterator listi;
        for (listi = visited.begin(); listi != visited.end();listi++){
            if ((*listi).checkSame()){
                return true;
            }
        }
        list<state>::iterator listi11;
        for (listi11 = tempvisited.begin(); listi11 != tempvisited.end(); listi11++){
            if ((*listi11).checkSame()){
                return true;
            }
        }
    }
    return false;
}

int main(){
    input();
    int totalmove = 0;
    state initState;
    initState.copyState();
    tree.push(initState);
    while (!tree.empty()){
        state s=tree.front();
        visited.push_back(s);
        tree.pop();
        if (s.checkGoal()){
            list<state> procedure;
            state temp = s;
            procedure.push_front(temp);
            //s.printState();
            cout << endl;
            while ((temp.parent) != NULL){
                state* thisparent = temp.parent;
                procedure.push_front(*(temp.parent));
                temp = *(temp.parent);
            }
            list<state>::iterator listi2;
            for (listi2 = procedure.begin(); listi2 != procedure.end(); listi2++){
                (*listi2).printState();
                cout << endl;
            }
            cout << "Total Steps: " << procedure.size() - 1 << endl;
            cout << "Total Search Moves: " << totalmove << endl;
            break;
        }
        s.changeAll();
        getCurPo();
        //cout << s.height<<endl;
        //printAll();
        //cout << endl;
        if (curX!=0){
            moveUp();
            if (!s.checkVisited()){
                state newup;
                newup.height = visited.back().height + 1;
                newup.parent = &visited.back();
                newup.copyState();
                //newup.printState();
                //cout << endl;
                tree.push(newup);
                totalmove++;
            //  tempvisited.push_back(newup);
            }
            moveDown();
        }
        getCurPo();
        if (curX != 2){
            moveDown();
            if (!s.checkVisited()){
                state newDown;
                newDown.height = visited.back().height + 1;

                newDown.parent = &visited.back();
                newDown.copyState();
                //newDown.printState();
                //cout << endl;
                tree.push(newDown);
                totalmove++;
            //  tempvisited.push_back(newDown);

            }
            moveUp();
        }
        getCurPo();
        if (curY != 0){
            moveLeft();
            if (!s.checkVisited()){
                state newleft;
                newleft.height = visited.back().height + 1;

                newleft.parent = &visited.back();
                newleft.copyState();
                //newleft.printState();
                //cout << endl;
                tree.push(newleft);
                totalmove++;
            //  tempvisited.push_back(newleft);

            }
            moveRight();
        }
        getCurPo();
        if (curY != 2){
            moveRight();
            if (!s.checkVisited()){
                state newRight;
                newRight.height = visited.back().height + 1;

                newRight.parent = &visited.back();
                newRight.copyState();
                //newRight.printState();
                //cout << endl;
                tree.push(newRight);
                totalmove++;
            //  tempvisited.push_back(newRight);

            }
            moveLeft();
        }
        //tempvisited.clear();
    }



    system("PAUSE");

} 

A*1:

 #include <iostream>
#include <list>

using namespace std;

int all[3][3];
int goal[3][3];
int curX, curY;

class state{
public:
    int allState[3][3];
    state* parent = NULL;
    int h = 0;
    int g = 0;
    int height = 0;
    bool checkVisited(){
        if (parent == NULL){
            return false;
        }
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (all[i][j] != (*parent).allState[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    void copyState(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                allState[i][j] = all[i][j];
            }

        }
    }
    void changeAll(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                all[i][j] = allState[i][j];
            }

        }
    }
    void printState(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                cout << allState[i][j];
            }
            cout << endl;
        }
    }
    bool checkSame(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (allState[i][j] != all[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    bool checkGoal(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (allState[i][j] != goal[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    void heuristic(){
        int result = 0;
        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                if (allState[i][j] != goal[i][j]&&goal[i][j]!=0){
                    result++;
                }
            }
        }
        h = result;
    }
};


list<state> visited;
list<state> tree;
list<state> tempvisited;

bool compareRules(state  a,state  b){
    int atotal = 0, btotal = 0;
    atotal = a.h + a.g;
    btotal = b.h + b.g;
    if (atotal>=btotal){
        return true;
    }
    else{
        return false;
    }
}


void printAll(){
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cout << all[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

void input(){
    cout << "A* for 8-puzzle (h1)" << endl;
    cout << "Input Format: 7 2 4 5 0 6 8 3 1" << endl;
    cout << endl;
    cout << "Please input the initial state:" << endl;
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cin >> all[i][j];
        }
    }
    cout << "Please input the goal state:" << endl;
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cin >> goal[i][j];
        }
    }

}

void getCurPo(){
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            if (all[i][j] == 0){
                curX = i;
                curY = j;
                return;
            }
        }
    }
}

void moveUp(){
    getCurPo();
    all[curX][curY] = all[curX - 1][curY];
    all[curX - 1][curY] = 0;
}

void moveDown(){
    getCurPo();
    all[curX][curY] = all[curX + 1][curY];
    all[curX + 1][curY] = 0;
}

void moveLeft(){
    getCurPo();
    all[curX][curY] = all[curX][curY - 1];
    all[curX][curY - 1] = 0;
}

void moveRight(){
    getCurPo();
    all[curX][curY] = all[curX][curY + 1];
    all[curX][curY + 1] = 0;
}

bool checkVisited(){
    if (visited.empty()){
        return false;
    }
    else{
        list<state>::iterator listi;
        for (listi = visited.begin(); listi != visited.end(); listi++){
            if ((*listi).checkSame()){
                return true;
            }
        }
        list<state>::iterator listtemp;
        for (listtemp = tempvisited.begin(); listtemp != tempvisited.end(); listtemp++){
            if ((*listtemp).checkSame()){
                return true;
            }
        }
    }
    return false;
}

int main(){
    input();
    int totalmove = 0;
    state initState;
    initState.copyState();
    tree.push_back(initState);
    while (!tree.empty()){
        list<state>::iterator listi1;
        state tempmin=*tree.begin();
        int temppo = 0;
        int finalpo = 0;
        for (listi1 = tree.begin(); listi1 != tree.end(); listi1++){
            if ((*listi1).g + (*listi1).h < tempmin.g + tempmin.h){
                tempmin = *listi1;
                finalpo = temppo;
            }
            temppo++;
        }

        state s = tempmin;
        visited.push_back(s);
        //cout << s.h << endl;
        //cout << s.g << endl;
        //cout << endl;
        list<state>::iterator listi3=tree.begin();
        advance(listi3, finalpo);
        if (listi3!=tree.end()){
            tree.erase(listi3);
        }
        if (s.checkGoal()){
            list<state> procedure;
            state temp = s;
            procedure.push_front(temp);
            //s.printState();
            cout << endl;
            while ((temp.parent) != NULL){
                state* thisparent = temp.parent;
                procedure.push_front(*(temp.parent));
                temp = *(temp.parent);
            }
            list<state>::iterator listi2;
            for (listi2 = procedure.begin(); listi2 != procedure.end(); listi2++){
                (*listi2).printState();
                cout << endl;
            }
            cout << "Total Steps: " << procedure.size() - 1 << endl;
            cout << "Total Search Moves: " << totalmove << endl;
            break;
        }
        s.changeAll();
        getCurPo();
        //printAll();
        if (curX != 0){
            moveUp();
            if (!s.checkVisited()){
                state newup;
            //  newup.height = visited.back().height + 1;
                newup.parent = &visited.back();
                newup.copyState();
                newup.heuristic();
                newup.g = visited.back().g + 1;
                //newup.printState();
                //cout << endl;
                tree.push_back(newup);
                totalmove++;
                //tempvisited.push_back(newup);
            }
            moveDown();
        }
        getCurPo();
        if (curX != 2){
            moveDown();
            if (!s.checkVisited()){
                state newDown;
                //newDown.height = visited.back().height + 1;

                newDown.parent = &visited.back();
                newDown.copyState();
                newDown.heuristic();
                newDown.g = visited.back().g + 1;
                //newDown.printState();
                //cout << endl;
                tree.push_back(newDown);
                totalmove++;
                //tempvisited.push_back(newDown);
            }
            moveUp();
        }
        getCurPo();
        if (curY != 0){
            moveLeft();
            if (!s.checkVisited()){
                state newleft;
            //  newleft.height = visited.back().height + 1;

                newleft.parent = &visited.back();
                newleft.copyState();
                newleft.heuristic();
                newleft.g = visited.back().g + 1;
                //newleft.printState();
                //cout << endl;
                tree.push_back(newleft);
                totalmove++;
                //tempvisited.push_back(newleft);
            }
            moveRight();
        }
        getCurPo();
        if (curY != 2){
            moveRight();
            if (!s.checkVisited()){
                state newRight;
            //  newRight.height = visited.back().height + 1;

                newRight.parent = &visited.back();
                newRight.copyState();
                newRight.heuristic();
                newRight.g = visited.back().g + 1;
                //newRight.printState();
                //cout << endl;
                tree.push_back(newRight);
                totalmove++;
                //tempvisited.push_back(newRight);
            }
            moveLeft();
        }
        //tempvisited.clear();
    }



    system("PAUSE");

}

A*2:

 #include <iostream>
#include <list>
#include "math.h"
using namespace std;

int all[3][3];
int goal[3][3];
int curX, curY;

class state{
public:
    int allState[3][3];
    state* parent = NULL;
    int h = 0;
    int g = 0;
    bool checkVisited(){
        if (parent == NULL){
            return false;
        }
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (all[i][j] != (*parent).allState[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    void copyState(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                allState[i][j] = all[i][j];
            }

        }
    }
    void changeAll(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                all[i][j] = allState[i][j];
            }

        }
    }
    void printState(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                cout << allState[i][j];
            }
            cout << endl;
        }
    }
    bool checkSame(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (allState[i][j] != all[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    bool checkGoal(){
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (allState[i][j] != goal[i][j]){
                    return false;
                }
            }

        }
        return true;
    }
    void heuristic(){
        int result = 0;
        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                bool temp = false;
                for (int k = 0; k < 3; k++){
                    if (temp) break;
                    for (int m = 0; m < 3; m++){
                        if (goal[i][j] != 0 && goal[i][j] == allState[k][m]){
                            temp = true;
                            result += abs(k - i) + abs(m - j);
                            break;
                        }
                    }
                }
            }
        }
        h = result;
    }
};


list<state> visited;
list<state> tree;

bool compareRules(state  a, state  b){
    int atotal = 0, btotal = 0;
    atotal = a.h + a.g;
    btotal = b.h + b.g;
    if (atotal >= btotal){
        return true;
    }
    else{
        return false;
    }
}


void printAll(){
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cout << all[i][j];
        }
        cout << endl;
    }
}

void input(){
    cout << "A* for 8-puzzle (h2)" << endl;
    cout << "Input Format: 7 2 4 5 0 6 8 3 1" << endl;
    cout << endl;
    cout << "Please input the initial state:" << endl;
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cin >> all[i][j];
        }
    }
    cout << "Please input the goal state:" << endl;
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            cin >> goal[i][j];
        }
    }

}

void getCurPo(){
    for (int i = 0; i<3; i++){
        for (int j = 0; j<3; j++){
            if (all[i][j] == 0){
                curX = i;
                curY = j;
                return;
            }
        }
    }
}

void moveUp(){
    getCurPo();
    all[curX][curY] = all[curX - 1][curY];
    all[curX - 1][curY] = 0;
}

void moveDown(){
    getCurPo();
    all[curX][curY] = all[curX + 1][curY];
    all[curX + 1][curY] = 0;
}

void moveLeft(){
    getCurPo();
    all[curX][curY] = all[curX][curY - 1];
    all[curX][curY - 1] = 0;
}

void moveRight(){
    getCurPo();
    all[curX][curY] = all[curX][curY + 1];
    all[curX][curY + 1] = 0;
}

bool checkVisited(){
    if (visited.empty()){
        return false;
    }
    else{
        list<state>::iterator listi;
        for (listi = visited.begin(); listi != visited.end(); listi++){
            if ((*listi).checkSame()){
                return true;
            }
        }
    }
    return false;
}

int main(){
    input();
    int totalmove = 0;
    state initState;
    initState.copyState();
    tree.push_back(initState);
    while (!tree.empty()){
        list<state>::iterator listi1;
        state tempmin = *tree.begin();
        int temppo = 0;
        int finalpo = 0;
        for (listi1 = tree.begin(); listi1 != tree.end(); listi1++){
            if ((*listi1).g + (*listi1).h < tempmin.g + tempmin.h){
                tempmin = *listi1;
                finalpo = temppo;
            }
            temppo++;
        }

        state s = tempmin;
        //cout << s.g << endl;
    //  cout << s.h << endl;
        //cout << endl;
        visited.push_back(s);
        list<state>::iterator listi3 = tree.begin();
        advance(listi3, finalpo);
        if (listi3 != tree.end()){
            tree.erase(listi3);
        }
        if (s.checkGoal()){
            list<state> procedure;
            state temp = s;
            procedure.push_front(temp);
            //s.printState();
            cout << endl;
            while ((temp.parent) != NULL){
                state* thisparent = temp.parent;
                procedure.push_front(*(temp.parent));
                temp = *(temp.parent);
            }
            list<state>::iterator listi2;
            for (listi2 = procedure.begin(); listi2 != procedure.end(); listi2++){
                (*listi2).printState();
                cout << endl;
            }
            cout << "Total Steps: " << procedure.size() - 1 << endl;
            cout << "Total Search Moves: " << totalmove << endl;
            break;
        }
        s.changeAll();
        getCurPo();
        //  printAll();
        if (curX != 0){
            moveUp();
            if (!s.checkVisited()){
                state newup;
                newup.parent = &visited.back();
                newup.copyState();
                newup.heuristic();
                newup.g = visited.back().g + 1;
                //newup.printState();
                //cout << endl;
                tree.push_back(newup);
                totalmove++;
            }
            moveDown();
        }
        getCurPo();
        if (curX != 2){
            moveDown();
            if (!s.checkVisited()){
                state newDown;
                newDown.parent = &visited.back();
                newDown.copyState();
                newDown.heuristic();
                newDown.g = visited.back().g + 1;
                //newDown.printState();
                //cout << endl;
                tree.push_back(newDown);
                totalmove++;

            }
            moveUp();
        }
        getCurPo();
        if (curY != 0){
            moveLeft();
            if (!s.checkVisited()){
                state newleft;
                newleft.parent = &visited.back();
                newleft.copyState();
                newleft.heuristic();
                newleft.g = visited.back().g + 1;
                //newleft.printState();
                //cout << endl;
                tree.push_back(newleft);
                totalmove++;

            }
            moveRight();
        }
        getCurPo();
        if (curY != 2){
            moveRight();
            if (!s.checkVisited()){
                state newRight;
                newRight.parent = &visited.back();
                newRight.copyState();
                newRight.heuristic();
                newRight.g = visited.back().g + 1;
                //newRight.printState();
                //cout << endl;
                tree.push_back(newRight);
                totalmove++;

            }
            moveLeft();
        }
    }



    system("PAUSE");

}
Cloris_CY
Cloris_CY 回复DarthHaric: 虽然您提到的思路并不是我所需要的,但还是十分感谢您的帮助!![图片说明](http://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/001/face/0.gif)
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!