免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開APP
userphoto
未登錄

開通VIP，暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP

首頁

好書

留言交流

下載APP

聯(lián)系客服
拼圖算法分析...
一、題目說明：
　　（九宮問題）在一個(gè)３×３的九宮中有１－８這８?jìng)€(gè)數(shù)及一個(gè)空格隨機(jī)的擺放在其中的格子里，如圖１－１所示。現(xiàn)在要求實(shí)現(xiàn)這個(gè)問題：將該九宮格調(diào)整為如圖１－１右圖所示的形式。調(diào)整的規(guī)則是：每次只能將與空格（上、下、或左、右）相鄰的一個(gè)數(shù)字平移到空格中。試編程實(shí)現(xiàn)這一問題的求解。

（圖１－１）

二、題目分析：
　　九宮問題是人工智能中的經(jīng)典難題之一，問題是在３×３方格棋盤中，放８格數(shù)，剩下的沒有放到的為空，每次移動(dòng)只能是和相鄰的空格交換數(shù)。程序自動(dòng)產(chǎn)生問題的初始狀態(tài)，通過一系列交換動(dòng)作將其轉(zhuǎn)換成目標(biāo)排列（如下圖１－２到圖１－３的轉(zhuǎn)換）。

 

 

 

 

（圖１－２）    （圖１－３）

　　九宮問題中，程序產(chǎn)生的隨機(jī)排列轉(zhuǎn)換成目標(biāo)共有兩種可能，而且這兩種不可能同時(shí)成立，也就是奇數(shù)排列和偶數(shù)排列。我們可以把一個(gè)隨機(jī)排列的數(shù)組從左到右從上到下用一個(gè)一維數(shù)組表示，如上圖１－２我們就可以表示成｛８，７，１，５，２，６，３，４，０｝其中０代表空格。
在這個(gè)數(shù)組中我們首先計(jì)算它能夠重排列出來的結(jié)果，公式就是：

∑（Ｆ（Ｘ））＝Ｙ，其中Ｆ（Ｘ）

　　就是一個(gè)數(shù)他前面比這個(gè)數(shù)小的數(shù)的個(gè)數(shù)，Ｙ為奇數(shù)和偶數(shù)個(gè)有一種解法。那么上面的數(shù)組我們就可以解出它的結(jié)果。

Ｆ（８）＝０；
Ｆ（７）＝０；
Ｆ（１）＝０；
Ｆ（５）＝１；
Ｆ（２）＝１；
Ｆ（６）＝３；
Ｆ（３）＝２；
Ｆ（４）＝３；
Ｙ＝０＋０＋０＋１＋１＋３＋２＋３＝１０

　　Ｙ＝１０是偶數(shù)，所以他的重排列就是如圖１－３的結(jié)果，如果加起來的結(jié)果是奇數(shù)重排的結(jié)果就是如圖１－１最右邊的排法。

三、算法分析
　　九宮問題的求解方法就是交換空格（０）位置，直至到達(dá)目標(biāo)位置為止。圖形表示就是：

（圖３－１）

　　要想得到最優(yōu)的就需要使用廣度優(yōu)先搜索，九宮的所以排列有９！種，也就是３６２８８０種排法，數(shù)據(jù)量是非常大的，我使用的廣度搜索，需要記住每一個(gè)結(jié)點(diǎn)的排列形式，要是用數(shù)組記錄的話會(huì)占用很多的內(nèi)存，我們把數(shù)據(jù)進(jìn)行適當(dāng)?shù)膲嚎s。使用ＤＷＯＲＤ形式保存，壓縮形式是每個(gè)數(shù)字用３位表示，這樣就是３×９＝２７個(gè)字節(jié)，由于８的二進(jìn)制表示形式１０００，不能用３位表示，我使用了一個(gè)小技巧就是將８表示位０００，然后用多出來的５個(gè)字表示８所在的位置，就可以用ＤＷＯＲＤ表示了。用移位和或操作將數(shù)據(jù)逐個(gè)移入，比乘法速度要快點(diǎn)。定義了幾個(gè)結(jié)果來存儲(chǔ)遍歷到了結(jié)果和搜索完成后保存最優(yōu)路徑。
類結(jié)構(gòu)如下：

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();
};

　　計(jì)算隨機(jī)隨機(jī)數(shù)組使用了vector模板用random_shuffle（，）函數(shù)來打亂數(shù)組數(shù)據(jù)，并計(jì)算目標(biāo)結(jié)果是什么。代碼：

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;
}

 

