招工做的网站,app拉新推广赚佣金,东莞h5网站制作,资料网站怎么做From: http://blog.sina.com.cn/s/blog_6a4b57e30100mfch.html
一、题目说明#xff1a; #xff08;九宫问题#xff09;在一个#xff13;#xff13;的九宫中有#xff11;#xff0d;#xff18;这#xff18;个数及一个空格随机的摆放在其中的格子里#…From: http://blog.sina.com.cn/s/blog_6a4b57e30100mfch.html
一、题目说明 九宫问题在一个×的九宫中有这个数及一个空格随机的摆放在其中的格子里如图所示。现在要求实现这个问题将该九宫格调整为如图右图所示的形式。调整的规则是每次只能将与空格上、下、或左、右相邻的一个数字平移到空格中。试编程实现这一问题的求解。 图 二、题目分析 九宫问题是人工智能中的经典难题之一问题是在×方格棋盘中放格数剩下的没有放到的为空每次移动只能是和相邻的空格交换数。程序自动产生问题的初始状态通过一系列交换动作将其转换成目标排列如下图到图的转换。 图 图 九宫问题中程序产生的随机排列转换成目标共有两种可能而且这两种不可能同时成立也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个一维数组表示如上图我们就可以表示成其中代表空格。 在这个数组中我们首先计算它能够重排列出来的结果公式就是
∑其中 就是一个数他前面比这个数小的数的个数为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。 是偶数所以他的重排列就是如图的结果如果加起来的结果是奇数重排的结果就是如图最右边的排法。 三、算法分析 九宫问题的求解方法就是交换空格位置直至到达目标位置为止。图形表示就是 图 要想得到最优的就需要使用广度优先搜索九宫的所以排列有种也就是种排法数据量是非常大的我使用的广度搜索需要记住每一个结点的排列形式要是用数组记录的话会占用很多的内存我们把数据进行适当的压缩。使用形式保存压缩形式是每个数字用位表示这样就是×个字节由于的二进制表示形式不能用位表示我使用了一个小技巧就是将表示位然后用多出来的个字表示所在的位置就可以用表示了。用移位和或操作将数据逐个移入比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。 类结构如下
// NineGrid.h
class CNineGird
{
public:
struct PlaceList
{
DWORD Place;
PlaceList* Left;
PlaceList* Right;
};
struct Scanbuf
{
DWORD Place;
int ScanID;
};
struct PathList
{
unsigned char Path[9];
};
private:
PlaceList *m_pPlaceList;
Scanbuf *m_pScanbuf;
RECT m_rResetButton;
RECT m_rAutoButton;
public:
int m_iPathsize;
clock_t m_iTime;
UINT m_iStepCount;
unsigned char m_iTargetChess[9];
unsigned char m_iChess[9];
HWND m_hClientWin;
PathList *m_pPathList;
bool m_bAutoRun;
private:
inline bool AddTree(DWORD place , PlaceList* parent);
void FreeTree(PlaceList* parent);
inline void ArrayToDword(unsigned char *array , DWORD data);
inline void DwordToArray(DWORD data , unsigned char *array);
inline bool MoveChess(unsigned char *array , int way);
bool EstimateUncoil(unsigned char *array);
void GetPath(UINT depth);
public:
void MoveChess(int way);
bool ComputeFeel();
void ActiveShaw(HWND hView);
void DrawGird(HDC hDC , RECT clientrect);
void DrawChess(HDC hDC , RECT clientrect);
void Reset();
void OnButton(POINT pnt , HWND hView);
public:
CNineGird();
~CNineGird();
};
计算随机随机数组使用了vector模板用random_shuffle函数来打乱数组数据并计算目标结果是什么。代码 // NineGrid.cpp
#include NineGrid.h
void CNineGird::Reset()
{
if(m_bAutoRun) return;
vector vs;
int i;
for (i 1 ; i 9 ; i )
vs.push_back(i);
vs.push_back(0);
random_shuffle(vs.begin(), vs.end());
random_shuffle(vs.begin(), vs.end());
for ( i 0 ; i 9 ; i )
{
m_iChess[i] vs[i];
}
if (!EstimateUncoil(m_iChess))
{
unsigned char array[9] {1,2,3,8,0,4,7,6,5};
memcpy(m_iTargetChess , array , 9);
}
else
{
unsigned char array[9] {1,2,3,4,5,6,7,8,0}
;
memcpy(m_iTargetChess , array , 9);
}
m_iStepCount 0;
}
// 数据压缩函数实现
inline void CNineGird::ArrayToDword(unsigned char *array , DWORD data)
{
unsigned char night 0;
for ( int i 0 ; i 9 ; i )
{
if (array[i] 8)
{
night (unsigned char)i;
break;
}
}
array[night] 0;
data 0;
data (DWORD)((DWORD)array[0] 29 | (DWORD)array[1] 26 |
(DWORD)array[2] 23 | (DWORD)array[3] 20 |
(DWORD)array[4] 17 | (DWORD)array[5] 14 |
(DWORD)array[6] 11 | (DWORD)array[7] 8 |
(DWORD)array[8] 5 | night);
array[night] 8;
}
// 解压缩时跟压缩真好相反解压代码
inline void CNineGird::DwordToArray(DWORD data , unsigned char *array)
{
unsigned char chtem;
for ( int i 0 ; i 9 ; i )
{
chtem (unsigned char)(data (32 - (i 1) * 3) 0x00000007);
array[i] chtem;
}
chtem (unsigned char)(data 0x0000001F);
array[chtem] 8;
}
// 由于可扩展的数据量非常的大加上我在保存的时候使用的是类型将每一步数据都记录在一个排序二叉树中按从小到大从左到有的排列搜索的时候跟每次搜索将近万次的形式比较快几乎是次方倍把几个在循环中用到的函数声明为内联函数并在插入的时候同时搜索插入的数据会不会在树中有重复来加快总体速度。二叉树插入代码
inline bool CNineGird::AddTree(DWORD place , PlaceList* parent)
{
if (parent NULL)
{
parent new PlaceList();
parent-Left parent-Right NULL;
parent-Place place;
return true;
}
if (parent-Place place)
return false;
if (parent-Place place)
{
return AddTree(place , parent-Right);
}
return AddTree(place , parent-Left);
}
// 计算结果是奇数排列还是偶数排列的代码
bool CNineGird::EstimateUncoil(unsigned char *array)
{
int sun 0;
for ( int i 0 ; i 8 ; i )
{
for ( int j 0 ; j 9 ; j )
{
if (array[j] ! 0)
{
if (array[j] i 1 )
break;
if (array[j] i 1)
sun;
}
}
}
if (sun % 2 0)
return true;
else
return false;
}
// 移动到空格位的代码比较简单只要计算是否会移动到框外面就可以了并在移动的时候顺便计算一下是不是已经是目标结果这是用来给用户手工移动是给与提示用的代码
inline bool CNineGird::MoveChess(unsigned char *array , int way)
{
int zero , chang;
bool moveok false;
for ( zero 0 ; zero 9 ; zero )
{
if (array[zero] 0)
break;
}
POINT pnt;
pnt.x zero % 3;
pnt.y int(zero / 3);
switch(way)
{
case 0 : //up
if (pnt.y 1 3)
{
chang (pnt.y 1) * 3 pnt.x ;
array[zero] array[chang];
array[chang] 0;
moveok true;
}
break;
case 1 : //down
if (pnt.y - 1 -1)
{
chang (pnt.y - 1) * 3 pnt.x ;
array[zero] array[chang];
array[chang] 0;
moveok true;
}
break;
case 2 : //left
if (pnt.x 1 3)
{
chang pnt.y * 3 pnt.x 1;
array[zero] array[chang];
array[chang] 0;
moveok true;
}
break;
case 3 : //right
if (pnt.x - 1 -1)
{
chang pnt.y * 3 pnt.x - 1;
array[zero] array[chang];
array[chang] 0;
moveok true;
}
break;
}
if (moveok !m_bAutoRun)
{
m_iStepCount ;
DWORD temp1 ,temp2;
ArrayToDword(array , temp1);
ArrayToDword(m_iTargetChess , temp2);
if (temp1 temp2)
{
MessageBox(NULL , 你真聪明这么快就搞定了! , ^_^ , 0);
}
}
return moveok;
}
// 我在进行广度搜索时候将父结点所在的数组索引记录在子结点中了所以得到目标排列的时候我们只要从子结点逆向搜索就可以得到最优搜索路径了。用变量m_iPathsize来记录总步数具体函数代码
void CNineGird::GetPath(UINT depth)
{
int now 0 , maxpos 100 ;
UINT parentid;
if (m_pPathList ! NULL)
{
delete[] m_pPathList;
}
m_pPathList new PathList[maxpos];
parentid m_pScanbuf[depth].ScanID;
DwordToArray(m_pScanbuf[depth].Place , m_pPathList[now].Path);
while(parentid ! -1)
{
if (now maxpos)
{
maxpos 10;
PathList * temlist new PathList[maxpos];
memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));
delete[] m_pPathList;
m_pPathList temlist;
}
DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[now].Path);
parentid m_pScanbuf[parentid].ScanID;
}
m_iPathsize now;
}
// 动态排列的演示函数最简单了为了让主窗体有及时刷新的机会启动了一个线程在需要主窗体刷新的时候用函数来暂停一下线程就可以了。代码
unsigned __stdcall MoveChessThread(LPVOID pParam)
{
CNineGird * pGird (CNineGird *)pParam;
RECT rect;
pGird-m_iStepCount 0;
::GetClientRect(pGird-m_hClientWin , rect);
for ( int i pGird-m_iPathsize ; i 0 ; i --)
{
memcpy(pGird-m_iChess , pGird-m_pPathList[i].Path , 9);
pGird-m_iStepCount ;
InvalidateRect( pGird-m_hClientWin , rect , false);
Sleep(300);
}
char msg[100];
sprintf(msg , ^_^ ! 搞定了!\r\n计算步骤用时%d毫秒 , pGird-m_iTime);
MessageBox(NULL , msg , ~_~ , 0);
pGird-m_bAutoRun false;
return 0L;
}
// 最后介绍一下搜索函数的原理首先得到源数组将其转换成型与目标比较如果相同完成不同就交换一下数据和空格位置加入二叉树搜索下一个结果直到没有步可走了在搜索刚刚搜索到的位置的子位置这样直到找到目标结果为止函数
bool CNineGird::ComputeFeel()
{
unsigned char *array m_iChess;
UINT i;
const int MAXSIZE 362880;
unsigned char temparray[9];
DWORD target , fountain , parent , parentID 0 , child 1;
ArrayToDword(m_iTargetChess , target);
ArrayToDword(array , fountain);
if (fountain target)
{
return false;
}
if (m_pScanbuf ! NULL)
{
delete[] m_pScanbuf;
}
m_pScanbuf new Scanbuf[MAXSIZE];
AddTree(fountain ,m_pPlaceList);
m_pScanbuf[ 0 ].Place fountain;
m_pScanbuf[ 0 ].ScanID -1;
clock_t tim clock();
while(parentID MAXSIZE child MAXSIZE)
{
parent m_pScanbuf[parentID].Place;
for ( i 0 ; i 4 ; i ) // 0 :UP , 1:Down ,2:Left,3:Right
{
DwordToArray(parent , temparray);
if (MoveChess(temparray,i)) //是否移动成功
{
ArrayToDword(temparray , fountain);
if (AddTree(fountain, m_pPlaceList)) //加入搜索数
{
m_pScanbuf[ child ].Place fountain;
m_pScanbuf[ child ].ScanID parentID;
if (fountain target) //是否找到结果
{
m_iTime clock() - tim;
GetPath(child);//计算路径
FreeTree(m_pPlaceList);
delete[] m_pScanbuf;
m_pScanbuf NULL;
return true;
}
child ;
}
}
} // for i
parentID;
}
m_iTime clock() - tim;
FreeTree(m_pPlaceList);
delete[] m_pScanbuf;
m_pScanbuf NULL;
return false;
}
重要函数的介绍结束下面是程序的运行结果和运算结果 转自http://www.qqgb.com/Program/VC/VCarithmetic/Program_55328_3.html
