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