Cloris_CY 于 2016.03.04 14:18 提问

2 8 3 1 2 3
1 0 4 ---->8 0 4
7 6 5 7 6 5

1个回答

u013596119   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;
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();
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();
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 回复DarthHaric: 虽然您提到的思路并不是我所需要的，但还是十分感谢您的帮助！![图片说明](http://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/001/face/0.gif)
2 年多之前 回复

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}中。

1.先说一下顺序队列来建立数据结构   /************************************************************************ 顺序队列（循环队列）实现FIFO分支限界法--装载问题把数据结构换了一下， 仅仅把之

#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