1、人工智能一一四皇后問題一、問題描述四皇后問題一個(gè)4X4國際象棋盤，依次放入四個(gè)皇后，條件：每行、每列及對(duì)角線上只 允許出現(xiàn)一枚棋子。圖A圖AN圖B設(shè)：DATA設(shè)：DATA二L (表)xGL其中：i j表示棋子所在行列T棋盤上可放入的棋子數(shù)為04 .L表中的元素?cái)?shù)為04個(gè)，即 43 如：24表示第二行第四列有一枚棋子 個(gè)Leng th L = 0 4 ,如圖A 12, 24, 31,定義規(guī)則：if 1W i 4 andLeng th DATA = i 1then APPEND(DATA( ij )1 j 4對(duì)于任一行i ,1 j 4表明每行有四條規(guī)則。比如第一行：R11, R12, R13, R

2、14棋盤中共有四行，所以共有16條規(guī)則。即: R11, R12, R13, R14R21, R22, R23, R24R31, R32, R33, R34R41, R42, R43, R4416條規(guī)則中，哪些是當(dāng)前可用規(guī)則，取決于DATA的長度，即：DATA中的元素 個(gè)數(shù)。換言之，每次只能將一個(gè)棋子放在當(dāng)前行的下一行。二、回溯法搜索策略圖(41) (42) (43) (44)(41) (42) (43)四皇后問題回溯算法捜索圖討論：上述算法產(chǎn)生22次回溯，原因在于規(guī)則自然順序排列，沒考慮任何智能因素。 改進(jìn)算法定義對(duì)角線函數(shù)：diag(i,j)：過ij點(diǎn)最長的對(duì)角線長度值。規(guī)定：如果：diag

3、(i,k) W diag(i,j)則規(guī)則排列次序?yàn)椋篟ik, Rij 同一行四條規(guī)則中，對(duì)角線函數(shù)值小的排在前面如果:diag(i,k) = diag(i,j)則規(guī)則排列次序?yàn)椋篟ij , Rik j V k 對(duì)角線長度相等的規(guī)則按照字母排列順序排序按照對(duì)角線長度定義規(guī)則的排列次序?yàn)?；Rm Re Rm RliRq Rg(24)U31少)(43)改進(jìn)右的索圖討論：利用局部知識(shí)排列規(guī)則是有效的。BACKTRACK算法對(duì)重復(fù)出現(xiàn)的狀態(tài)沒有判斷，所以可能造成出現(xiàn)死循環(huán)。沒有對(duì)搜索深度加以限制，可能造成搜索代價(jià)太大。三、算法描述回溯法一一在約束條件下先序遍歷，并在遍歷過程中剪去那些不滿足條件的 分支。使

4、用回溯算法求解的問題特征，求解問題要分為若干步，且每一步都有幾種 可能的選擇，而且往往在某個(gè)選擇不成功時(shí)需要回頭再試另外一種選擇，如果到 達(dá)求解目標(biāo)則每一步的選擇構(gòu)成了問題的解，如果回頭到第一步且沒有新的選擇 則問題求解失敗。在回溯策略中，也可以通過引入一些與問題相關(guān)的信息來加快搜索解的速 度。對(duì)于皇后問題來說，由于每一行、每一列和每一個(gè)對(duì)角線，都只能放一個(gè)皇 后，當(dāng)一個(gè)皇后放到棋盤上后，不管它放在棋盤的什么位置，它所影響的行和列 方向上的棋盤位置是固定的，因此在行、列方面沒有什么信息可以利用。但在不 同的位置，在對(duì)角線方向所影響的棋盤位置數(shù)則是不同的。可以想象，如果把一 個(gè)皇后放在棋盤的某個(gè)

5、位置后，它所影響的棋盤位置數(shù)少，那么給以后放皇后留 下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也 小。四、算法流程圖五、源程序#include #define N 4 char boardNN;int t;int colN;存儲(chǔ)第i行對(duì)應(yīng)的列的值，這樣的(i,j)值滿足當(dāng)前棋盤上的皇后不能互相攻擊。int safetyPlace(int x,int y) (x,y)位置是否安全int i,j; for(i=0;ix;i+)j=coli; if(x=i|y=j) return 0;if(x-y=i-j|x+y=i+j)/判斷左右對(duì)角線return 0;return 1;

6、void get_position(int i)處在第i 行時(shí)狀態(tài)int w,j;char a1=3;if(i=N)/輸出棋盤for (w=0;wN;w+)for (j=0;jN;j+)if(boardwj=001) printf(%c ,boardwj);else printf(%c,a0);printf(%c ,boardwj); printf(n);printf(n);n);printf(n);t+;else int u;for (u=0;uvN;u+)記錄下第i行可行的列的位置放置皇后轉(zhuǎn)換到下一個(gè)狀態(tài)，即下一行回溯到當(dāng)前狀態(tài)，重置列和棋盤的值 記錄下第i行可行的列的位置放置皇后轉(zhuǎn)換到下

7、一個(gè)狀態(tài)，即下一行回溯到當(dāng)前狀態(tài)，重置列和棋盤的值 coli=u; boardiu=001; get_position(i+1);coli=0; boardiu=0;main()printf(%c 是皇后!nn,001);get_position(0);printf(一共有小種方法！ n,t);六、結(jié)果截圖I C:J MSOFTCYti Ysnbi nwwteimp.exe 魄皇后?目甲甲目一共有殳種方袪!七、總結(jié)心得體會(huì)通過對(duì)四皇后問題的編程學(xué)習(xí)，讓我對(duì)搜索策略更深層次的理解，尤其能比 較熟練掌握回溯策略首先將規(guī)則給出一個(gè)固定的排序，在搜索時(shí)，對(duì)當(dāng)前狀 態(tài)（搜索開始時(shí)，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測(cè)每一條規(guī)則，在當(dāng)前狀態(tài)未使 用過的規(guī)則中找到第一條可應(yīng)用規(guī)則，應(yīng)用于當(dāng)前狀態(tài)，得到的新狀態(tài)重新設(shè)置 為當(dāng)前狀態(tài)，并重復(fù)以上搜索。如果當(dāng)前狀態(tài)無規(guī)則可用，或者所有規(guī)則已經(jīng)被 試探過仍未找到問題的解，則將當(dāng)前狀態(tài)的前一個(gè)狀態(tài)（即直接生成該狀態(tài)的狀 態(tài)）設(shè)置為當(dāng)