astar2.cpp

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

#include "stdafx.h"
#include "astar2.h"



struct cmp{
	bool operator()(const int & a, const int & b) const{
		if(open[a].val == open[b].val)
			return open[a].step > open[b].step;		
		return open[a].val > open[b].val;
	}
};
CString ASTAR2::getIntroduction(){
	CString intro = "A*搜索算法\r\n\r\n"
					"f(x) = g(x) + h(x)，\r\n"
					"其中g(x)为搜索深度，\r\n"
					"h(x)为所有不在目标位置的图片数目之和，\r\n"
					"在h(x)系数为1的情况下保证为最优解";

	return intro;
}

int ASTAR2::search(int begin, int end, int &stop, int val){
	if((getreverse(begin) & 1) != (getreverse(end) & 1) ) {  //逆序数不一样，无解
		result = NOANSWER;
		return -1;
	}
	std::priority_queue<int, std::vector<int>, cmp> Q;
	result = SUCCESS;	
	open[0].father = -1;
	open[0].step = 0;
	open[0].status = begin;	
	open[0].val = reset(begin, end, 2) * val;
	int index, tmp;
	for(index = 0, tmp = begin; tmp % 10; ++index, tmp /= 10);
	open[0].zero = index;
	Q.push(top = 0);
	tree.reset();
	tree.add(begin);
	while(!stop && !Q.empty()){
		index = Q.top();
		Q.pop();
		if(open[index].status == end){
			last_index = index;
			totalnode = top;
			expanded = top + 1 - Q.size();
			inopen = Q.size();
			return 1;
		}
		int zero = open[index].zero;
		for(int i = 0; i < dir_count[zero]; i++){				
			int tmp = getnextstatus(open[index].status, zero, dir[zero][i]);
			if(tree.add(tmp) ){
				open[++top].father = index;
				open[top].status = tmp;
				open[top].step = open[index].step + 1;
				open[top].zero = dir[zero][i];
				if(!val)
					open[top].val = open[top].step;
				else
					open[top].val = (getval(tmp, (open[index].val - open[index].step) / val, zero, dir[zero][i]) * val)
						+ open[top].step;				
				Q.push(top);
			}
		}
	}
	//获取结点信息
	expanded = top + 1 - Q.size();
	inopen = Q.size();
	if(stop){
		result = STOP;
		return -2;
	}
	result = CANTFIND;
	return 0;
}