n皇后問題和羅馬尼亞問題實習(xí)報告

1、 人工智能課程實人工智能課程實 習(xí)報告習(xí)報告 題目：n 皇后問題和羅馬尼亞問題皇后問題和羅馬尼亞問題 班號： 191122 學(xué)號： 20121003553 姓名： 葉葉 超超 指導(dǎo)老師：趙曼趙曼 2014.11 目錄目錄 人工智能課程實習(xí)報告人工智能課程實習(xí)報告.1 目錄目錄.2 羅馬尼亞問題羅馬尼亞問題.4 一、問題描述一、問題描述.4 二、圖的數(shù)據(jù)結(jié)構(gòu)二、圖的數(shù)據(jù)結(jié)構(gòu).5 三、實現(xiàn)算法三、實現(xiàn)算法.5 1.寬度優(yōu)先 .5 1.1數(shù)據(jù)結(jié)構(gòu)：.5 1.2算法思想：.6 1.3運行結(jié)果：.6 2.深度優(yōu)先 .7 2.1數(shù)據(jù)結(jié)構(gòu)：.7 2.2算法思想：.7 2.3運行結(jié)果：.7 3.貪婪算法 .8

2、 3.1數(shù)據(jù)結(jié)構(gòu)：.8 3.2算法思想：.8 3.3運行結(jié)果：.8 4.a*算法.9 4.1數(shù)據(jù)結(jié)構(gòu)：.9 4.2算法思想：.9 4.3運行結(jié)果：.9 四、比較結(jié)論四、比較結(jié)論.9 n n 皇后問題皇后問題.11 一、問題描述一、問題描述：.11 二、數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu).11 三、實現(xiàn)算法三、實現(xiàn)算法.11 1、回溯法 .12 1.1數(shù)據(jù)結(jié)構(gòu)：.12 1.2算法思想：.12 1.3運行結(jié)果:.12 2、遺傳算法 .12 2.1數(shù)據(jù)結(jié)構(gòu)：.13 2.2算法思想：.13 2.3運行結(jié)果.13 3、csp 最小沖突法.13 3.1數(shù)據(jù)結(jié)構(gòu)：.13 3.2算法思想：.14 3.3運行結(jié)果:.14 四

3、、比較結(jié)論四、比較結(jié)論.14 總結(jié)總結(jié).15 附源代碼附源代碼.15 羅馬尼亞問題 .15 n 皇后問題.26 遞歸算法.27 遺傳算法.29 csp 最小沖突法.35 羅馬尼亞問題羅馬尼亞問題 一、問題描述一、問題描述 （1）羅馬尼亞問題：find bucharest starting at arad 分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和 a*算法求解“羅馬利亞度假 問題”。要求：分別用文件存儲地圖和啟發(fā)函數(shù)表，用生成節(jié)點數(shù)比較幾 種算法在問題求解時的效率，列表給出結(jié)果。 （2）附（羅馬尼亞地圖） （3） （3）各結(jié)點啟發(fā)值： 二、圖的數(shù)據(jù)結(jié)構(gòu)二、圖的數(shù)據(jù)結(jié)構(gòu) (1)節(jié)點信息： typede

