九宫问题是人工智能中的经典难题之一,问题是在3×3方格棋盘中,放8格数,剩下的没有放到的为空,每次移动只能是和相邻的空格交换数。程序自动产生问题的初始状态,通过一系列交换动作将其转换成目标排列(如下图1-2到图1-3的转换)
九宫问题中,程序产生的随机排列转换成目标共有两种可能,而且这两种不可能同时成立,也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个一维数组表示,如上图1-2我们就可以表示成{8,7,1,5,2,6,3,4,0}其中0代表空格。
在这个数组中我们首先计算它能够重排列出来的结果,公式就是:
∑(F(X))=Y,其中F(X)
就是一个数他前面比这个数小的数的个数,Y为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。
F(8)=0;
F(7)=0;
F(1)=0;
F(5)=1;
F(2)=1;
F(6)=3;
F(3)=2;
F(4)=3;
Y=0+0+0+1+1+3+2+3=10
Y=10是偶数,所以他的重排列就是如图1-3的结果,如果加起来的结果是奇数重排的结果就是如图1-1最右边的排法。
要想得到最优的就需要使用广度优先搜索,九宫的所以排列有9!种,也就是362880种排法,数据量是非常大的,我使用的广度搜索,需要记住每一个结点的排列形式,要是用数组记录的话会占用很多的内存,我们把数据进行适当的压缩。使用DWORD形式保存,压缩形式是每个数字用3位表示,这样就是3×9=27个字节,由于8的二进制表示形式1000,不能用3位表示,我使用了一个小技巧就是将8表示位000,然后用多出来的5个字表示8所在的位置,就可以用DWORD表示了。用移位和或操作将数据逐个移入,比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。
}
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;
}
动态排列的演示函数最简单了,为了让主窗体有及时刷新的机会,启动了一个线程在需要主窗体刷新的时候,用Slee(UINT)函数来暂停一下线程就可以了。代码:
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;
}
最后介绍一下搜索函数的原理,首先得到源数组,将其转换成DWORD型,与目标比较,如果相同完成,不同就交换一下数据和空格位置,加入二叉树,搜索下一个结果,直到没有步可走了,在搜索刚刚搜索到的位置的子位置,这样直到找到目标结果为止,函数:
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;
}
哇!有点长,看不太懂!慢慢研究下
图在哪呢?
图在百度里找吧
v也就是奇数排列和偶数排列
谢谢 分享
奇数排列和偶数排列
随机排列转换成目标
经典难题之一
奇数和偶数个有一种解法
Y=10是偶数,所以他的重排列就是如图1-3的结果
数组我们就可以解出它的结果
经典难题之一
偶数个有一种解法。