第七講搜索-文庫吧
2025-09-07 13:01 本頁面
【正文】 6 5 7 ?方案一：每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)九進(jìn)制數(shù)， 則 4個(gè)字節(jié)就能表示一個(gè)節(jié)點(diǎn) 。 此方案需要編寫字符串形式的 9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。 判重 ? 合理編碼，減小存儲(chǔ)代價(jià) ? 不同的編碼方式所需要的存儲(chǔ)空間會(huì)有較大差別 8 2 3 4 1 6 5 7 ?方案二：為結(jié)點(diǎn)編號(hào) ?把每個(gè)結(jié)點(diǎn)都看一個(gè)排列，以此排列在全部排列中的位置作為其編號(hào) ?排列總數(shù)： 9!=362880 ?只需要一個(gè)整數(shù) (4字節(jié) )即可存下一個(gè)結(jié)點(diǎn) ?判重用的標(biāo)志數(shù)組只需要 362880字節(jié)即可。 此方案比方案 1省空間； 此方案需要編寫給定排列求序號(hào)和給定序號(hào)求排列的函數(shù)，這些函數(shù)的執(zhí)行速度慢于字符串形式的 9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。 判重 ? 時(shí)間與空間的權(quán)衡 ? 對(duì)于狀態(tài)數(shù)較小的問題，可以用最直接的方式編碼以空間換時(shí)間； ? 對(duì)于狀態(tài)數(shù)太大的問題，需要利用好的編碼方法以時(shí)間換空間； ? 具體問題具體分析。 輸入數(shù)據(jù)： 2 3 4 1 5 x 7 6 8 輸出結(jié)果： ullddrurdllurdruldr 用廣搜解決八數(shù)碼問題 2 3 4 1 5 7 6 8 輸入數(shù)據(jù)代表： 移動(dòng)序列中 u 表示使空格上移 d 表示使空格下移 r 表示使空格右移 l 表示使空格左移 1 2 3 4 5 6 7 8 輸出數(shù)據(jù)是一個(gè)移動(dòng)序列，使得移動(dòng)后結(jié)果變成 //本程序在 ai上會(huì)超內(nèi)存，在 acm上能過 include iostream using namespace std。 int nGoalStatus。 //目標(biāo)狀態(tài) unsigned char szFlag[48427562]。 //節(jié)點(diǎn)是否擴(kuò)展的標(biāo)記 char szResult[1000000]。 char szMoves[1000000]。 //移動(dòng)步驟 int anFather[1000000]。 //父節(jié)點(diǎn)指針 int MyQueue[1000000]。 //狀態(tài)隊(duì)列 int nQHead。 int nQTail。 char sz4Moves[] = udrl。//四種動(dòng)作 八數(shù)碼例子程序 int NineToTen( char * s ) //九進(jìn)制字符串轉(zhuǎn)十進(jìn)制 { int nResult = 0。 for( int i = 0。 s[i]。 i ++ ) { nResult *= 9。 nResult += s[i] 39。039。 } return nResult。 } int GetBit( unsigned char c,int n) { return ( c n ) amp。 1。 } void SetBit( unsigned char amp。 c, int n,int v) { if( v ) c |= (1 n)。 else c amp。= ~(1 n)。 } int TenToNine( int n, char * s) //十進(jìn)制數(shù)轉(zhuǎn)九進(jìn)制字符串?？赡苡星皩?dǎo) 0 //返回 0的位置 { int nZeroPos。 int nBase = 1。 int j = 0。 while( nBase = n) nBase *= 9。 nBase /= 9。 do { s[j] = n/nBase + 39。039。 if( s[j] == 39。039。 ) nZeroPos = j。 j ++。 n %= nBase。 nBase /= 9。 }while( nBase = 1 )。 s[j] = 0。 //判是否要加前導(dǎo) 0 if( j 9 ) { for( int i = j + 1。 i 0。 i ) s[i] = s[i1]。 s[0] = 39。039。 return 0。 } return nZeroPos。 } int NewStatus( int nStatus, char cMove) //求從 nStatus經(jīng)過 cMove 移動(dòng)后得到的新狀態(tài) //若移動(dòng)不可行則返回 1 { char szTmp[20]。 int nZeroPos = TenToNine(nStatus,szTmp)。 switch( cMove) { case 39。u39。: if( nZeroPos 3 0 ) return 1。 else { szTmp[nZeroPos] = szTmp[nZeroPos 3]。 szTmp[nZeroPos 3] = 39。039。 } break。 case 39。d39。: if( nZeroPos + 3 8 ) return 1。 else { szTmp[nZeroPos] = szTmp[nZeroPos + 3]。 szTmp[nZeroPos + 3] = 39。039。 } break
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1