4、f struct char cityname20;城市名 int value;啟發(fā)函數(shù)值 int cost;路徑花費 ver; ()地圖信息 typedef struct ver vmaxv;一維城市數(shù)組 int edgemaxvmaxv;二維邊數(shù)組 int numofedges; graph; （3）圖的操作函數(shù) void read_v(graph int rear; int front; int count; seqcquene; 隊列操作： void queueinitiate(seqcquene *q)； int queuenotempty(seqcquene q)； int queu

5、edelete(seqcquene *q,int *d)； int queueappend(seqcquene *q,int x)；先進先出（bfs） 記錄父親用于打印路徑 typedef struct int father; int me; way; 1.2 算法思想：算法思想： 從 arad 結(jié)點出發(fā)，判斷是否為目標結(jié)點，若否， 寬度優(yōu)先搜索系統(tǒng) 地 探尋與該結(jié)點相連 的結(jié)點，算法首先搜索和 arad 相距（深度）為 k 的所有頂點，然后再去搜索和 arad 相距為 k+l 的其他頂點 ，找出并存進待 擴展結(jié)點表，等待擴展，每次先判斷待擴展結(jié)點表是否為空，若否則從待擴 展結(jié)點表中取出一個結(jié)

6、點進行擴展，并將擴展后的結(jié)點存進該表，若是，則 返回失敗。該算法同時能生成一棵根為 arad 且包括所有可達頂點的寬度優(yōu) 先樹 1.3 運行結(jié)果：運行結(jié)果： 2.深度優(yōu)先深度優(yōu)先 2.1 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 堆棧 typedef struct int a100;記錄入棧城市序號 int top1;棧頂 int weight;最大路徑用于剪枝 stack; 2.2 算法思想：算法思想： 深度優(yōu)先搜索是一種每次都要達到被搜索結(jié)構(gòu)的葉結(jié)點的搜索方法 ，直到 不能再深入為止，然后返回到另一個結(jié)點，繼續(xù)對該結(jié)點進行深搜。當有目標 結(jié)點出現(xiàn)時，返回目標結(jié)點，搜索結(jié)束；否則，若待擴展結(jié)點表已空，且未找 到

7、目標結(jié)點，則返回失敗，停止搜索。 同樣，深度優(yōu)先搜索從 arad 結(jié)點出發(fā)，判斷是否為目標結(jié)點，若否，探尋 與該結(jié)點相連的結(jié)點，算法首先搜索一條分支上的所有頂點，然后再去搜索和 arad 的其它分支結(jié)點，找出并存進待擴展結(jié)點表，等待擴展，每次先判斷待擴 展結(jié)點表是否為空，若否，則從待擴展結(jié)點表中取出一個結(jié)點進行擴展，并將 擴展后的結(jié)點存進該表，若是，則返回失敗。該算法同時能生成一棵根為 arad 且包括所有可達頂點的深度優(yōu)先樹。 在深度優(yōu)先搜索中，我用到堆棧來存儲待擴展結(jié)點表。 2.3 運行結(jié)果：運行結(jié)果： 說明：深度優(yōu)先找到解生成的節(jié)點數(shù)為 12，路徑長度為 605，程序中增加回溯 和剪枝功

8、能，所以會繼續(xù)搜索優(yōu)于當前解的路徑，當生成 14 個節(jié)點時找到了最 優(yōu)解 418，但此時不能確定該解就是最優(yōu)解，因為還有路徑?jīng)]有遍歷，當生成 30 個節(jié)點時，所有路徑都已嘗試，確定最優(yōu)解為 418。 3.貪婪算法貪婪算法 3.1 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 隊列（bfs，貪婪，*公用） typedef struct int queuemaxsize; int rear; int front; int count; seqcquene; 隊列操作： void queueinitiate(seqcquene *q)； int queuenotempty(seqcquene q)； int queuede

9、lete(seqcquene *q,int *d)； int queueorderappend(seqcquene *q,int x,graph g)；越小優(yōu)先級越高 記錄父親用于打印路徑 typedef struct int father; int me; way; 3.2 算法思想：算法思想： 貪婪算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。貪婪 算法不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。貪 婪算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題他 能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。 在解決羅馬尼亞度假問題時，貪婪算法通過比較每個待

10、擴展結(jié)點的 h 值， 即啟發(fā)函數(shù)生成的到目標結(jié)點的啟發(fā)函數(shù)值，選取一個最小的，來確定當前要 擴展的結(jié)點，并將生成的結(jié)點放進 fringe 結(jié)點表。 在貪婪算法中，我用到隊列存儲待擴展結(jié)點表。 3.3 運行結(jié)果：運行結(jié)果： 4.a*算法算法 4.1 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 隊列（bfs，貪婪，*公用） typedef struct int queuemaxsize; int rear; int front; int count; seqcquene; 隊列操作： void queueinitiate(seqcquene *q)； int queuenotempty(seqcquene q)； in

