人工智能实验报告

}

///////////////////////////

// the two states exchange

void Eight::move(state des, state src) { for(int row = 0; row

/////////////////////////

// extend other states

void Eight::genNewState(state oldState) { int row,col; int temp;//保存状态转换数组中的值 state newState; findZeroPostion(row,col,oldState);//find zero position if(row +1 < N)//0向下移动 { //move(newState, oldState); newState = oldState; newState.depth = oldState.depth +1; newState.parent = oldState.nID; newState.nID = nAutoIncrease++;//对ID自动编号 //switch temp = newState.arrState[row][col]; newState.arrState[row][col] = newState.arrState[row+1][col]; newState.arrState[row+1][col] = temp; newState.value = w(newState.arrState) + newState.depth; //newState.value = f(newState); //push newState to open genToOpen(newState); } if(row - 1 > -1)//0向上移动 {

}

newState = oldState;

newState.depth = oldState.depth +1; newState.parent = oldState.nID;

newState.nID = nAutoIncrease++;//对ID自动编号

//switch

temp = newState.arrState[row][col];

newState.arrState[row][col] = newState.arrState[row-1][col]; newState.arrState[row-1][col] = temp;

newState.value = w(newState.arrState) + newState.depth; //newState.value = f(newState); //push newState to open genToOpen(newState);

if(col +1 < N)//0向右移动 { newState = oldState; newState.depth = oldState.depth +1; newState.parent = oldState.nID; newState.nID = nAutoIncrease++;//对ID自动编号 }

//switch

temp = newState.arrState[row][col];

newState.arrState[row][col] = newState.arrState[row][col+1]; newState.arrState[row][col+1] = temp;

newState.value = w(newState.arrState) + newState.depth; //newState.value = f(newState); //push newState to open genToOpen(newState);

if(col -1 > -1)//0向左移动 { newState = oldState; newState.depth = oldState.depth +1; newState.parent = oldState.nID; newState.nID = nAutoIncrease++;//对ID自动编号 //switch temp = newState.arrState[row][col]; newState.arrState[row][col] = newState.arrState[row][col-1]; newState.arrState[row][col-1] = temp;

newState.value = w(newState.arrState) + newState.depth; //newState.value = f(newState); //push newState to open genToOpen(newState); } }

/////////////////////////////////////

//把open表中已访问的state放到closed表中 void Eight::moveToClosed(state s) { int i = ++closedIndex; closed[i] = s; //delete from open table for(int j = 0;j < openIndex-1; j++) open[j]=open[j+1]; //open length-1 openIndex--; }

/////////////////////////////////////

//把扩展的状态放入open表中 void Eight::genToOpen(state s) { if(IsInOpen(s)) { //show(s); //cout<<\该状态已存在open表中！\ nAutoIncrease--; return; } if(IsInClosed(s)) { //show(s); //cout<<\该状态已存在closed表中！\ nAutoIncrease--; return; } int i = ++openIndex; open[i] = s;

open[i].depth = s.depth; open[i].parent = s.parent; open[i].value = s.value; }

////////////////////////////

// current state compare to goal state bool Eight::compare(state s) { for(int i=0; i

////////////////////////////

// Is current state in closed table bool Eight::IsInClosed(state s) { for(int k = 0; k <= closedIndex; k++) { if(closed[k] == s) return true; } return false; }

////////////////////////////

// Is current state in open table bool Eight::IsInOpen(state s) { for(int k = 0; k <= openIndex; k++) { if(open[k] == s) return true; } return false; }

void Eight::heuristicSearch() {