第七讲搜索

第七讲搜索内容摘要：

case 39。 l39。 : if( nZeroPos % 3 == 0) return 1。 else { szTmp[nZeroPos] = szTmp[nZeroPos 1]。 szTmp[nZeroPos 1 ] = 39。 039。 } break。 case 39。 r39。 : if( nZeroPos % 3 == 2) return 1。 else { szTmp[nZeroPos] = szTmp[nZeroPos + 1]。 szTmp[nZeroPos + 1 ] = 39。 039。 } break。 } return NineToTen(szTmp)。 } bool Bfs(int nStatus) { int nNewStatus。 nQHead = 0。 nQTail = 1。 MyQueue[nQHead] = nStatus。 while ( nQHead != nQTail) { //队列不为空 nStatus = MyQueue[nQHead]。 if( nStatus == nGoalStatus ) {//找到目标状态 return true。 } for( int i = 0。 i 4。 i ++ ) { //尝试 4种移动 nNewStatus = NewStatus(nStatus,sz4Moves[i])。 if( nNewStatus == 1 ) continue。 //不可移，试下一种移法 int nByteNo = nNewStatus / 8。 int nBitNo = nNewStatus % 8。 if( GetBit( szFlag[nByteNo],nBitNo)) continue。 //如果扩展标记已经存在， //则不能入队 //设上已扩展标记 SetBit( szFlag[nByteNo],nBitNo,1)。 //新节点入队列 MyQueue[nQTail] = nNewStatus。 anFather[nQTail] = nQHead。 //记录父节点 //记录本节点是由父节点经什么动作而来 szMoves[nQTail] = sz4Moves[i]。 nQTail ++。 } nQHead ++。 } return false。 } int main() { nGoalStatus = NineToTen(123456780)。 memset(szFlag,0,sizeof(szFlag))。 char szLine[50]。 char szLine2[20]。 (szLine,48)。 int i,j。 //将输入的原始字符串变为九进制字符串 for( i = 0, j = 0。 szLine[i]。 i ++ ) { if( szLine[i] != 39。 39。 ) { if( szLine[i] == 39。 x39。 ) szLine2[j++] = 39。 039。 else szLine2[j++] = szLine[i]。 } } szLine2[j] = 0。 if( Bfs(NineToTen(szLine2))) { int nMoves = 0。 int nPos = nQHead。 do { szResult[nMoves++] = szMoves[nPos]。 nPos = anFather[nPos]。 } while( nPos)。 for( int i = nMoves 1。 i = 0。 i ) { cout szResult[i]。 } } else cout unsolvable endl。 } 用深搜解决本题不好。 如用递归实现，不作特殊处理的话，很容易就导致递归层数太多而栈溢出。 可以不写递归，自己用大数组实现一个栈。 这可以避免栈溢出。 但是可能导致输出结果的步数太多（几万步），这样交到 POJ上会 Output limit exceeded 如果运气很坏，也可能数组会不够用。 用深搜解决八数码问题 广搜与深搜的比较  广搜一般用于状态表示比较简单、求最优策略的问题  需要保存所有扩展出的状态，占用的空间大；  每次扩展出结点时所走过的路径均是最短路；  深搜几乎可以用于任何问题  只需要保存从起始状态到当前状态路径上的结点；  根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择。 影响搜索效率的因素  影响搜索效率的因素 搜索对象 (枚举什么 ） 搜索顺序 （ 先枚举什么 ， 后枚举什么 ） 剪枝 (及早判断出不符合要求的情况 ） 例题： POJ1011 木棒问题  问题描述： 乔治拿来一组等长的棍子，将它们随机地裁断（截断后。