11、t queuedelete(seqcquene *q,int *d)； intqueue_a_orderappend(seqcquene *q,int x,graph g)越小優(yōu)先級越高 4.2 算法思想：算法思想： a*算法用公式表示為： f(n)=g(n)+h(n), 其中 f(n) 是從初始點經(jīng)由結(jié)點 n 到 目標點的估價函數(shù)；g(n) 是在狀態(tài)空間中從初始節(jié)點到 n 節(jié)點的實際代價， h(n)是從 n 到目標節(jié)點最佳路徑的估計代價。 a*能找到最優(yōu)解的條件，關(guān)鍵在于估價函數(shù) h(n)的選?。蝗艄纼r值35 時，用回溯法已不能較好的解決 n 皇 后問題。 2、遺傳算法、遺傳算法 2.1 數(shù)

12、據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： int *arry =null; arry=new int *zhongqun;/種群 arryi=new int n+1;/個體 2.2 算法思想：算法思想： 遺傳算法（genetic algorithm）是模擬物進化論的自然選擇和遺傳學(xué)機理的 生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。 對于一個求函數(shù)最大值的優(yōu)化問題，首先初始化，包括種群的大小，編碼的方 案，遺傳的代數(shù)，變異的概率，等等；然后進行選擇操作；接著是將選擇的個 體進行交叉；然后再進行選擇，并將選擇的個體進行變異；最后就是更新最優(yōu) 值了。 大概分為：初始化，循環(huán)雜交、變異、選擇、檢測

13、解，終止計算。 2.3 運行結(jié)果運行結(jié)果 遺傳算法優(yōu)點是能很好的處理約束，能很好的跳出局部最優(yōu)，最終得到全 局最優(yōu)解，全局搜索能力強；缺點是收斂較慢，局部搜索能力較弱，運行時間 長，且容易受參數(shù)的影響。 3、csp 最小沖突法最小沖突法 3.1 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： structstruct dddd intint csp;/csp;/沖突數(shù)沖突數(shù) intint position;/position;/位置位置 ; dddd *arry;*arry; nqueen=newnqueen=new intn;/intn;/皇后矩陣皇后矩陣 arry=newarry=new ddn;/cspddn;/

14、csp 矩陣矩陣 3.2 算法思想：算法思想： 最小沖突法基本思想和爬山法相同，每次尋找使沖突值最小的狀態(tài)，直至找 到?jīng)_突值為 0 的情況、既滿足條件的 n 皇后擺放位置。 3.3 運行結(jié)果運行結(jié)果: 與爬山法一樣 csp 最小沖突法容易陷入局部最優(yōu)，86%的時間會卡??；但是 csp 最小沖突法較簡單，在皇后的個數(shù)較多時體現(xiàn)出來效率最高，處理多約束 大規(guī)模問題時往往不能得到較好的解。 四、比較結(jié)論 n t/ms 816 24 32 3550 64100200 回溯1111511027142469812865301 - - - - ga1140243931 - - 9103451819280 -

15、 - csp470 16 156 500 62512972266139898 回溯法在皇后數(shù)目較小的，很占優(yōu)勢，它的速度非常的快，但隨著皇后數(shù) 目的增加，回溯法顯得很不實用，在 n=35 時，用回溯法已不能較好的解決 n 皇 后問題。 遺傳算法優(yōu)點是能很好的處理約束，能很好的跳出局部最優(yōu)，最終得到全 局最優(yōu)解，全局搜索能力強；缺點是收斂較慢，局部搜索能力較弱，運行時間 中等，且容易受 n 值的影響。遺傳算法的運行時間在 n 很小時沒有回溯法快， 但是隨著 n 值的增加，遺產(chǎn)算法的優(yōu)點也就顯現(xiàn)出來，它能夠解決回溯法不能 解決的問題。 csp 最小沖突法是一種始終都比較快的算法，它的運行時間與皇后

