main.cpp

一个基于启发式算法的搬运工求解程序

/*
	1 改进了DeadLock中的错误
	2 添加了动态权值
*/

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iostream>
#include <string>
#include <windows.h>
#include "CMinCostFlow.h"
using namespace std;

//#define display

const int MAX_HASH		= 200003;
const int MAX_STEP		= 150;
const int MAX_BOXNUM	= 10;
const int MAX_ROW		= 20;
const int MAX_COL		= 20;
const int MUL			= 1;
const double e			= 3;
const int N				= 100;

class CNode
{
public:
	CNode(): peo_pos(-1), next(NULL), pathn(0) {}
public:
	int g;
	int h;
	short peo_pos;						// 初始为-1表示这是一个空节点
	short path[MAX_STEP * 2];			// 存储方式为“箱子位置，方向"
	short pathn;
	short boxpos[MAX_BOXNUM];			// 最大箱子数20, 保证里面是按照递增顺序
	unsigned __int64 hashvalue;
	CNode *next;
};

class CError
{
public:
	CError(string message): msg(message) {};
	string ErrorMessage();
private:
	string msg;
};

int row;
int col;
int boxnum;
int *destpos;									// 箱子目的地的位置
int dp[4];
int node_all;									// 已经扩展的节点的数目
int node_cal;									// 找到目标时已经扩展的节点
int **min_dis;
unsigned __int64 **zobrist_table;
CNode hashtable[MAX_HASH];
CNode from;
char *chessboard;
ifstream fin("data.in");
//ofstream fout("data.out");

int	CalH(double *s, int n, int *people, int *box, int box_n);
int Rotate(int axisp, int p, int angle);		// 将p绕axisp逆时针旋转angle度，返回新位置
void UpdateH(CNode &m);
void BFS(CNode &m, int f, int *pos, int pos_n, bool *valid, int *dis, bool consider_box);
void Display(CNode m);
void Read();
void Test();
void AddToHash(CNode &m, CNode *p);
bool CanReach(CNode &m , int f, int t);
bool NoBalk(CNode &m, int pos, int dir, bool consider_box);
bool Arrive(CNode &m);
bool Same(CNode &m, CNode &n);
bool DeadLock(CNode &m, int newpos);
bool operator < (const CNode &m, const CNode &n);
bool ChessBoard(int p, char ch);
bool Match0(int newpos);
bool Match1(int newpos);
bool Match2(int newpos);
bool Match3(int newpos);
CNode *FindInHash(CNode &m);
CNode Run();
string AsString(CNode &m);
unsigned __int64 Hash(CNode &m);
unsigned __int64 Rand64();

int main()
{
	try
	{
		CNode r;
		int time_f;
		int time_t;

		Read();
		time_f = GetTickCount();
		r = Run();
		time_t = GetTickCount();
		if(r.peo_pos == -1)
			cout << "no path" << endl;
		else
		{
#ifdef display
			Display(r);
#endif
			cout << "总扩展节点数: " << node_all << endl;
			cout << "已计算节点数: " << node_cal << endl;
			cout << "time = " << (time_t - time_f) / 1000.0 << endl;
		}
	}
	catch(CError &error)
	{
		cout << error.ErrorMessage() << endl;
	}
	//Test();
	
	return 0;
}

void Test()
{
	//
}

string CError::ErrorMessage()
{
	return msg;
}

bool ChessBoard(int p, char ch)
{
	if(ch == 'g')
		return chessboard[p] == 'g' || chessboard[p] == '&';
	if(ch == 'b')
		return chessboard[p] == 'b' || chessboard[p] == '&';
	return chessboard[p] == ch;
}

