IDAstar搜索

http://poj.org/problem?id=1077

Source Code

Problem: 1077  User: p_hoenix 
Memory: 220K  Time: 0MS 
Language: C++  Result: Accepted 

Source Code 
#include <iostream>
#include <utility>
#include <vector>
#include <fstream>
#include <math.h>
using namespace std;

const int MAX = 1 << 20;
const int ROW = 3, COL = 3;



//棋盘
struct Board
{
	Board& operator=(const Board &b)
	{
		for(int i = 0; i < ROW; i++)
			for(int j = 0; j < COL; j++)
				tile[i][j] = b.tile[i][j];
		r = b.r;
		c = b.c;
		return *this;
	}
	int tile[ROW][COL];//4*4的方块
	int r,c;//空格的位置
};
typedef Board Status;

struct Step
{
	int r,c;
	int dir;
};

class PicturePizzle
{
public:
	friend void input(PicturePizzle &pp);
	
	PicturePizzle()
	{
		pStepDir = (int*)malloc(sizeof(int) * MAX);
		stepHeap = (Board*)malloc(sizeof(Board) * MAX);
	}
	
	~PicturePizzle()
	{
		free(pStepDir);
		free(stepHeap);
	}
	//移动步骤.
	typedef struct{
		int r,c;//空格位置
		int dir;//移动方向
	}Step;
	
	//判断以该状态开始是否可以完成拼图
	bool JudgeValidStatus();
	//heuristic function,启发式函数,计算(估算)最大移动步数
	int Heuristic();
	//IDA*搜索寻找移动方案
	//当前状态,深度,h(),前一步的移动方向.
	bool IDAstar(Status &s, int depth, int h, int prevDir);
	
	//打印移动路径
	void ShowStep(int depth);
	
	void Run();
	
	//private:
	Board board;
	int h;
	int maxDepth;
	vector<Board> step;
	int *pStepDir;
	Board *stepHeap;
	//郁闷的地方,C++ primer里面说可以给const static在里面初始化,在类外面定义的,但是VC6.0不可以
	//目标棋盘
	const static Board destBoard;// = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 4, 4};
	const static int nDestPos[ROW * COL + 1][2];//最终棋盘的各个方块的位置
	const static int dir[4][2];
};

//1到16的方块编号
const Board PicturePizzle::destBoard = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 2, 2};//10, 11, 12, 13, 14, 15, 16, 3, 3};
const int PicturePizzle::nDestPos[ROW * COL + 1][2] = {{-1, -1},
{0, 0}, {0, 1}, {0, 2},
{1, 0}, {1, 1},{1, 2},
{2, 0}, {2, 1}, {2, 2}};
//{3, 0}, {3, 1}, {3, 2}, {3, 3}};

const int PicturePizzle::dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//左上右下

bool PicturePizzle::JudgeValidStatus()
{
	int i, j, array[ROW * COL], k, sum;
	sum = k = 0;
	//转化成一维数组
	for(i = 0; i < ROW; i++)
		for(j = 0; j < COL; j++)
		{
			array[k++] = board.tile[i][j];
		}
	//因为在最终状态下,棋盘的一维数组是有序递增的.
	//除了X结点外,要到达目标位置需要移动的最大步数,因为在转换成了一维后原本可以上下移动的都被转化成了水平移动.
	//但是幸运的是,他们是同奇同偶的.具体的证明我也不知道,画图有这么个规律
	for(i = 0; i <= ROW * COL - 2; i++)
		for(j = i + 1; j <= ROW * COL - 1; j++)
			if(array[i] > array[j])
				sum++;
	//这个是X方块到目标位置的最短步数,不管怎么移动,只要最后是在目标位置,必定是同奇同偶的.(简单的考虑就是撤销)
	//而每一次的其他方块的移动都是与X方块的交换来实现的,所以他们的和必定是偶数
	sum += abs(board.r - nDestPos[ROW * COL][0]) + abs(board.c - nDestPos[ROW * COL][1]);
	return sum % 2 == 0;
}

int PicturePizzle::Heuristic()
{
	int r, c, tile, sum = 0;
	for(r = 0; r < ROW; r++)
		for(c = 0; c < COL; c++)
		{
			tile = board.tile[r][c];
			//计算每个方块(非空格)移动到目标位置的曼哈顿距离,不需要计算空格
			if(tile != ROW * COL)
			{
				sum += abs(r - nDestPos[tile][0]) + abs(c - nDestPos[tile][1]);
			}
		}
	h = sum;
	return sum;
}



