searcher.cpp

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

#include "stdafx.h"
#include "searcher.h"
#include <cmath>


HASH tree;
struct NODE open[MAXNODE];
int top;

double searcher::getB(){
	static const double limit = 1e-6;
	double low = 1.0, up = 10.0, mid;
	int step = open[last_index].step + 1;
	while(true){
		mid = (low + up) / 2;
		double t = (pow(mid, step) - mid) / (mid - 1) - totalnode;
		if(fabs(t) < limit){
			return (B = mid);	
		}else if(t > 0)
			up = mid;
		else
			low = mid;		
	}
}

void searcher::getPath(std::vector<int> &vec){
	vec.clear();
	std::vector<int> path;
	while(last_index != -1){
		path.push_back(::open[last_index].status);
		last_index = ::open[last_index].father;
	}
	while(!path.empty() ){
		vec.push_back(path.back() );
		path.pop_back();
	}
}

CString searcher::getResult(){//-1无解，-2用户终止，0找不到解，1有解
	CString res;
	char str[50];
	if(result == NOANSWER)
		res = "无解";
	else{
		if(result == CANTFIND)
			res = "有解但该算法找不到答案\r\n";
		else if(result == STOP)
			res = "解步长：用户中止\r\n";
		else{
			sprintf(str, "解步长：%d\r\n", open[last_index].step);
			res += str;			
		}
		sprintf(str, "已扩展结点：%d\r\n待扩展结点：%d\r\n", expanded, inopen);
		res += str;
		if(result == SUCCESS){
			getP();
			getB();
			sprintf(str, "外显率P：%.6lf\r\n", P);
			res += str;
			if(fabs(B - 1.0) < 1e-2)
				res += "由于步数过长，无法算出有效分枝因数";
			else{
				sprintf(str, "有效分枝因数：%.3lf\r\n", B);
				res += str;
			}
		}
	}
	return res;
}

int searcher::reset(const int begin, const int end, int mode){   //重置初始值，返回初始位置启发值
	m_end = end;
	int i, j;		
	
	for(i = 0, j = 1; i < 9; ten[i] = j, j *= 10, ++i);
	for(i = 0; i < 9; ++i){
		des[end / ten[i] % 10] = i;
		for(j = 0; j < 9; ++j){
			dis[i][j] = abs(i / 3 - j / 3) + abs(i % 3 - j % 3);
			swap[i][j] = ten[i] - ten[j];
		}			
	}

	if(mode == 1){   //Astar1
		for(i = j = 0; i < 9; ++i) 
			if(begin / ten[i] % 10) 
				j += dis[ des[begin / ten[i] % 10] ][i];		
	}else{ //Astar2
		for(i = j = 0; i < 9; ++i) 
			if( (begin / ten[i] % 10) && (i != des[begin / ten[i] % 10]) ) 
				++j;
	}
	return j;
}

int searcher::getreverse(int status){  //逆序数
	int tmp[9], sum = 0;
	for(int i = 0; i < 9; ++i){
		tmp[i] = status % 10;
		status /= 10;
		if(tmp[i]){
			for(int j = 0; j < i; ++j)
				if(tmp[i]) sum += (tmp[j] > tmp[i]);	
		}
	}
	return sum;
}


bool HASH::add(const int m_data){
	int mod = (m_data << 1) % MAXSIZE;  //获取哈希值
	for(struct Node * p = hash[mod]; p; p = p->next){
		if(m_data == p->data)    //状态已存在
			return false;
	}	
	node[ID].data = m_data;     //添加新结点
	node[ID].next = hash[mod];
	hash[mod] = &node[ID];
	++ID;
	return true;
}