一个8数码问题是将如图所示的初始格局中的小格子的数字经过若干步移动后（只能水平和垂直移动到一个空白处）形成如图所示的目标格局。
例：
2 8 3 1 2 3
1 0 4 ---->8 0 4
7 6 5 7 6 5
利用分支限界法解决
在线等待各位大神指教，急！
不知道你说的分支界限法师什么。。。全给你放上来吧，很早以前做过的
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");
}