main.cpp

分别用深度优先和广度优先来算八数码问题

// h(n): 将牌“不在位”的距离和
//每个Node都有一个唯一的ID与之对应
#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<fstream>
#include<string>
using namespace std;
#define  UP		0
#define  DOWN	1
#define  LEFT	2
#define	 RIGHT  3
ofstream outfile;
class Node					//代表每个节点处的数码状态
{
private:
	int x,y;				//记录0所处的位置
	int parentID;			// 
public:
	int count;				// 记录此数码状态是通过多少次移动达到的
	int state[3][3];		//记录当前数码的状态
	Node(int state[3][3]){
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++){
				if (state[i][j] == 0){
					x = i;	// x:行
					y = j;	// y:列
				}
				this->state[i][j] = state[i][j];
			}
		count = 0;
		parentID = 0;
	}
	/*Node(Node const& cNode){
		outfile<<"= constuction"<<endl;
		this->x = cNode.x;
		this->y = cNode.y;
		this->count = cNode.count;
		for (int i = 0; i < 3; i++)
			for ( int j = 0; j < 3; j++){
				this->state[i][j] = cNode.state[i][j];
			}
		this->parent = cNode.parent;
	}*/
	int f() const{	                //计算当前状态与目标状态之间的评价函数
		return count + h();
	}
	int h() const{
		int h = 0;
		for (int i = 0; i < 3; i++)
			for ( int j = 0; j < 3; j++){
				switch (state[i][j]){
					case 0:
						break;
					case 1:
						h += abs(i) + abs(j);
						break;
					case 2:
						h += abs(i) + abs(j - 1);
						break;
					case 3:
						h += abs(i) + abs(j - 2);
						break;
					case 4:
						h += abs(i - 1) + abs(j - 2);
						break;
					case 5:
						h += abs(i - 2) + abs(j - 2);
						break;
					case 6:
						h += abs(i - 2) + abs(j - 1);
						break;
					case 7:
						h += abs(i - 2) + abs(j);
						break;
					case 8:
						h += abs(i - 1) + abs(j);
						break;
					default:;
						//outfile<<"h(n) error!"<<endl;
				}
			}
		return h;
	}
	bool operator < (Node const& right) const{		//重载小于号，用于set的排序
		/*outfile<<"operator <"<<endl;
		for (int i = 0; i < 3; i++){
			for (int j = 0; j < 3; j++){
				outfile<<state[i][j]<<" ";
			}
			outfile<<endl;
		}
		for (int i = 0; i < 3; i++){
			for (int j = 0; j < 3; j++){
				outfile<<right.state[i][j]<<" ";
			}
			outfile<<endl;
		}*/
		//right.print();
		bool flag = true;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++){
				if (this->state[i][j] != right.state[i][j]){
					//outfile<<"i="<<i<<", j="<<j<<endl;
					//outfile<<state[i][j]<<" "<<right.state[i][j]<<endl;
					flag = false;
					break;
				}
			}
		//outfile<<"flag="<<flag<<endl;
		if (flag == true)
			return false;
		else{ 
			if (f() == right.f()){
				return (this->getID() < right.getID());
			}
			else 
				return (f() < right.f());
		}
	}
	int getID()const{
		return int(state[0][0] + state[0][1]*8 + state[0][2]*pow(8.0,2)
			 + state[1][0]*pow(8.0,3) + state[1][1]*pow(8.0,4) + state[1][2]*pow(8.0,5)
			 + state[2][0]*pow(8.0,6) + state[2][1]*pow(8.0,7) + state[2][2]*pow(8.0,8));
	}
	bool isEqual(Node const& cNode)const{
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++){
				if (this->state[i][j] != cNode.state[i][j])
					return false;
			}
		return true;
	}
	bool operator == (Node const& right)const{
		return this->isEqual(right);
	}
	void move(int num){				//各种移动操作
		switch(num){
			case UP:
				state[x][y] = state[x - 1][y];
				state[x - 1][y] = 0;
				x--;
				count++;
				break;
			case DOWN:
				state[x][y] = state[x + 1][y];
				state[x + 1][y] = 0;
				x++;
				count++;
				break;
			case LEFT:
				state[x][y] = state[x][y - 1];
				state[x][y - 1] = 0;
				y--;
				count++;
				break;
			case RIGHT:
				state[x][y] = state[x][y + 1];
				state[x][y + 1] = 0;
				y++;
				count++;
				break;
			default:
				outfile<<"move error!"<<endl;
		}
	}
	int getX(){
		return x;
	}
	int getY(){
		return y;
	}
	int getParentID()const{
		return parentID;
	}
	void setParent(Node& cNode){
		parentID = cNode.getID();
		this->count = cNode.count + 1;
	}
};
set<Node> OPEN;			// OPEN表，按每个节点的f(n)进行排序，f(n)最小的即为此set的第一个元素
set<Node> CLOSED;
map<int, Node> IDMAP;	//用来存储ID到Node的映射