bool Match0(int newpos)
{
	// 严格坑形，目标节点数目比当前坑中箱子数目要少
	int i;
	static int dp_left[4] = {-1, col, 1, -col};
	static int dp_up[4] = {-col, -1, col, 1};
	int u;		// b 比 g 多的数目
	int p;

	for(i = 0; i < 4; i++)
	{
		// 逆时针转的变化量
		u = 0;
		p = newpos;
		if(ChessBoard(p + dp_up[i], '#'))
		{
			if(ChessBoard(p, 'b'))
				u++;
			if(ChessBoard(p, 'g'))
				u--;
		}
		else
			continue;
		// 向左走				
		while(!ChessBoard(p + dp_left[i], '#') 
			&& ChessBoard(p + dp_left[i] + dp_up[i], '#'))
		{
			if(ChessBoard(p + dp_left[i], 'b'))
				u++;
			if(ChessBoard(p + dp_left[i], 'g'))
				u--;
			p += dp_left[i];
		}
		if(!ChessBoard(p + dp_left[i], '#')
			&& !ChessBoard(p + dp_left[i] + dp_up[i], '#'))
			continue;		
		// 向右走
		p = newpos;
		while(!ChessBoard(p - dp_left[i], '#')
			&& ChessBoard(p - dp_left[i] + dp_up[i], '#'))
		{
			if(ChessBoard(p - dp_left[i], 'b'))
				u++;
			if(ChessBoard(p - dp_left[i], 'g'))
				u--;
			p -= dp_left[i];
		}
		if(!ChessBoard(p - dp_left[i], '#') 
			&& !ChessBoard(p - dp_left[i] + dp_up[i], '#'))
			continue;
		// 如果目标位置数目比箱子数目少那么死锁
		if(u > 0)
			return true;
	}	

	return false;
}

bool Match1(int newpos)
{
	/*
		判断四个在一起的
		bb
		bb

		bb
		b#

		bb
		##

		#b
		^# 
		前三种都可以统一到一起，但第四种无论^为什么符号必死锁所以预判断
	*/

	// 只要相邻90度的两个地方是墙并且当前不是目标位置就死锁
	if(!ChessBoard(newpos, 'g') && ChessBoard(newpos, 'b'))
		if ((ChessBoard(newpos - col, '#') || ChessBoard(newpos + col, '#'))
		&& (ChessBoard(newpos - 1, '#') || ChessBoard(newpos + 1, '#')))
		return true;

	
	static int b[4];	
	int i;
	int j;
	int u;
	int t;

	for(t = 0; t < 4; t++)
	{
		for(i = 0; i < 4; i++)
		{
			if(t == 0)
			{
				b[0] = newpos;
				b[1] = Rotate(newpos, newpos + 1, i * 90);
				b[2] = Rotate(newpos, newpos + col, i * 90);
				b[3] = Rotate(newpos, newpos + col + 1, i * 90);
			}
			if(t == 1)
			{
				b[0] = Rotate(newpos, newpos - 1, i * 90);
				b[1] = newpos;
				b[2] = Rotate(newpos, newpos - 1 + col, i * 90);
				b[3] = Rotate(newpos, newpos + col, i * 90);
			}
			if(t == 2)
			{
				b[0] = Rotate(newpos, newpos - col, i * 90);
				b[1] = Rotate(newpos, newpos - col + 1, i * 90);
				b[2] = newpos;
				b[3] = Rotate(newpos, newpos + 1, i * 90);
			}
			if(t == 3)
			{
				b[0] = Rotate(newpos, newpos - col - 1, i * 90);
				b[1] = Rotate(newpos, newpos - col, i * 90);
				b[2] = Rotate(newpos, newpos - 1, i * 90);
				b[3] = newpos;
			}
			u = 0;
			for(j = 0; j < 4; j++)
				if(ChessBoard(b[j], 'b') || ChessBoard(b[j], '#'))
					u++;
			if(u != 4)
				continue;
			u = 0;
			for(j = 0; j < 4; j++)
			{
				if(ChessBoard(b[j], 'g'))
					u--;
				if(ChessBoard(b[j], 'b'))
					u++;
			}
			if(u > 0)
				return true;			
		}
	}

	return false;
}