int global = 0;
bool PicturePizzle::IDAstar(Status &s, int depth, int h, int prevDir)
{
	//cout<<global++<<endl;
	
	if(memcmp(&s, &destBoard, sizeof(destBoard)) == 0)//到达目标状态
	{
		this->ShowStep(depth);
		return true;
	}
	if(depth >= maxDepth)//超过当前深度
		return false;
	Status ns;
	int nr,nc,nh,moveTile;
	for(int d = 0; d < 4; d++)
	{
		if(abs(d - prevDir) == 2)//会撤销上次的移动
			continue;
		ns = s;
		nr = s.r + dir[d][0];
		nc = s.c + dir[d][1];
		if(nr < 0 || nr > ROW - 1 || nc < 0 || nc > COL - 1)//越界
			continue;
		//移动方块
		moveTile = s.tile[nr][nc];
		ns.tile[s.r][s.c] = moveTile;
		ns.tile[nr][nc] = ROW * COL;
		ns.r = nr;
		ns.c = nc;
		
		//向左移动.并且与X交换的方块离它的目标位置近了一步.
		//反过来,因为X是向左的,那么moveTile就是向右的,那么这个时候只有moveTile在它的目标位置的左边的时候才成立
		//也就是说它原来的位置nc是在目标的左边
		if(d == 0 && nc < nDestPos[moveTile][1])
			nh = h - 1;//nh比当前的h少1
		else if(d == 1 && nr < nDestPos[moveTile][0])//上
			nh = h - 1;
		else if(d == 2 && nc > nDestPos[moveTile][1])//右
			nh = h - 1;
		else if(d == 3 && nr > nDestPos[moveTile][0])
			nh = h - 1;
		else
			nh = h + 1;
		
		//大于f
		if(depth + nh > maxDepth)
			continue;
		
		//step.insert(step.begin() + depth, ns);
		//step.erase(step.begin() + depth + 1);
		
		pStepDir[depth] = d;
		stepHeap[depth] = ns;
		
		if(IDAstar(ns, depth + 1, nh, d))
			return true;
	}
	return false;
}


void PicturePizzle::ShowStep(int depth)
{
	int i = 0;
	//cout<<depth<<endl;
	
	for(i = 0; i < depth; i++)
		switch(pStepDir[i])
	{
		case 0:
			cout<<'l';
			break;
		case 1:
			cout<<'u';
			break;
		case 2:
			cout<<'r';
			break;
		case 3:
			cout<<'d';
			break;
	}
	cout<<endl;
	/*
	for(i = 0; i < depth; i++)
	{
	for(int r = 0; r < ROW; r++)
	{
	for(int c = 0; c < COL; c++)
	cout<<stepHeap[i].tile[r][c]<<"\t";
	cout<<endl;
	}
	cout<<endl<<endl;
	}
	*/
	
	/*
	cout<<step.size()<<endl<<endl;
	for(vector<Board>::iterator iter = step.begin(); iter != step.end(); iter++)
	{
	cout<<i++<<endl;
	for(int r = 0; r < 4; r++)
	{
	for(int c = 0; c < 4; c++)
				cout<<iter->tile[r][c]<<"\t";
				cout<<endl;
				}
				cout<<endl<<endl;
}*/
}

void PicturePizzle::Run()
{
	if(JudgeValidStatus())
	{
		maxDepth = Heuristic();
		while(maxDepth++)
			if(IDAstar(board, 0, h, 20))
				break;
	}
	else
	{
		cout<<"unsolvable"<<endl;
	}
	
}

void input(PicturePizzle &pp)
{
	//cout<<"输入一个文件(.txt),表示拼图的初始"
	//fstream file("in.txt");
	int num;
	for(int r = 0; r < ROW; r++)
		for(int c = 0; c < COL; c++)
		{
			//file>>num;
			cin>>num;
			if(/*file.fail()*/cin.fail())
			{
				//file.clear();
				//file.ignore(1,'\t');
				cin.clear();
				cin.ignore(1, ' ');
				pp.board.tile[r][c] = ROW * COL;
				pp.board.r = r;
				pp.board.c = c;
			}
			else
				pp.board.tile[r][c] = num;
		}
		//file.close();
}



int main()
{
	//freopen("out.txt", "w", stdout);
	
	PicturePizzle pp;
	input(pp);
	pp.Run();
	
	return 0;
}