實(shí)驗(yàn)報(bào)告8-excel_20xx(四)-資料下載頁(yè)
2025-10-15 23:42本頁(yè)面
【正文】 的。② BACKTRACK算法對(duì)重復(fù)出現(xiàn)的狀態(tài)沒(méi)有判斷，所以可能造成出現(xiàn)死循環(huán)。③ 沒(méi)有對(duì)搜索深度加以限制，可能造成搜索代價(jià)太大。三、算法描述回溯法——在約束條件下先序遍歷，并在遍歷過(guò)程中剪去那些不滿足條件的分支。使用回溯算法求解的問(wèn)題特征，求解問(wèn)題要分為若干步，且每一步都有幾種可能的選擇，而且往往在某個(gè)選擇不成功時(shí)需要回頭再試另外一種選擇，如果到達(dá)求解目標(biāo)則每一步的選擇構(gòu)成了問(wèn)題的解，如果回頭到第一步且沒(méi)有新的選擇則問(wèn)題求解失敗。在回溯策略中，也可以通過(guò)引入一些與問(wèn)題相關(guān)的信息來(lái)加快搜索解的速度。對(duì)于皇后問(wèn)題來(lái)說(shuō)，由于每一行、每一列和每一個(gè)對(duì)角線，都只能放一個(gè)皇后，當(dāng)一個(gè)皇后放到棋盤(pán)上后，不管它放在棋盤(pán)的什么位置，它所影響的行和列方向上的棋盤(pán)位置是固定的，因此在行、列方面沒(méi)有什么信息可以利用。但在不同的位置，在對(duì)角線方向所影響的棋盤(pán)位置數(shù)則是不同的?？梢韵胂螅绻岩粋€(gè)皇后放在棋盤(pán)的某個(gè)位置后，它所影響的棋盤(pán)位置數(shù)少，那么給以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。四、算法流程圖五、源程序include define N 4 char board[N][N]。int t。int col[N]。//存儲(chǔ)第i行對(duì)應(yīng)的列的值，這樣的(i,j)值滿足當(dāng)前棋盤(pán)上的皇后不能互相攻擊。int safetyPlace(int x,int y)//(x,y)位置是否安全 {int i,j。for(i=0。i{j=col[i]。if(x==i||y==j)return 0。if(xy==ij||x+y==i+j)//判斷左右對(duì)角線return 0。}return 1。} void get_position(int i)//處在第i行時(shí)狀態(tài) {int w,j。char a[1]={3}。if(i==N)//輸出棋盤(pán){for(w=0。w{for(j=0。j{if(board[w][j]==001)printf(“%c ”,board[w][j])。else{printf(“%c”,a[0])。printf(“%c ”,board[w][j])。}}printf(“n”)。}printf(“n”)。printf(“n”)。t++。}else{int u。for(u=0。u{if(safetyPlace(i,u)==1){col[i]=u。//記錄下第i行可行的列的位置board[i][u]=001。//放置皇后get_position(i+1)。//轉(zhuǎn)換到下一個(gè)狀態(tài)，即下一行col[i]=0。//回溯到當(dāng)前狀態(tài)，重置列和棋盤(pán)的值board[i][u]=0。} }} } main(){printf(“%c是皇后!nn”,001)。get_position(0)。printf(“一共有%d種方法！n”,t)。}六、結(jié)果截圖七、總結(jié)——心得體會(huì)通過(guò)對(duì)四皇后問(wèn)題的編程學(xué)習(xí)，讓我對(duì)搜索策略更深層次的理解，尤其能比較熟練掌握回溯策略——首先將規(guī)則給出一個(gè)固定的排序，在搜索時(shí)，對(duì)當(dāng)前狀態(tài)（搜索開(kāi)始時(shí)，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測(cè)每一條規(guī)則，在當(dāng)前狀態(tài)未使用過(guò)的規(guī)則中找到第一條可應(yīng)用規(guī)則，應(yīng)用于當(dāng)前狀態(tài)，得到的新?tīng)顟B(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索。如果當(dāng)前狀態(tài)無(wú)規(guī)則可用，或者所有規(guī)則已經(jīng)被試探過(guò)仍未找到問(wèn)題的解，則將當(dāng)前狀態(tài)的前一個(gè)狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當(dāng)前狀態(tài)。重復(fù)以上搜索，直到找到問(wèn)題的解，或者試探了所有可能后仍找不到問(wèn)題的解為止。同時(shí)，在整個(gè)編程學(xué)習(xí)過(guò)程中，使得我對(duì)人工智能感到越來(lái)越多的趣味性（例如四皇后問(wèn)題上升到n皇后如何求解），更引起我對(duì)學(xué)習(xí)人工智能這門(mén)課程的積極性。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1