bool Match2(int newpos)
{
	//  ##
	// #*b
	// #b
	// 如果两个箱子和*位置处有b > g，那么死锁
	// 利用旋转复数, 四个墙和两个箱子和一个*依次编号
	int i;
	int u;
	int t;
	static int b[7];	

	for(t = 0; t < 2; t++)
	{
		for(i = 0; i < 4; i++)
		{
			if(t == 0)
			{
				b[0] = Rotate(newpos, newpos - col - 1, 90 * i);
				b[1] = Rotate(newpos, newpos - col, 90 * i);
				b[2] = Rotate(newpos, newpos - 2, 90 * i);
				b[3] = Rotate(newpos, newpos - 1, 90 * i);
				b[4] = newpos;
				b[5] = Rotate(newpos, newpos + col - 2, 90 * i);
				b[6] = Rotate(newpos, newpos + col - 1, 90 * i);
			}
			if(t == 1)
			{
				b[0] = Rotate(newpos, newpos - 2 * col, 90 * i);
				b[1] = Rotate(newpos, newpos - 2 * col + 1, 90 * i);
				b[2] = Rotate(newpos, newpos - col - 1, 90 * i);
				b[3] = Rotate(newpos, newpos - col, 90 * i);
				b[4] = Rotate(newpos, newpos - col + 1, 90 * i);
				b[5] = Rotate(newpos, newpos - 1, 90 * i);
				b[6] = newpos;
			}	

			u = 0;
			if(!ChessBoard(b[4], 'b') || !ChessBoard(b[6], 'b'))
				continue;
			if(ChessBoard(b[0], '#')
				&& ChessBoard(b[1], '#')
				&& ChessBoard(b[2], '#')
				&& ChessBoard(b[5], '#'))
			{
				if(ChessBoard(b[3], 'g'))
					u--;
				if(ChessBoard(b[3], 'b'))
					u++;
				if(ChessBoard(b[4], 'g'))
					u--;
				if(ChessBoard(b[4], 'b'))
					u++;
				if(ChessBoard(b[6], 'g'))
					u--;
				if(ChessBoard(b[6], 'b'))
					u++;

				if(u > 0)
					return true;
			}
		}
	}

	return false;
}

bool Match3(int newpos)
{
	// #b
	//  b#
	static int b[4];
	int i;
	int j;
	int t;
	int u;

	for(t = 0; t < 2; t++)
	{
		for(i = 0; i < 4; i++)
		{
			if(t == 0)
			{
				b[0] = Rotate(newpos, newpos - 1, i * 90);
				b[1] = newpos;
				b[2] = Rotate(newpos, newpos + col, i * 90);
				b[3] = Rotate(newpos, newpos + col + 1, i * 90);
			}
			if(t == 1)
			{
				b[0] = Rotate(newpos, newpos - col - 1, i * 90);
				b[1] = Rotate(newpos, newpos - col, i * 90);
				b[2] = newpos;
				b[3] = Rotate(newpos, newpos + 1, i * 90);
			}	
			if(!ChessBoard(b[0], '#')
				|| !ChessBoard(b[1], 'b')
				|| !ChessBoard(b[2], 'b')
				|| !ChessBoard(b[3], '#'))
				continue;

			u = 0;
			for(j = 1; j <= 2; j++)
			{
				if(ChessBoard(b[j], 'g'))
					u--;
				if(ChessBoard(b[j], 'b'))
					u++;
			}
			if(u > 0)
				return true;
		}
	}

	//  b#
	// #b
	// 考虑对陈情况
	for(t = 0; t < 2; t++)
	{
		for(i = 0; i < 4; i++)
		{
			if(t == 0)
			{
				b[0] = newpos;
				b[1] = Rotate(newpos, newpos + 1, i * 90);
				b[2] = Rotate(newpos, newpos + col - 1, i * 90);
				b[3] = Rotate(newpos, newpos + col, i * 90);
			}
			if(t == 1)
			{
				b[0] = Rotate(newpos, newpos - col, i * 90);
				b[1] = Rotate(newpos, newpos - col + 1, i * 90);
				b[2] = Rotate(newpos, newpos - 1, i * 90);
				b[3] = newpos;
			}	
			if(!ChessBoard(b[0], 'b')
				|| !ChessBoard(b[1], '#')
				|| !ChessBoard(b[2], '#')
				|| !ChessBoard(b[3], 'b'))
				continue;

			u = 0;
			if(ChessBoard(b[0], 'g'))
				u--;
			if(ChessBoard(b[0], 'b'))
				u++;
			if(ChessBoard(b[3], 'g'))
				u--;
			if(ChessBoard(b[3], 'b'))
				u++;
			if(u > 0)
				return true;
		}
	}

	return false;
}

string AsString(CNode &m)
{
	string r;
	int i;

	for(i = 0; i < row * col; i++)
	{
		r += chessboard[i];
		if((i + 1) % col == 0)
			r += '\n';
	}
	for(i = 0; i < boxnum; i++)
		if(r[m.boxpos[i] + m.boxpos[i] / col] == 'g')
			r[m.boxpos[i] + m.boxpos[i] / col] = '&';
		else
			r[m.boxpos[i] + m.boxpos[i] / col] = 'b';

	return r;
}

bool operator < (const CNode &m, const CNode &n)
{
	return m.g + m.h > n.g + n.h;
}

int Rotate(int axisp, int p, int angle)
{
	static int zx[4] = {1, 0, -1, 0};
	static int zy[4] = {0, 1, 0, -1};