searcher.h

来自「滑块问题求解系统：利用深度优先搜索和广度优先搜索解决有趣的滑块问题求解系统。」· C头文件 代码 · 共 88 行

#include <vector>
#include <queue>
#ifndef _SEARCHER_H_
#define _SEARCHER_H_

class HASH;
struct NODE{
	int status;    //状态
	int step;      //步长
	int val;       //估价值
	int father;    //父结点
	int zero;      //空格所在位置
};


const int MAXNODE = 182000;
extern HASH tree;
extern struct NODE open[MAXNODE];
extern int top;


class searcher{
protected:
	int ten[9];   //ten[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000}
	int swap[9][9];   //状态转换用数组
	int dis[9][9];    //两数码之间的距离
	int des[9];	      //目标结点各个数码所在位置
	int m_end;        //结束状态
	int last_index;   //open表最后一个元素下标
	int expanded;     //已扩展的节点
	int inopen;       //仍在open表中的结点
	enum{NOANSWER, STOP, CANTFIND, SUCCESS}result;  //搜索结果
	int totalnode;   //搜索过的总节点数 - 1。
	double P;  //外显率  P = L / T;  L为路径长度， T为中间生成的节点总数。
	double B;  //有效分枝因数 T = B * (B ^ L - 1) / (B - 1); 可二分求解。

public:
	
	virtual int search(int begin, int end, int &stop, int val = 0) = 0;  //-1无解，-2用户终止，0找不到解，1有解
	virtual void getPath(std::vector<int> &vec);
	int reset(const int begin, const int end, int mode = 1);   //重置初始值，返回初始位置启发值		
	int getnextstatus(const int status, const int zero, const int zero_to){   //获取下一个状态
		return status + swap[zero][zero_to] * (status / ten[zero_to] % 10);		
	}
	virtual CString getIntroduction() = 0;  //介绍
	virtual CString getResult();     //获取搜索结果
	int getreverse(int status);  //逆序数	
	void getP(){  //获得外显率
		P = ( (double) open[last_index].step) / totalnode;
	}
	double getB();  //获得有效分枝因数
	int getStep(){return open[last_index].step;}   //解步长
	int getTotalnode(){return totalnode + 1;}   //总共生成节点数
};

class HASH{
protected:
	struct Node{
		int data;	
		struct Node* next;
	};
	const static int MAXSIZE= 70001, ALL = 182000;	
	int ID;
	struct Node *hash[MAXSIZE], node[ALL];
public:
	bool add(const int m_data);
	void reset(){   //重置哈希表
		memset(hash, 0, sizeof(hash) );
		ID = 0;
	}
};

const int dir_count[] = {2, 3, 2, 3, 4, 3, 2, 3, 2};
const int dir[][4] = {
	{1, 3, 0, 0},
	{0, 2, 4, 0},
	{1, 5, 0, 0},
	{0, 4, 6, 0},
	{1, 3, 5, 7},
	{2, 4, 8, 0},
	{3, 7, 0, 0},
	{4, 6, 8, 0},
	{5, 7, 0, 0}
};



#endif