tbfs.cpp

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

#include "stdafx.h"
#include "tbfs.h"


int HASH_TBFS::add(const int m_data, const int index, const int mode){  //-1不存在，1已存在,反向插入时如果存在返回index
	int mod = (m_data << 1) % MAXSIZE;
	for(struct Node * p = hash[mod]; p; p = p->next){
		if(m_data == p->data){
			if(mode)
				return p->index;
			else
				return -1;
		}
	}
	if(mode) return -1;
	node[ID].data = m_data;
	node[ID].index = index;
	node[ID].next = hash[mod];
	hash[mod] = &node[ID];
	++ID;
	return 1;
}


HASH_TBFS tree_front, tree_back;
struct NODE open_back[MAXNODE];

CString TBFS::getIntroduction(){
	CString intro = "双向广度优先搜索\r\n\r\n"
					"该分别从初始结点与结束结点同时扩展，每次从状态少的一边进行扩展"
					"，一次扩展一层，能大大减少搜索结点，而且能保证找到最优解。";
	return intro;
}


int top_back;
void TBFS::combinepath(int index, int index_back){
	index_back = open_back[index_back].father;
	do{
		open[++top].status = open_back[index_back].status;
		open[top].step = open[index].step + 1;
		open[top].father = index;
		index = top;		
		index_back = open_back[index_back].father;
	}while(index_back != -1);
	last_index = index;
	totalnode = top + top_back + 1;
}

int TBFS::search(int begin, int end, int &stop, int val){
	if((getreverse(begin) & 1) != (getreverse(end) & 1) ){  //逆序数不一样，无解
		result = NOANSWER;
		return -1;
	}

	std::queue<int> Q_front, Q_back;
	result = SUCCESS;
	open[0].father = -1;
	open[0].step = 0;
	open[0].status = begin;
	open_back[0].father = -1;
	open_back[0].step = 0;
	open_back[0].status = end;

	int index, tmp, tmp_step;
	for(index = 0, tmp = begin; tmp % 10; ++index, tmp /= 10);
	open[0].zero = index;
	for(index = 0, tmp = end; tmp % 10; ++index, tmp /= 10);	
	open_back[0].zero = index;

	Q_front.push(top = 0);
	Q_back.push(top_back = 0);

	tree_front.reset();
	tree_front.add(begin, 0);
	tree_back.reset();
	tree_back.add(end, 0);
	reset(begin, end); //初始转换信息

	while(!stop && (!Q_front.empty() || !Q_back.empty() ) ){
		if(Q_back.empty() || !Q_front.empty() && Q_front.size() < Q_back.size()){			
			tmp_step = open[Q_front.front()].step;			
			do{
				index = Q_front.front();
				Q_front.pop();
				if( (tmp = tree_back.add(open[index].status, index, 1) ) != -1){
					combinepath(index, tmp);
					inopen = Q_front.size() + Q_back.size();
					expanded = top + top_back + 2 - inopen;
					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_front.add(tmp, top + 1) != -1){
						open[++top].father = index;
						open[top].status = tmp;
						open[top].step = open[index].step + 1;
						open[top].zero = dir[zero][i];
						Q_front.push(top);
					}
				}
				
			}while(!stop && !Q_front.empty() && open[Q_front.front()].step == tmp_step);
		}else{			
			tmp_step = open_back[Q_back.front()].step;			
			do{
				index = Q_back.front();
				Q_back.pop();
				if( (tmp = tree_front.add(open_back[index].status, index, 1) ) != -1){
					combinepath(tmp, index);
					inopen = Q_front.size() + Q_back.size();
					expanded = top + top_back + 2 - inopen;
					return 1;
				}
				int zero = open_back[index].zero;
				for(int i = 0; i < dir_count[zero]; i++){				
					int tmp = getnextstatus(open_back[index].status, zero, dir[zero][i]);
					if(tree_back.add(tmp, top_back + 1) != -1){
						open_back[++top_back].father = index;
						open_back[top_back].status = tmp;
						open_back[top_back].step = open_back[index].step + 1;
						open_back[top_back].zero = dir[zero][i];
						Q_back.push(top_back);
					}
				}
				
			}while(!stop && !Q_back.empty() && open[Q_back.front()].step == tmp_step);
		}
	}

	inopen = Q_front.size() + Q_back.size();
	expanded = top + top_back + 2 - inopen;

	if(stop){
		result = STOP;
		return -2;
	}
	result = CANTFIND;
	return 0;
}