一个8数码问题是将如图所示的初始格局中的小格子的数字经过若干步移动后(只能水平和垂直移动到一个空白处)形成如图所示的目标格局。
例:
2 8 3 1 2 3
1 0 4 ---->8 0 4
7 6 5 7 6 5
利用分支限界法解决
在线等待各位大神指教,急!
用分支限界法解决8数码问题,它的限界函数应该是什么?求各位大神解答!
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答
- u52983610 2016-03-04 14: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"); }
解决 无用评论 打赏 举报
悬赏问题
- ¥30 这是哪个作者做的宝宝起名网站
- ¥60 版本过低apk如何修改可以兼容新的安卓系统
- ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
- ¥50 有数据,怎么建立模型求影响全要素生产率的因素
- ¥50 有数据,怎么用matlab求全要素生产率
- ¥15 TI的insta-spin例程
- ¥15 完成下列问题完成下列问题
- ¥15 C#算法问题, 不知道怎么处理这个数据的转换
- ¥15 YoloV5 第三方库的版本对照问题
- ¥15 请完成下列相关问题!