8数码问题的c++代码

大小: 457KB

文件类型: .zip

金币: 1

下载: 0 次

发布日期: 2021-06-13
语言: C/C++
标签: 8数码 c++ 源代码

高速下载

资源简介

参见我的博文：http://blog.csdn.net/j56754gefge/article/details/47170967 这是8数码问题的一套完整解决方案，包括问题模型、搜索方法、界面表示等。有问题请给我发邮件，代码里面有我mail

资源截图

小图大图

代码片段和文件信息

#include “Astar.h“
#include 
#include 
using namespace std;

int Astar::node::search_mode;


Astar::Astar（）
{
	movement[0] = &node::up; 
	movement[1] = &node::down; 
	movement[2] = &node::left; 
	movement[3] = &node::right;
}


unsigned char  Astar::getInverseNumber（ unsigned char num[9] ）
{
	unsigned char inverse_number = 0;
	for（ unsigned char i=0; i<8; i++ ）
		if（ num[i] ）
			for（ unsigned char j=i+1; j<9; j++ ）
				if（ num[j] && num[i] > num[j] ）
					inverse_number++;
	return inverse_number%2; // 0 or 1
}

bool  Astar::reachable（ unsigned char num[9] ）
{
	unsigned char n = getInverseNumber（ num ）;
	unsigned char goal_inverse_number = getInverseNumber（ puzzle8::goal ）;
	return n==goal_inverse_number;
}

int  Astar::seearch（ unsigned char init_state[9] MODE mode ）
{
	node::search_mode = mode;
	if（ !reachable（ init_state ） ）
		return -1;
	node *current = new node;
	current->state.set（ init_state ）;
	if（ current->isGoal（） ）{
		delete current;
		return 0;
	}
	// store all allocated nodes as well as the corresponding eigen value
	map caches; // all nodes
	map::iterator cache_iter;	
	unsigned long long key[4];
	current->state.toEigenVal（ key ）;
	caches[key[0]] = current;
	// queue each leaf node according to its priority
	priority_queue > open_table; // nodes to expand
	open_table.push（ make_pair（-current->cost（）current） ）;
	// search
	bool stopped = false;
	for（ int cnt=0; !open_table.empty（） && !stopped; cnt++ ）{
		current = open_table.top（）.second;
		open_table.pop（）;		
		//current->state.print（）; cout<		// try to expand: get child node‘s eigen value to test if it has been found before
		current->state.children（ key ）;
		int child_depth = current->depth + 1;
		for（ int m=0; m<4; m++ ）{
			if（ !key[m] ）
				continue;
			cache_iter = caches.find（ key[m] ）;
			bool not_found = cache_iter==caches.end（）;
			// if the child node is new or though it was found before but now is with a shallow depth
			// then we should indeed create it add it to our queue
			if（ not_found || child_depth < cache_iter->second->depth ）{
				node *next = （current->*（movement[m]））（）;
				if（ not_found ）
					caches[key[m]] = next;
				else
					cache_iter->second = next;
				open_table.push（ make_pair（-next->cost（）next） ）;
				if（ next->isGoal（） ）{
					current = next;
					stopped = true;
					break;
				}
			}
		}
	}
	// searching is done. now retrieve path by backtracking
	if（ !current->isGoal（） ）
		return -1;
	vector move_path;
	while（ current->parent ）{
		move_path.push_back（ current ）;
		current = current->parent;
	}
	int search_depth = move_path.size（）;
	search_result.resize（ search_depth ）;
	vector::iterator result_itr = search_result.begin（）;
	for（ vector::reverse_iterator itr=move_path.rbegin（）; itr!=move_path.rend（）; itr++ ）
		*（resu

属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-07-31 16:32  8数码\
     文件     1173504  2015-07-31 16:29  8数码\8数码.exe
     文件        4101  2015-07-31 16:29  8数码\Astar.cpp
     文件        2192  2015-07-31 16:28  8数码\Astar.h
     文件        2150  2015-07-31 16:23  8数码\demo.cpp
     文件         259  2015-07-30 19:07  8数码\puzzle8.cpp
     文件        5104  2015-07-31 16:28  8数码\puzzle8.h
     文件        4324  2015-07-31 13:16  8数码\puzzle_game.cpp
     文件         660  2015-07-31 12:10  8数码\puzzle_game.h

上一篇：21点游戏代码 C语言
下一篇：Windows屏幕截图工具C++源代码

共有条评论

8数码问题的c++代码

资源简介

资源截图

代码片段和文件信息

评论

相关资源