aidlg.cpp

滑块问题求解系统：利用深度优先搜索和广度优先搜索解决有趣的滑块问题求解系统。

			move(GetFocus()->GetDlgCtrlID() - IDC_INIT_0);
			if(getStatus(pos_begin_return) == getStatus(pos_end_return) ){
				MessageBox("恭喜成功！");
				GetMenu()->EnableMenuItem(ID_CREATE, MF_BYCOMMAND | MF_ENABLED);
			}else{
				GetMenu()->EnableMenuItem(ID_CREATE, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED);
			}
		}
	}
}

void CAIDlg::OnBnClickedCheckHand()
{
	// TODO: 在此添加控件通知处理程序代码
	if(display.IsWindowEnabled() && 
		IDOK != MessageBox("将要丢失搜索信息，是否确认", "确认", MB_OKCANCEL) ){
			( (CButton *)GetDlgItem(IDC_CHECK_HAND) )->SetCheck(0);
			return;
	}
	if( ( (CButton *)GetDlgItem(IDC_CHECK_HAND) )->GetCheck() ){
		if(!statusReady() ){
			MessageBox("未设置初未状态！", "错误");
			( (CButton *)GetDlgItem(IDC_CHECK_HAND) )->SetCheck(0);
		}else{			
			prevstep.EnableWindow(FALSE);
			nextstep.EnableWindow(FALSE);
			recover.EnableWindow(FALSE);
			display.EnableWindow(FALSE);

			//状态框按钮
			( (CButton *) GetDlgItem(IDC_BUTTON_DEFAULT) )->EnableWindow(FALSE);
			( (CButton *) GetDlgItem(IDC_BUTTON_RANDOM) )->EnableWindow(FALSE);
			( (CButton *) GetDlgItem(IDC_BUTTON_HAND) )->EnableWindow(FALSE);
			( (CButton *) GetDlgItem(IDC_CHECK_BEGIN) )->EnableWindow(FALSE);
			( (CButton *) GetDlgItem(IDC_CHECK_END) )->EnableWindow(FALSE);
			( (CButton *) GetDlgItem(IDC_CHECK_NOANSWER) )->EnableWindow(FALSE);	
			
			m_byhand = gamestart = true;
			( (CButton *) GetDlgItem(IDC_BUTTON_BEGIN) )->EnableWindow(FALSE);					
			nowstatus = getStatus(pos_begin_return);
			laststatus = getStatus(pos_end_return);
			top = 0;
			path.clear();	
			path.push_back(nowstatus);
		}
	}else{
		if(path.size() > 1 && IDOK != MessageBox("将要丢失已移动过的信息，是否确认", "确认", MB_OKCANCEL) ){
			( (CButton *)GetDlgItem(IDC_CHECK_HAND) )->SetCheck(1);
			return;
		}
		m_byhand = gamestart = false;
		path.clear();
		top = -1;
		SetNowstep(0);
		//恢复状态框按钮
		( (CButton *) GetDlgItem(IDC_BUTTON_BEGIN) )->EnableWindow(TRUE);
		( (CButton *) GetDlgItem(IDC_BUTTON_DEFAULT) )->EnableWindow(TRUE);
		( (CButton *) GetDlgItem(IDC_BUTTON_RANDOM) )->EnableWindow(TRUE);
		( (CButton *) GetDlgItem(IDC_BUTTON_HAND) )->EnableWindow(TRUE);
		( (CButton *) GetDlgItem(IDC_CHECK_BEGIN) )->EnableWindow(TRUE);
		( (CButton *) GetDlgItem(IDC_CHECK_END) )->EnableWindow(TRUE);
		( (CButton *) GetDlgItem(IDC_CHECK_NOANSWER) )->EnableWindow(TRUE);	
	}
}