16、是個數(shù)沒 有必然的聯(lián)系，而且在 n 很大時，它顯現(xiàn)出來運行時間短，效率高的優(yōu)勢，但 它的缺點是會出現(xiàn)山脊、高原，86%的時間會卡住。總的來說，csp 最小沖突法 較簡單，也比較快，在皇后的個數(shù)較多時體現(xiàn)出來效率最高，處理多約束大規(guī) 模問題時往往不能得到較好的解。 總的來說，回溯在 n 值很小時，效率很高，但其求解范圍很小，超過 35 基 本就解不出來，遺傳算法求解范圍適中。在 n 值很大(100)時，前兩者都不能 再解決，此時，csp 最小沖突法的效率最高，且與 n 值沒有必然的聯(lián)系。 總結(jié)總結(jié) 通過此次課程實習(xí)不僅大大加深了我對幾種經(jīng)典搜索算法的理解，而且?guī)?助我很好的復(fù)習(xí)了隊列、堆棧、圖、

17、文件讀寫這幾部分的內(nèi)容，使我對幾種基 本的數(shù)據(jù)結(jié)構(gòu)類型的運用更加熟練。在解決這些問題的過程中我不但很好的鞏 固了數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識，而且提高了編程及程序調(diào)試能力，增強了自己編程 的信心。 總之，在這次課程實習(xí)過程中我是實實在在學(xué)到了一些課堂上學(xué)不到的東西， 同時也提高了實踐能力。同時在這個過程中也暴露了自己的不少問題，在今后 的學(xué)習(xí)過程成也會更加有針對性。最后還要感謝老師的悉心指導(dǎo)，解答我編程 過程中的疑問、指出我程序中的不足，及提出可行的解決方法，讓我的程序的 功能更加完善。 附源代碼附源代碼 羅馬尼亞問題羅馬尼亞問題 /*羅馬尼亞問題* /*代碼清單： graph.h stack.h qu

18、eue.h main.cpp*/ /*graph.h* #include #include #include #include #define maxv 20 typedef struct char cityname20; int value; int cost; ver; typedef struct ver vmaxv; int edgemaxvmaxv; int numofedges; graph; void read_v(graph char ch20; fstream infile(heuristic_value.txt,ios:in); i=0; while(infilech g.

19、vi.cost=0; strcpy(g.vi.cityname,ch); i+; void read_edge(graph fstream infile(map.txt,ios:in); i=0; while(infilevalu) g.edgei/20i%20=valu; /coutg.edgei/20i%20; i+; int getfirstv(graph g,int v) int col; if(v=20) return -1; for(col=0;col0 return -1; int getnextv(graph g,int v1,int v2) int col; if(v1=20

20、|v2=20) return -1; for(col=v2+1;col0 return -1; /*stack.h* #include #includegraph.h typedef struct int a100; int top1; int weight; stack; bool stacknotfull(stack *st) if(st-top1top10) return true; else return false; void initiatestack(stack *st) st -top1=0; st-weight=0; void stackpop(stack *st,graph

21、 g) int x; if( staknotempty(st) st-top1-; x=st-ast-top1; if(st-top10 ) st-weight=st-weight-g.edgest-ast-top1-1x; else cout棧已空！ast-top1=x; if(st-top10 ) st-weight=st-weight+g.edgest-ast-top1-1st-ast-top1; st-top1+; else cout棧已滿！endl; void printstack(stack *st,graph g) int x; x=0; while(xtop1) cout ax

22、.cityname ; x+; /cout路徑長度為：weightendl; coutrear=0; q-front=0; q-count=0; int queuenotempty(seqcquene q) if(q.count!=0)return 1; else return 0; int queueappend(seqcquene *q,int x) if(q-count0 q-rear =(q-rear +1)%maxsize; q-count +; return 1; int queuedelete(seqcquene *q,int *d) if(q-count =0) cout隊列已

23、空queue q-front; q-front=(q-front+1)%maxsize; q-count-; return 1; int queueorderappend(seqcquene *q,int x,graph g) if(q-count0 q-rear =(q-rear +1)%maxsize; q-count +; return 1; else if( g.vx.valuequeueq-front.value)/隊頭插入 q-queueq-front-1=x; q-front =(q-front-1+maxsize)%maxsize; q-count +; return 1; e

24、lse /排序找位置插入 int position=q-front; while(g.vx.valueg.vq-queueposition.value)position+; for(int i=q-front;iqueue(i-1+maxsize)%maxsize=q-queuei%maxsize; q-queue(i-1+maxsize)%maxsize=x; q-front =(q-front-1+maxsize)%maxsize; q-count +; /a* int queue_a_orderappend(seqcquene *q,int x,graph g) if(q-count0

25、q-rear =(q-rear +1)%maxsize; q-count +; return 1; else if( g.vx.value+g.vx.costqueueq- front.value+g.vq-queueq-front.cost)/隊頭插入 q-queueq-front-1=x; q-front =(q-front-1+maxsize)%maxsize; q-count +; return 1; else /排序找位置插入 int position=q-front; while(g.vx.value+g.vx.cost g.vq- queueposition%maxsize.va

26、lue+g.vq-queueposition%maxsize.cost) position+; for(int i=q-front;iqueue(i-1+maxsize)%maxsize=q-queuei%maxsize; q-queue(i-1+maxsize)%maxsize=x; q-front =(q-front-1+maxsize)%maxsize; q-count +; /*main.cpp * #include queue.h typedef struct int father; int me; way; way *b=new way100; int i=0; int end=2

27、; int count=0; int visitedcity20; void visit(int v, int u) bi.father=u; bi.me=v; i=i+1; void printbw(graph g,way *b,int end,int start) int bway=0; cout遍歷路徑為（反序）：; coutg.vend.cityname ; while(1) for(int j=0;ji;j+) if(bj.me=end) coutg.vbj.father.cityname ; bway+=g.edgebj.mebj.father; end=bj.father; if

28、(end=start)break; coutendl; cout路徑長度為：bwayendl生成節(jié)點數(shù)為：countweight=maxweight) w=-1; if(v=end cout路徑長度為：weightendl生成節(jié)點數(shù)為： countendl; else w=getfirstv(g,v); while(w!=-1) if(!visitedw) depthfsearch(g,w,visited,st); w=getnextv(g,v,w); visitedv=0; stackpop(st, g); void greedy(graph g,int v); void a(graph *

29、g,int v); void main() graph g; graph * p= read_v(g); read_edge(g); / cout寬度優(yōu)先：endl ; broadfsearch(g,0); / cout深度優(yōu)先endl; int visited20=0; count=0; stack *st; st=new stack; initiatestack( st); depthfsearch( g, 0,visited,st); cout確定深度優(yōu)先找到最優(yōu)路徑為：maxweightendl; cout確定深度優(yōu)先找到最優(yōu)解生成節(jié)點數(shù)為：countendl; / cout貪婪算法：

30、endl ; greedy( g,0);printbw( g, b,end,0); / couta 星算法：endl ; a(p, 0); / /貪婪算法 void greedy(graph g,int v) i=0;count=0; int visited20=0; int u,w; seqcquene queue; visitedv=1; if(v=end)return; queueinitiate( queueorderappend( count+; while(queuenotempty(queue) queuedelete( if(u=end) count+; return; w=g

31、etfirstv(g,u); while(w!=-1) if(!visitedw) visit( w,u); if(w=end)count+;return; queueorderappend(count+; w=getnextv(g,u,w); /a*算法 void a(graph *g,int v) i=0;count=0; int u,w; seqcquene queue; seqcquene *q= if(v=end)return; queueinitiate( queue_a_orderappend(count+; while(queuenotempty(queue) queuedel

32、ete( if(u=end) cout路徑長度為：vu.cost+ g-vu.valueendl生成節(jié) 點數(shù)為：countendl; /coutvu.cost+ g-vu.valuecount+vw.cost=g-vu.cost+g-edgewu; queue_a_orderappend(count+; w=getnextv(*g,u,w); n 皇后問題皇后問題 /*n 皇后問題* 遞歸算法遞歸算法 /*遞歸算法 #include #include #include #include #include using namespace std; bool check(int rowcurren

33、t,int * /判斷函數(shù) voidprint(ofstream /打印函數(shù) void solve(int rowcurrent,int * /判斷函數(shù)，凡是橫豎有沖突，或是斜線上有沖突，返回 false bool check(int rowcurrent,int * while(i rowcurrent) if(nqueeni=nqueenrowcurrent| (abs(nqueeni- nqueenrowcurrent) = abs(i-rowcurrent) ) return false; i+; return true; /將所有可能出現(xiàn)的結(jié)果輸出文本文檔 void print(of

34、stream for (int i = 0;i n;i+) for(int j = 0 ; j n; j+) os(nqueeni=j?1:0); ossetw(2); osn; /核心函數(shù)。遞歸解決 n 皇后問題，觸底則進行打印 void solve(int rowcurrent,int * count+; return; for(int i = 0; i n; i+) nqueenrowcurrent = i; /row 行 i 列試一試 if(check(rowcurrent,nqueen) solve(rowcurrent+1,nqueen,n,count,os); /移向下一行 in

35、t main() clock_t start, finish; while(1) ofstream os; int n; /問題規(guī)模 os.open(result.txt,ios_base:app); if(!os.is_open() /判斷文件是否存在。 cerr找不到文件！endl; int count = 0; /解的計數(shù) cout請輸入問題的規(guī)模 nn; if(n4) cerr問題規(guī)模必須大于 4endl; return 0; int *nqueen = new intn; start = clock(); solve(0,nqueen,n,count,os); finish = cl

36、ock(); osn皇后求解時間為：countfinish-startn; coutn皇后求解時間為：countfinish-startendl; delete nqueen; os.close(); return 0; 遺傳算法遺傳算法 /*遺傳算法* #include #include #include #include #include #include #include using namespace std; #define maxgeneration 10000000 #define zhongqun 50 #define p0 0.1 int maxtime=2000*3600;

37、/2h clock_t timestart,timenow ; int *arry =null; int *temp; int p; int generation; void initial(int genes ,int *p)/ genes lenth of gene;p zhongqun zhizheng; int i,j,k,t,sign,mod=genes; int *temp=new intgenes; for( i=0;igenes;i+) tempi=i; for(i=0;izhongqun;i+,mod=genes) pigenes=0; /沖突=0; for(j=0;jgen

38、es;j+) sign=rand()%mod; pij=tempsign; t=tempmod-1; tempmod-1=tempsign; tempsign=t; mod-; if(mod=1) pi+j=temp0; /計算沖突個數(shù) for(j=0;jgenes-1;j+) for(k=j+1;kgenes;k+) if(pij=pik|abs(pij-pik)=abs(j-k) pigenes+; delete temp; int position(int *tmp,int c) int j; for(j=0;j5;j+) if(*(tmp+j)=c)break; return(j);

39、void invert(int pos_start,int pos_end,int xcity) int j,k,t; if(pos_startpos_end) j=pos_start+1; k=pos_end; for(;j=k;j+,k-) t=tempj; tempj=tempk; tempk=t; else if(xcity-1-pos_start=pos_end+1) j=pos_end;k=pos_start+1; for(;kxcity;j-,k+) t=tempj;tempj=tempk;tempk=t; k=0; for(;k=0;j-,k+) t=tempj;tempj=t

40、empk;tempk=t; j=xcity-1; for(;k=j;k+,j-) t=tempj;tempj=tempk; tempk=t; /計算沖突個數(shù) tempxcity=0; for(j=0;jxcity-1;j+) for(k=j+1;kxcity;k+) if(tempj=tempk|abs(tempj-tempk)=abs(j-k) tempxcity+; void cross(int genes) int i,j,k,ind,mod=zhongqun,temp1; int*tmp; temp=new intgenes+1; for(i=0;izhongqun;i+) for(j

41、=0;jtempgenes) for(j=0;jgenes+1;j+) arryij=tempj; void selfcross(int genes) int i,j,k,ind,mod=zhongqun,temp1; int*tmp; temp=new intgenes+1; for(i=0;izhongqun;i+) for(j=0;jtempgenes) for(j=0;jgenes+1;j+) arryij=tempj; int mutation(int genes) int i,j,k,l,temp; for(i=0;izhongqun;i+) if(rand()/32768.0)p

42、0) j=rand()%genes; k=rand()%genes; if(j!=k) temp=arryij; arryij=arryik; arryik=temp; arryigenes=0; /計算沖突個數(shù) for(j=0;jgenes-1;j+) for(k=j+1;kgenes;k+) if(arryij=arryik|abs(arryij-arryik)=abs(j-k) arryigenes+; return 0; bool check(int genes) for(int i=0;izhongqun;i+) if(arryigenes=0) p=i; return true;

43、return false; int loop(int genes) generation=0; for(generation=0;generation=maxtime) return 0; return 0; void main() int n,i; coutga 算法endl; ofstream os; /osendl; while(1) do coutn; if(n=3) cout輸入錯誤！請重新輸入endl; while(n100); timestart=clock(); os.open(result.txt,ios_base:app); if(!os.is_open() /判斷文件是否

44、存在。 cerr找不到文件！endl; osn皇后n; arry=new int *zhongqun; for(i=0;izhongqun;i+ ) arryi=new int n+1; initial(n,arry); if(loop(n) timenow=clock(); coutn皇后求解時間為：; couttimenow-timestart ; coutendl; for ( i = 0;i n;i+) for(int j = 0 ; j n; j+) os(arrypi=j?1:0); ossetw(2); osn; osn皇后求解時間為：; ostimenow-timestart

45、; ; osgeneration:generation; ; ostime:timenow-timestart; endl; else coutfailed; osfailed! ; osgeneration:generation; ; ostime:timenow-timestart; endl; os.close(); int j,k; for(j=0;jn-1;j+) for(k=j+1;kn;k+) if(arrypj=arrypk|abs(arrypj-arrypk)=abs(j-k) coutno!; delete arry; csp 最小沖突法最小沖突法 /*csp 最小沖突法

46、#include #include #include #include #include #include #include using namespace std; #define maxstep 2000 clock_t timestart,timenow ; struct dd int csp; int position; ; dd *arry; int *nqueen;/ 皇后位置 int q=0,step=0;/初始沖突數(shù) void initial(int genes ,int *p)/ 初始化皇后位置/計算初始沖突個數(shù) int i,j,k,t,sign,mod=genes; int *temp=new intgenes; for( i=0;igenes;i+) tempi=i; for(j=0;jgenes;j+) sign=rand()%mod; pj=tempsign; t=tempmod-1; tempmod-1=tempsign; tempsign=t; mod-; if(mod=1) p+j=temp0; delete temp; q=0; /沖突=0; /計算初始沖突個數(shù) for(j=0;jgenes-1;j+) for(k=j+1;kgenes;k+) if(n