idfs.cpp

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

#include "stdafx.h"
#include "idfs.h"
#include "bdfs.h"


extern HASH_BDFS tree_bdfs;

CString IDFS::getIntroduction(){
	CString intro = "迭代加深深度优先搜索\r\n\r\n"
					"搜索时优先搜索子树，"
					"在迭代步长为1时，保证为最优解。"
					"可以在效率与解答之间找到平衡点。";
	return intro;
}


int IDFS::search(int begin, int end, int &stop, int val){
	if((getreverse(begin) & 1) != (getreverse(end) & 1) ){  //逆序数不一样，无解
		result = NOANSWER;
		return -1;
	}
	std::vector<int> Q;
	result = SUCCESS;
	open[0].father = -1;
	open[0].step = 0;
	open[0].status = begin;
	int index, tmp;
	for(index = 0, tmp = begin; tmp % 10; ++index, tmp /= 10);
	open[0].zero = index;	
	reset(begin, end) - 1; //初始转换信息
	totalnode = 0;
	int limit = 0;
	while(!stop){
		limit ++;
		tree_bdfs.reset();
		tree_bdfs.add(begin, 0, 0);
		Q.push_back(top = 0);	
		while(!stop && !Q.empty()){
			index = Q.back();
			Q.pop_back();		
			if(open[index].status == end){
				last_index = index;
				totalnode += top;
				expanded = totalnode + 1 - Q.size();
				inopen = Q.size();
				return 1;
			}
			if(open[index].step >= limit) continue;
			int zero = open[index].zero;
			for(int i = 0; i < dir_count[zero]; i++){				
				int tmp = getnextstatus(open[index].status, zero, dir[zero][i]);
				int newindex = tree_bdfs.add(tmp, top + 1, open[index].step + 1);
				if(newindex == 0){
					open[++top].father = index;
					open[top].status = tmp;
					open[top].step = open[index].step + 1;
					open[top].zero = dir[zero][i];
					Q.push_back(top);
				}else if(newindex > 0){
					open[newindex].father = index;
					open[newindex].step = open[index].step + 1;			
					Q.push_back(newindex);
				}
			}
		}
		totalnode += top + 1;
	}
	expanded = top + 1 - Q.size();
	inopen = Q.size();
	if(stop){
		result = STOP;
		return -2;
	}
	result = CANTFIND;
	return 0;
}