void print(Node cNode){			//打印结果
	//outfile<<"print"<<endl;
	stack<int> nodeStack;
	int id;
	id = cNode.getParentID();
	while (id != 0){
		nodeStack.push(id);
		id = IDMAP.find(id)->second.getParentID();
	}
	int steps = nodeStack.size() + 1;
	while (!nodeStack.empty()){
		id = nodeStack.top();
		nodeStack.pop();
		for (int i = 0; i < 3; i++){
			for (int j = 0; j < 3; j++){
				outfile<<IDMAP.find(id)->second.state[i][j]<<" ";
			}
			outfile<<endl;
		}
		outfile<<endl;
	}
	for (int i = 0; i < 3; i++){
		for (int j = 0; j < 3; j++){
			outfile<<cNode.state[i][j]<<" ";
		}
		outfile<<endl;
	}
	outfile<<"total steps:"<<steps<<endl;
}
void operate(Node& pNode, Node& node)	//对expand出的节点进行操作
{	
	// mj类型的节点
	//outfile<<CLOSED.count(node)<<endl;
	//CLOSED.count(node);
	//outfile<<OPEN.count(node)<<endl;
	//outfile<<"find:"<<(CLOSED.find(node) == CLOSED.end())<<endl;
	if (OPEN.count(node) == 0 && CLOSED.count(node) == 0){
		//outfile<<"mj"<<endl;
		node.setParent(pNode);
		OPEN.insert(node);
		IDMAP.insert(make_pair(node.getID(), node));
	}
	// mk类型的节点
	else if (OPEN.count(node) > 0 && CLOSED.count(node) == 0){
		//outfile<<"mk"<<endl;
		if (OPEN.find(node)->f() > node.f()){
			OPEN.find(node)->setParent(pNode);
			// OPEN.find(node)->count = pNode.count + 1;
		}
	}
	// ml类型的节点
	else if (OPEN.count(node) == 0 && CLOSED.count(node) > 0){
		//outfile<<"ml"<<endl;
		if (CLOSED.find(node)->f() > node.f()){
			node.setParent(pNode);
			if (CLOSED.erase(node) == 0)
				//outfile<<"erase error!"<<endl;
			OPEN.insert(node);
		}
	}

	else{ 
		if (OPEN.count(node) > 0 && CLOSED.count(node) > 0){
		//outfile<<"error!"<<endl;
		}
	}
}
void expand(Node& cNode){
	//各种移动操作
	//UP
	if (cNode.getX()== 0);		// Do nothing
	else {
		Node newNode = cNode;
		newNode.move(UP);
		operate(cNode, newNode);
		
	}
	//DOWN
	if (cNode.getX() == 2);		// Do nothing
	else{
		Node newNode = cNode;
		newNode.move(DOWN);
		operate(cNode, newNode);
	}
	if (cNode.getY() == 0);			// Do nothing
	else{
		Node newNode = cNode;
		newNode.move(LEFT);
		operate(cNode, newNode);
	}
	if (cNode.getY() == 2);		// Do nothing
	else{
		Node newNode = cNode;
		newNode.move(RIGHT);
		operate(cNode, newNode);
	}
}
int main()
{
	string fileName;
	cin>>fileName;
	ifstream infile;
	infile.open(fileName.c_str());
	outfile.open("result.txt");
	// cin
	int state[3][3];
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			infile>>state[i][j];
	infile.close();
	//利用逆序数判断
	int counter = 0;
	for (int i = 0; i < 3; i++){
		for (int j = 0; j < 3; j++){
			for (int s = 0; s < 3; s++){
				for (int t = 0; t < 3; t++){
					if ((state[s][t] < state[i][j]) && ((s > i) || ((s == i) && (t > j))) && (state[s][t] != 0) && (state[i][j] != 0))
						counter++;
				}
			}
		}
	}
	if (counter % 2 == 0){
		outfile<<"no solution"<<endl;
		outfile.close();
		return 0;
	}
	//初始化OPEN表
	Node s = Node(state);
	OPEN.insert(s);
	IDMAP.insert(make_pair(s.getID(), s));
	//开始循环 
	while(1){
		// no solution!
		if (OPEN.size() == 0){
			outfile<<"no solution"<<endl;
			break;
		}
		Node begin = *OPEN.begin();
		//outfile<<IDMAP.size()<<endl;
		//outfile<<"h()="<<begin.h()<<endl;
		if (OPEN.begin()->h() == 0){			//找到结果
			print(*OPEN.begin());
			break;
		}
		pair<set<Node>::iterator, bool> ret;
		ret = CLOSED.insert(begin);
		if (ret.second == false)
			outfile<<"Insert to CLOSED error!"<<endl;
		OPEN.erase(begin);
		// expand
		expand(begin);
	}
	outfile.close();
	return 0;
}