數(shù)據(jù)壓縮函數(shù)實(shí)現(xiàn)：

inline voidCNineGird::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;
}

解壓縮時(shí)跟壓縮真好相反，解壓代碼：

inline void CNineGird::DwordToArray(DWORDdata , 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;
}

　　由于可擴(kuò)展的數(shù)據(jù)量非常的大，加上我在保存的時(shí)候使用的是ＤＷＯＲＤ類型，將每一步數(shù)據(jù)都記錄在一個(gè)排序二叉樹中，按從小到大從左到有的排列，搜索的時(shí)候跟每次搜索將近萬次的形式比較快幾乎是Ｎ次方倍，把幾個(gè)在循環(huán)中用到的函數(shù)聲明為內(nèi)聯(lián)函數(shù)，并在插入的時(shí)候同時(shí)搜索插入的數(shù)據(jù)會(huì)不會(huì)在樹中有重復(fù)來加快總體速度。二叉樹插入代碼：

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);
}

計(jì)算結(jié)果是奇數(shù)排列還是偶數(shù)排列的代碼：

bool CNineGird::EstimateUncoil(unsignedchar *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;
}

　　移動(dòng)到空格位的代碼比較簡(jiǎn)單，只要計(jì)算是否會(huì)移動(dòng)到框外面就可以了，并在移動(dòng)的時(shí)候順便計(jì)算一下是不是已經(jīng)是目標(biāo)結(jié)果，這是用來給用戶手工移動(dòng)是給與提示用的，代碼：

inline bool CNineGird::MoveChess(unsignedchar *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;
}

　　我在進(jìn)行廣度搜索時(shí)候，將父結(jié)點(diǎn)所在的數(shù)組索引記錄在子結(jié)點(diǎn)中了，所以得到目標(biāo)排列的時(shí)候，我們只要從子結(jié)點(diǎn)逆向搜索就可以得到最優(yōu)搜索路徑了。用變量m_iPathsize來記錄總步數(shù)，具體函數(shù)代碼：

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;
}

 

　　動(dòng)態(tài)排列的演示函數(shù)最簡(jiǎn)單了，為了讓主窗體有及時(shí)刷新的機(jī)會(huì)，啟動(dòng)了一個(gè)線程在需要主窗體刷新的時(shí)候，用Ｓｌｅｅ（ＵＩＮＴ）函數(shù)來暫停一下線程就可以了。代碼：

unsigned __stdcall MoveChessThread(LPVOIDpParam)
{
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計(jì)算步驟用時(shí)%d毫秒" ,pGird->m_iTime);
MessageBox(NULL , msg , "~_~" , 0);
pGird->m_bAutoRun = false;
return 0L;
}

　　最后介紹一下搜索函數(shù)的原理，首先得到源數(shù)組，將其轉(zhuǎn)換成ＤＷＯＲＤ型，與目標(biāo)比較，如果相同完成，不同就交換一下數(shù)據(jù)和空格位置，加入二叉樹，搜索下一個(gè)結(jié)果，直到?jīng)]有步可走了，在搜索剛剛搜索到的位置的子位置，這樣直到找到目標(biāo)結(jié)果為止，函數(shù)：

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)) //是否移動(dòng)成功
{
ArrayToDword(temparray , fountain);
if (AddTree(fountain, m_pPlaceList)) //加入搜索數(shù)
{
m_pScanbuf[ child ].Place = fountain;
m_pScanbuf[ child ].ScanID = parentID;
if (fountain == target) //是否找到結(jié)果
{
m_iTime = clock() - tim;
GetPath(child);//計(jì)算路徑
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;
}

 

重要函數(shù)的介紹結(jié)束，下面是程序的運(yùn)行結(jié)果和運(yùn)算結(jié)果：

  轉(zhuǎn)自：http://www.qqgb.com/Program/VC/VCarithmetic/Program_55328_3.html

本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。
打開APP，閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
c#調(diào)用c++的ocx控件傳遞數(shù)組
64位（
利用偽造內(nèi)核文件來繞過IceSword的檢測(cè)
使用C編譯器產(chǎn)生清晰的二進(jìn)制文件
用C/C++實(shí)現(xiàn)SMC動(dòng)態(tài)代碼加密技術(shù)
VC數(shù)據(jù)類型
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)！
如果VIP功能使用有故障，
可點(diǎn)擊這里聯(lián)系客服！

聯(lián)系客服