void CAIDlg::OnBnClickedButtonRandom()
{
	// TODO: 在此添加控件通知处理程序代码
	if(!path.empty() && 
		IDOK != MessageBox("将要丢失原来信息，是否确认", "确认", MB_OKCANCEL) ){		
			return;
	}
	path.clear();
	const int CHANGETIME = 10000;
	prevstep.EnableWindow(FALSE);
	nextstep.EnableWindow(FALSE);
	display.EnableWindow(FALSE);
	recover.EnableWindow(FALSE);
	srand((unsigned int) time(NULL) );
	int begin, end;
	do{
		if(m_random_begin.GetCheck()){
			int begin[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
			memset(pos_begin_return, -1, sizeof(pos_begin_return));
			memset(pos_begin, -1, sizeof(pos_begin));
			for(int i = 0; i < CHANGETIME; ++i){
				int iRand = rand() % 9;
				int tmp = begin[i % 9];
				begin[i % 9] = begin[iRand];
				begin[iRand] = tmp;
			}
			for(int i = 0; i < 9; ++i){
				m_init[i].SetBitmap(NULL);
				if(begin[i]){
					m_selectval = begin[i];
					changeBitmap(m_init, select_begin, pos_begin, pos_begin_return, i);
				}
			}
			m_selectval = 0;
		}
		if(m_random_end.GetCheck()){
			int end[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
			memset(pos_end_return, -1, sizeof(pos_end_return));
			memset(pos_end, -1, sizeof(pos_end));
			for(int i = 0; i < CHANGETIME; ++i){
				int iRand = rand() % 9;
				int tmp = end[i % 9];
				end[i % 9] = end[iRand];
				end[iRand] = tmp;
			}
			for(int i = 0; i < 9; ++i){
				m_end[i].SetBitmap(NULL);
				if(end[i]){
					m_selectval = end[i];
					changeBitmap(m_end, select_end, pos_end, pos_end_return, i);
				}
			}
			m_selectval = 0;
		}
		begin = getStatus(pos_begin_return);
		end = getStatus(pos_end_return);
	}while(( (CButton *)GetDlgItem(IDC_CHECK_NOANSWER) )->GetCheck() && 
		(search->getreverse(begin) & 1) != (search->getreverse(end) & 1) );
	if( ( (CButton *)GetDlgItem(IDC_CHECK_HAND) )->GetCheck() ){
		top = 0;
		path.clear();	
		path.push_back(getStatus(pos_begin_return) );
		nowstatus = getStatus(pos_begin_return);
		laststatus = getStatus(pos_end_return);	
	}
	GetMenu()->EnableMenuItem(ID_CREATE, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED);
	SetNowstep(0);
}


BOOL CAIDlg::statusReady(void)
{
	int i, ct;
	for(i = 0, ct = 0; i < 9; ++i){
		if(pos_begin_return[i] == -1 || pos_end_return[i] == -1)
			ct++;
	}
	return ct <= 2;
}

int CAIDlg::getStatus(int pos_return[])
{	
	for(int i = (NUM - 1), status = 0; i >= 0; --i){
		status *= 10;
		if(pos_return[i] > 0)
			status += pos_return[i];
	}
	return status;
}

void CAIDlg::SetStatus(CButton button[], CButton select[], int pos[], int pos_return[], int status){
	memset(pos, -1, sizeof(int) * NUM);
	memset(pos_return, -1, sizeof(int) * NUM);
	for(int i = 0; i < NUM; ++i){
		button[i].SetBitmap(NULL);
		if(status % 10){
			m_selectval = status % 10;
			changeBitmap(button, select, pos, pos_return, i);
		}
		status /= 10;
	}
}


void CAIDlg::OnBnClickedSearchType()
{
	// TODO: 在此添加控件通知处理程序代码
	switch(GetFocus()->GetDlgCtrlID()){
		case IDC_RADIO_DFS:
			search_type = TYPE_DFS;
			search = &dfs;
			break;
		case IDC_RADIO_BDFS:
			search_type = TYPE_BDFS;
			search = &bdfs;
			break;
		case IDC_RADIO_BFS:
			search_type = TYPE_BFS;
			search = &bfs;
			break;
		case IDC_RADIO_TBFS:
			search_type = TYPE_TBFS;
			search = &tbfs;
			break;
		case IDC_RADIO_ASTAR1:
			search_type = TYPE_ASTAR1;
			search = &astar1;
			break;
		case IDC_RADIO_ASTAR2:
			search_type = TYPE_ASTAR2;
			search = &astar2;
			break;
		case IDC_RADIO_IDFS:
			search_type = TYPE_IDFS;
			search = &idfs;
			break;
		case IDC_RADIO_IDA:
			search_type = TYPE_IDA;
			search = &ida;
			break;			
	}	
	SetInstroduction();
}

void CAIDlg::SetInstroduction()
{
	SetDlgItemText(IDC_EDIT_INTRO, search->getIntroduction() );
}


//时间统计函数：
__int64 FileTimeToQuadWord(PFILETIME pft){
	return (Int64ShllMod32(pft->dwHighDateTime, 32) | pft->dwLowDateTime);
}



//线程执行函数：
DWORD WINAPI SearchProc(LPVOID lpParameter){
	CAIDlg *p = (CAIDlg *) lpParameter;

	int begin = p->getStatus(p->pos_begin_return);
	int end = p->getStatus(p->pos_end_return);
	if(begin == end){
		p->MessageBox("一样的还用搜吗？", "^-^");
		p->gamestart = false;
		//恢复状态框按钮
		( (CButton *) p->GetDlgItem(IDC_CHECK_HAND) )->EnableWindow(TRUE);
		( (CButton *) p->GetDlgItem(IDC_BUTTON_DEFAULT) )->EnableWindow(TRUE);
		( (CButton *) p->GetDlgItem(IDC_BUTTON_RANDOM) )->EnableWindow(TRUE);
		( (CButton *) p->GetDlgItem(IDC_BUTTON_HAND) )->EnableWindow(TRUE);
		( (CButton *) p->GetDlgItem(IDC_CHECK_BEGIN) )->EnableWindow(TRUE);
		( (CButton *) p->GetDlgItem(IDC_CHECK_END) )->EnableWindow(TRUE);
		p->SetDlgItemText(IDC_BUTTON_BEGIN, "开始搜索");
		return 0;
	}
	p->GetMenu()->EnableMenuItem(ID_CREATE, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED);
	
	p->SetDlgItemText(IDC_EDIT_RESULT,  "搜索中……");


	//线程时间统计参数
	FILETIME ftKernelTimeStart, ftKernelTimeEnd;
	FILETIME ftUserTimeStart, ftUserTimeEnd;
	FILETIME ftDummy;
	__int64 qwKernelTimeElapsed, qwUserTimeElapsed, qwTotalTimeElapsed;
	
	//获取当前时间值
	GetThreadTimes(GetCurrentThread(), &ftDummy, &ftDummy, &ftKernelTimeStart, &ftUserTimeStart);

	p->stop = 0;

	switch(p->search_type){		
		case p->TYPE_BDFS:
			p->ans = p->search->search(begin, end, p->stop, p->m_maxstep);
			break;
		case p->TYPE_DFS:	
		case p->TYPE_BFS:
		case p->TYPE_TBFS:
		case p->TYPE_IDFS:
		case p->TYPE_IDA:
			p->ans = p->search->search(begin, end, p->stop);
			break;	
		case p->TYPE_ASTAR1:
		case p->TYPE_ASTAR2:
			p->ans = p->search->search(begin, end, p->stop, p->m_heuristic);
			break;	
	}

	//结束时时间值
	GetThreadTimes(GetCurrentThread(), &ftDummy, &ftDummy, &ftKernelTimeEnd, &ftUserTimeEnd);
	//Get the elapsed kernel and user times by 
	//converting the start and end times 
	//from FILETIMEs to quad words, and then 
	//subtract the start times from the end times.

	qwKernelTimeElapsed = FileTimeToQuadWord(&ftKernelTimeEnd) - FileTimeToQuadWord(&ftKernelTimeStart);

	qwUserTimeElapsed = FileTimeToQuadWord(&ftUserTimeEnd) - FileTimeToQuadWord(&ftUserTimeStart);

	//Get total time duration by adding the kernel
	//and user times.

	qwTotalTimeElapsed = qwKernelTimeElapsed + qwUserTimeElapsed;

	char str[30];
	sprintf(str, "时间：%.2lfms\r\n", ( (double)qwTotalTimeElapsed) / 10000);
	CString result = str;

	//搜索结果

	//显示
	result += p->search->getResult();
	p->SetDlgItemText(IDC_EDIT_RESULT,  result);

	if(p->ans == -1 ){
		p->MessageBox("此图无解！");		
	}else if(p->ans == -2){
		p->MessageBox("用户终止搜索！");			
	}else if(!p->ans){
		p->MessageBox("未找到解！");
	}else{		
		p->top = 0;
		p->search->getPath(p->path);
		( (CButton *)p->GetDlgItem(IDC_BUTTON_NEXT))->EnableWindow(TRUE);
		( (CButton *)p->GetDlgItem(IDC_BUTTON_AUTO))->EnableWindow(TRUE);
		p->nextstep.EnableWindow(TRUE);
		p->recover.EnableWindow(TRUE);
		p->display.EnableWindow(TRUE);		
		p->GetMenu()->EnableMenuItem(ID_CREATE, MF_BYCOMMAND | MF_ENABLED);
	}

	//搜索结束
	p->gamestart = false;

	//恢复状态框按钮
	( (CButton *) p->GetDlgItem(IDC_CHECK_HAND) )->EnableWindow(TRUE);
	( (CButton *) p->GetDlgItem(IDC_BUTTON_DEFAULT) )->EnableWindow(TRUE);
	( (CButton *) p->GetDlgItem(IDC_BUTTON_RANDOM) )->EnableWindow(TRUE);
	( (CButton *) p->GetDlgItem(IDC_BUTTON_HAND) )->EnableWindow(TRUE);
	( (CButton *) p->GetDlgItem(IDC_CHECK_BEGIN) )->EnableWindow(TRUE);
	( (CButton *) p->GetDlgItem(IDC_CHECK_END) )->EnableWindow(TRUE);
	( (CButton *) p->GetDlgItem(IDC_CHECK_NOANSWER) )->EnableWindow(TRUE);	
	p->SetDlgItemText(IDC_BUTTON_BEGIN, "开始搜索");
	return 0;
}

#ifdef TEST

DWORD WINAPI TestProc(LPVOID lpParameter){
	CAIDlg *p = (CAIDlg *) lpParameter;
	const int M = 35;
	struct Test{
		double B;
		int step;		
	}test_bfs[M], test_tbfs[M], test_a1[M], test_a2[M], test_ids[M];
	int count[M];
	memset(test_bfs, 0, sizeof(test_bfs) );
	memset(test_tbfs, 0, sizeof(test_tbfs) );
	memset(test_a1, 0, sizeof(test_a1) );
	memset(test_a2, 0, sizeof(test_a2) );
	memset(test_ids, 0, sizeof(test_ids) );
	memset(count, 0, sizeof(count) );
	for(int i = 0; i < M; ++i){
		test_bfs[i].B = test_tbfs[i].B = test_a1[i].B 
			= test_a2[i].B = test_ids[i].B = 0.;
	}
	int stop = 0;
	for(int i = 1; i <= 50000; ++i){
		p->OnBnClickedButtonRandom();
		p->SetNowstep(i);
		int begin = p->getStatus(p->pos_begin_return);
		int end = p->getStatus(p->pos_end_return);

		//bfs
		p->search = &p->bfs;
		p->search->search(begin, end, stop);
		int step = p->search->getStep();
		count[step]++;
		test_bfs[step].step += p->search->getTotalnode();
		test_bfs[step].B += p->search->getB();

		//tbfs
		p->search = &p->tbfs;
		p->search->search(begin, end, stop);			
		test_tbfs[step].step += p->search->getTotalnode();