【正文】 count = nowStategetTotalCount()。 for (int capticy = count。 capticy) { for (int i = 0。 ++i) { Boat boat(i, capticy i)。boat)) return true。 capticy = Boat::c。 i = capticy。 if (move(nowState, amp。 } } } } print(NULL)。}//實施一步?jīng)Q策，將得到的新狀態(tài)添加到列表，返回是否達到目標狀態(tài)bool RiverCrossing::move(State *nowState, Boat *boat){ //獲得下一個狀態(tài) State *destState。//船離開此岸 } else if (nowStateiBoatAtSide == 0) { destState = new State(*nowState + *boat)。 print(destState)。//找到結果 } else if (destStateisSafe()) {//檢查是否安全 if (!findInList(openList, *destState) amp。 !findInList(closeList, *destState)) {//檢查是否在表中 //添加沒出現(xiàn)過的狀態(tài)節(jié)點到open表 (destState)。 } } } delete destState。}//檢查給定狀態(tài)是否存在于列表中State* RiverCrossing::findInList(listState* amp。state){ for (listState*::iterator ite = ()。 ++ite) { if (**ite == state) return *ite。}//根據(jù)達到的目標狀態(tài)，回溯打印出求解過程void RiverCrossing::print(State *endState){ cout================================================endl。 } else { coutSearch successed!endl。 State *pState = endState。//用棧將鏈表逆序，以便輸出 while (pState) { (pState)。 } int count = 0。 ()。 if (() 0) cout 。 } coutendl。 } cout================================================endl。二、問題描述給定九宮格的初始狀態(tài)，要求在有限步的操作內(nèi)，使其轉化為目標狀態(tài)，且所得到的解是代價最小解(即移動的步數(shù)最少)。五、實驗條件每人一臺計算機獨立完成實驗。//主函數(shù)void main(){ NineGrid::ShowInfo()。 coutPlease input the initial state: (ex:134706582)endl。 coutPlease input the target state: (ex:123804765)endl。 NineGrid nineGrid(start, end)。 system(pause)。define SPACE 39。define AT(s, x, y) (s)[(x) * 3 + (y)]enum Move { UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3}。//指向目標狀態(tài)，用于評價h的值 string grid。//空格所在位置 int moves。//價值 State *pPrevious。grid, State *pPrevious = NULL)。//獲取逆序數(shù) void evaluate()。//檢查是否可以移動 State takeMove(Move move)。state) { return grid == 。//九宮重排問題class NineGrid{private: vectorState* openList, closeList。 clock_t startTime。//比較逆序數(shù)奇偶性是否相同 bool takeMove(State *nowState, Move move)。listToCheck, State amp。//檢查某狀態(tài)節(jié)點是否在列表中 void print(State *endState)。public: static void ShowInfo()。start, string amp。 bool solve()。include include iostreaminclude stackinclude algorithmusing namespace std。/*=======================Methods for class State=======================*///構造函數(shù)State::State(string amp。 thispPrevious = pPrevious。 else thismoves = 0。 evaluate()。 i 3。 j 3。 y = j。 } } }}bool State::check(Move move){ switch (move) { case UP: if (x 1 0) return false。 case DOWN: if (x + 1 = 3) return false。 case LEFT: if (y 1 0) return false。 case RIGHT: if (y + 1 = 3) return false。 } return true。 switch (move) { case UP: destX = x 1。 break。 destY = y。 case LEFT: destX = x。 break。 destY = y + 1。 } string tGrid = grid。 AT(tGrid, destX, destY) = AT(tGrid, x, y)。 return State(tGrid, this)。 int g = moves, h = 0。 i 3。 j 3。 if(AT(grid, i, j) == SPACE) continue。 ii 3。 jj 3。 } } } } } thisvalue = g + h。//　　所有棋子的逆序總數(shù)為逆序數(shù)。 for (int i = 0。 ++i) { if(grid[i] == SPACE) continue。 j i。 if (grid[i] grid[j]) ++count。}/*=====================Methods for class NineGrid=====================*///顯示信息void NineGrid::ShowInfo(){ cout************************************************endl。 cout by 1040501211 陳嘉生 endl。}//構造函數(shù)NineGrid::NineGrid(string amp。dest) : startState(start), endState(dest){ State::pEndState = amp。 ()。}//解決問題bo