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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
八数码问题 队列式分支限界法
随机给定一个3×3的矩阵,其元素为8个不同的数码,起始状态为S0,目标状态为Sg,要求用两种或以上的方法设计优先队列式分支限界法,寻找从初始状态变换到目标状态的最优解,说明不同的优先选择策略变换到最终状态用了多少步,并对获得的结果做出比较分析。最终状态均如Sg表示。
最优装载问题或者01背包问题的分支限界法求解
问题的提出:背包的容量为 c,物品的个数为n,物品的重量依次为w1,w2,......,wn,求背包中的最大容量。01背包问题和下面所描述的装载问题解法一致,大家可以认为是同一类问题。有一批公n个集装箱的两艘载重重量为C1,C2的轮船,集装箱的重量分别为w1,w2,......,wn,我们知道集装箱是不能拆开分别装入两艘船上的,所以该问题和01背包问题是一类问题,此时我们只需要考虑将第一艘船尽量装
分支限界法解决装载问题
分支限界法解决装载问题 C++实现。 分支限界法类似于回溯法,也是一种在问题的解空间树T中搜索问题解的算法。
分支限界法之最大团问题
A,最大团问题:给定一个无向图G=(V,E),其中V代表顶点集合,E代表边的集合。,如果U是V的子集,且对于U中任意两个顶点u和v都是相连的,即u-->v属于E,则称顶点子集U是图G的完全子图或者G的图。显然最大团就是指满足上述条件且含有顶点数最多的团。比如下图所示: 子集{A, B}是G 的大小为2 的团。这个团不是极大团(因为顶点数不是最多的),因为它包含在G 的更大团{A,B, E}中。
分支限界法解决装载问题之FIFO队列方式的总结
1.先说一下顺序队列来建立数据结构   /************************************************************************ 顺序队列(循环队列)实现FIFO分支限界法--装载问题把数据结构换了一下, 仅仅把之
分支限界问题分析--和回溯法的区别以及在何时用的区别
分支限界法类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的
运用分支限界法解决布线问题
#include typedef struct { int row; int col; }Position; int FindPath (Position start, Position finish, int &PathLen, Position *&path) { //计算从起始位置start到目标位置finish的最短布线路径,找到返回1,否则,返回0 int i; i
最大团问题-分支限界算法
算法设计与分析课上,老师布置了一个讲解最大团的分支限界算法的went
装载问题-分支限界算法-java实现
本例采用java编写的装载问题,采用的是FIFO队列形式,参考:算法设计与分析
分支限界法解决N皇后问题
使用分支限界法解决N皇后问题。因为是广度优先,而且占用比较多的额外空间,所以并不是解N皇后问题的很好的算法,主要是理解分支限界法的使用。