人工智能實習報告

1、精選優(yōu)質文檔-傾情為你奉上人工智能實習報告第一部分 羅馬尼亞問題（1）問題描述：Find Bucharest starting at Arad分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和A*算法求解“羅馬利亞度假問題”。要求：分別用文件存儲地圖和啟發(fā)函數(shù)表，用生成節(jié)點數(shù)比較幾種算法在問題求解時的效率，列表給出結果。羅馬尼亞地圖如下：各節(jié)點啟發(fā)函數(shù)值如下：（2）數(shù)據(jù)結構：邏輯結構：采用數(shù)組完成，并配套設置相應標志位。存儲結構：啟發(fā)函數(shù)值及其對應地名采用結構體數(shù)組place20存儲，從文件中讀入。結構體聲明如下：typedef structchar name20;/存儲地名，數(shù)組下標表示地名標號int q

2、f;/存儲相應啟發(fā)函數(shù)值路徑采用二維數(shù)組data2020存儲，從文件中讀入：（3）算法思想：寬度優(yōu)先(BFS)：從初始結點出發(fā)，判斷是否為目標結點。若否，寬度優(yōu)先搜索與該結點相連接的結點并存進待擴展結點表needvisit等待擴展。當一個結點完全擴展（即與其所有相連的結點都已進入待擴展表或已擴展表），記錄下此時結點的數(shù)值并立出一標志位，以等待最后輸入時的判斷。判斷待擴展結點表是否為空，若否則從待擴展結點表表首中取出一個結點進行擴展，并將擴展后的結點存進visited。直到搜索到目標結點。最后輸出結果result。訪問visited計算出生成結點數(shù)量n_num并輸出。深度優(yōu)先（DFS）：大致同寬

3、度優(yōu)先算法，數(shù)據(jù)結構仍然保持不變，但采用搜索策略時優(yōu)先進行深度探索，即從初始結點出發(fā)，選擇一與其相連且未在visited中的結點（即此節(jié)點未被訪問過）。不同的是對于一個結點存入已訪問的判斷，深度優(yōu)先采取的是判斷該結點是否有未被訪問的后繼結點，以及該后繼結點又是否有未擴展的后繼結點，以此類推，最后找到目標結點。最后輸出結果result。訪問visited計算出生成結點數(shù)量n_num并輸出。貪婪算法(Greedy)：貪婪算法在對問題求解時，總是選擇局部最優(yōu)，逐步累加最終形成問題的相對最優(yōu)解（而非絕對）。從初始結點出發(fā)后，進行比較，計算出與其相連的所有結點中，所需移動消耗最少的結點。將初始結點存入v

4、isited中，該結點存入needvisit中。然后，重新以該結點為初始結點，再進行計算并移動，最終移動至目標結點。當不可移動時（即與其相連的所有結點都已訪問過），則退后一步，在此基礎上再選擇移動消耗最少的結點。最終一定可以到達目標結點。A * 算法：A*算法用公式表示為：f(n)=g(n)+h(n), 其中f(n) 是從初始點經(jīng)由結點n到目標點的估價函數(shù)；g(n) 是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價， h(n)是從n到目標節(jié)點最佳路徑的估計代價。A*算法大致也同貪婪算法，只是對于結點的選擇依據(jù)不同。（4） 運行結果：寬度優(yōu)先(BFS)：深度優(yōu)先（DFS）：貪婪算法(Greedy)：A

5、 * 算法：（5）比較結論：寬度優(yōu)先深度優(yōu)先貪婪算法A*算法生成結點數(shù)目111275各算法搜索路徑依次如下： 經(jīng)過比較，顯然，A*算法與貪婪算法生成的結點數(shù)目最少，效率最高。深度優(yōu)先生成的結點數(shù)目最多，效率最低，但這主要是因為程序中的搜索次序由對應結點序號決定，而恰好首選的結點又不是正確的結點才導致了這樣的結果。通常來講，一般寬度優(yōu)先的效率最低。從運行出的搜索路徑來看寬度優(yōu)先、深度優(yōu)先和貪婪算法搜索找到的也都不一定是最優(yōu)解，只有A*算法具有完備性且始終找到的都是最優(yōu)解。即使寬度優(yōu)先一定可以找到最優(yōu)解，但往往它找到的第一個并非是最優(yōu)的（本例中輸出的就并不是最優(yōu)的）。在最壞的情況是，當目標結點是第

6、d層的最后一個被擴展的結點時，它將耗費大量的時間。其優(yōu)先時間復雜度：O（bn+1）（b為分支因子，d為深度）；空間復雜度為所存儲的節(jié)點的個數(shù)。而深度優(yōu)先僅在結點有限的情況下是完備的，同樣的，它也不能找到最優(yōu)解。深度優(yōu)先的時間復雜度：O（bm）；空間復雜度：O（b*m+1）（b為分支因子，m為深度）。貪婪算法找到的解也不一定是最優(yōu)解。其時間復雜度：O（bm）（b代表分支數(shù)，m為深度）；空間復雜度為O(bm)。所以只有A*算法是完備的，且能夠找到最優(yōu)解。第二部分 N皇后問題（1）問題描述：在n*n格的國際象棋上擺放n個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上， 分

7、別用回溯法（遞歸）、GA算法和CSP算法求解n皇后問題。要求：. 輸入n，并用運行時間比較幾種算法在相同規(guī)模的問題時的求解效率，并列表給出結果。. 比較同一算法在n不相同時的運行時間，分析算法的時間復雜性，并列表給出結果。（2）數(shù)據(jù)結構：1、邏輯結構：用到線性結構包括一維數(shù)組，二維數(shù)組。2、存儲結構（物理結構）：順序存儲結構。（3）算法思想：回溯法：回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇。在N皇后問題中基本思想是：從第一列開始放置第一個皇后，然后第二列符合要求放第2個皇后，如果沒有符合位置符合要求，那么就要

8、改變第一個皇后的位置，重新放第2個皇后的位置，直到找到符合條件的位置，每次放置皇后之后都進行檢查，驗證是否符合要求（即皇后之間無沖突），當放置要求的數(shù)量N后問題即得到解。GA算法：從定義上看，遺傳算法是模擬物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。對于一個求函數(shù)最大值的優(yōu)化問題，首先初始化，包括種群的大小，編碼的方案，遺傳的代數(shù)，變異的概率，等等；然后進行選擇操作；接著是將選擇的個體進行交叉；然后再進行選擇，并將選擇的個體進行變異；最后就是更新最優(yōu)值了。在本題中，采用的選擇方法為按適應度比例選擇，其中適應度為染色體（棋盤）中的基因（皇后

9、）之間的沖突數(shù)目。操作過程如下，采用單親遺傳算法：1.產(chǎn)生初始種群。2. 對當前種群根據(jù)變異概率進行變異，生成新種群。3.檢驗停止準則，如果有解則停止，否則轉到2重復執(zhí)行。為了更快的得到解，采取了進一步的優(yōu)化，在選擇之后對中間個體進行一定幾率的變異（將適應度較低的基因進行變異），從而使得更快的得到解決方案。CSP算法：1.初始化各個信息表，皇后位置初始化先讓每列的皇后獨占一行，確保每一行只有一個皇后，再隨機交換任意兩列皇后所在的位置，打亂棋盤2.執(zhí)行最小沖突算法：1).分析棋盤，算出棋盤每個位置其他皇后對它的沖突數(shù)，一個皇后對它沖突那個位置的值+1，每個皇后會影響水平和兩個傾斜線上的各個位置2

10、).從第一列開始遍歷，把列的皇后移動到本列沖突數(shù)最小的位置，當有多個最小值的隨機取得其中的一個。3).更新棋盤，按皇后原來的位置和移動后的位置更新三個方向上各個位置的沖突數(shù)，原來位置三個方向上各個位置沖突數(shù)-1，移動后的位置三個方向各個位置沖突數(shù)+1，遍歷到最后一列。4).判斷是否滿足可行解，當各個皇后所在位置沖突數(shù)為0及找到可行解。5).當本次循環(huán)各個皇后的位置和上次循環(huán)皇后的位置不變，重新初始化各個皇后的位置。跳轉到 2）6).當找到可行解退出循環(huán)。（4） .運行結果：回溯法：GA算法：CSP算法：（兩種情況）找不到結果時：找到結果時：（笑臉表示放置皇后的位置，*表示未放置皇后）總體大致為

11、：（5） 比較結論：回溯法GA算法CSP算法時間復雜度O（n!）O(kN)O(NN)運行時間（s）1.0090.0615.4專心-專注-專業(yè)附程序關鍵代碼：羅馬尼亞度假問題：寬度優(yōu)先算法：int BFS()int i = 0,j,v = 0,r = 1,u = 0,m = 1,p = 0;initdata();while(1)if(needvisiti != 99)visitedv = needvisiti;v+;u = needvisiti;needvisiti = 99;for(j = 0;j 20;j+)if(datauj != 1000 & datauj != 0)p=check_vi

12、sit(j);if(p = 0)needvisitm = j;m+;resultr = j;r+;if(j = 2)BFS_out();return 0;elsei+;return 0;深度優(yōu)先算法：int find_after_node(int Line)int j;int p;for(j = 0;j ,);for(i = 1;resulti != 0 & i ,);return 0;elsereturn 1;return 1;int DFS()int i = 0,p1 = 0;n_num = 1;initdata();visited0

13、 = 0;needvisit1 = 0;/0標括?記?為a已?訪?問&從洙?第臺?結點?開a始?p1 = cal_DFS();while(p1 = 1)/沒?有瓺找到?正y確?路徑?r = r-1;resultr = 0;/結果?還1原-1位?needvisit1 = resultr-1;p1 = cal_DFS();for(i = 0;i 20;i+)if(visitedi = 99)n_num+;printf(NULL);printf(n生成結點數(shù)為a：%dn,n_num); return 0;貪婪算法：int find_Greedy_node(int Line,int r)int c1

14、= 0;/c為所需返回的下一結點編括號int j;int min = 1000;/存放最小移動消耗for(j = 0;j 20;j+)if(dataLinej != 1000 & dataLinej != 0 & check_visit(j) != 1)if(dataLinej min)min = dataLinej;c1 = j;visitedc1 = c1;resultr = c1;return c1;int Greedy_out(int r1)int i;int num = 0;printf(路徑為a:);for(i = 0;i r1 & i ,);fo

15、r(i = 0;i 20;i+)if(visitedi!=99)num+;printf(n生成結點數(shù)為a:%dn,num);return 0;int Greedy()int Line = 0;int r = 1;/r-resultinitdata();visited0 = 0;while(Line != 2)Line = find_Greedy_node(Line,r);r+;Greedy_out(r);return 0;A*算法：int find_A_node(int Line,int r)int c = 0;int j;int min = 10000;for(j = 0;j 20;j+)i

16、f(dataLinej != 1000 & dataLinej != 0 & check_visit(j) != 1)if(dataLinej+placej.qf min)min = dataLinej + placej.qf;c = j;visitedc = c;resultr = c;return c;int A_out(int r1)int i;int num = 0;printf(路徑為a:);for(i = 0;i r1 & i ,);for(i = 0;i 20;i+)if(visitedi!=99)num+;printf(n生成結點數(shù)為a:%dn

17、,num);return 0;int A()int Line = 0;int r = 1;initdata();visited0 = 0;while(Line != 2)Line = find_A_node(Line,r);r+;A_out(r);return 0;N皇后問題：回溯法：bool place(int k) int i; for(i = 1;in) for(i = 1;i = n;i+) coutxi ; coutendl; pl+; else for(i = 1; i = n; i+) xt = i; if(place(t) Queen(t+1); return 0; void

18、main() clock_t start,finish;double duration;printf(The number of queen:n);scanf(%d,&n);start = clock();if(n=0) printf(No results!);else Queen(1); coutplunitFitness = 0 ;for (i = 0 ; i eachFitnessi = 0 ;for (j = 0 ; j eachFitnessi += Aggressive(p, i, j) ;p-unitFitness += p-eachFitnessi ;void CreateSt

19、artPopulation ()int i, j ;int tmpMAX_QUEENS ;for (i = 0 ; i n ; i+)tmpi = i ;for (i = 0 ; i n ; i+)j = rand() % (n - i) ;s_population.queeni = tmpj ;tmpj = tmpn - i - 1 ;Update(&s_population) ;void Mutate () int i, j, swap ;int worst ;Population baby ;worst = 0 ;for (i = 0 ; i n ; i+)if (s_populatio

20、n.eachFitnessi s_population.unitFitness | (double)rand() / RAND_MAX Critical)s_population = baby ;int RouletteWheelSelection()int selection = 0;int i ;double slice = (double)rand() / RAND_MAX;double addFitness = 0;for(i = 0; i slice)selection = i;break;return selection;void CrossOverFM (Population f

21、ather, Population mother, Population *baby)int flagMAX_QUEENS ;int pos1, pos2, tmp ;int i, j ;do pos1 = rand() % n ;pos2 = rand() % n ; while (pos1 = pos2) ;if (pos1 pos2) tmp = pos1 ; pos1 = pos2 ; pos2 = tmp; for (j = 0 ; j n ; j +)flagj = 0 ;for (j = pos1; j = pos2; j+)flagfather.queenj = 1 ;for(

22、i = 0, j = 0 ; i n ; i+)if (i pos2) while (flagmother.queenj) j+ ;baby-queeni = mother.queenj ;j + ;else baby-queeni = father.queeni ;Update(baby) ;void CrossOver() int i ;int father, mother ;Population p30 + MAX_QUEENS / 10 ;int count ;m_totFitness = 0 ;for (i = 0 ; i m_size ; i+)m_totFitness += m_

23、populationi.unitFitness ;for (count = 0 ; count m_size - 2 ; count+)father = RouletteWheelSelection () ;mother = RouletteWheelSelection () ;CrossOverFM (m_populationfather, m_populationmother, &pcount) ; for (count = 0 ; count max_queens;int swap_row1, swap_row2;for(int i = 0; i queen_listi.init_pos

24、ition = i;list-queen_listi.result_position = i;list-queen_listi.conflicts = i;list-queen_listi.change = true;list-queen_listi.move_list_num = 0;memset(list-queen_listi.move_list,0,5*sizeof(int);/srand(time(NULL);for(int num = 0; num queen_listswap_row1.init_position = list-queen_listswap_row2.init_p

25、osition;list-queen_listswap_row2.result_position = list-queen_listswap_row1.result_position;list-queen_listswap_row1.result_position = list-queen_listswap_row1.init_position;list-queen_listswap_row2.init_position = list-queen_listswap_row2.result_position;int get_min_conflicts_position(List list,int

26、 row_num)int i, min_conflict_line_number = Queen_line_conflictsrow_num0;list-queen_listrow_num.move_list_num = 1; int line_number = 0; int line_conflict = 0;int move_num = 0;int rand_line_number; for(i = 1; i line_conflict)min_conflict_line_number = line_conflict;list-queen_listrow_num.move_list_num

27、 = 1; list-queen_listrow_num.move_list0 = i;line_number = i; else if(min_conflict_line_number = line_conflict) if(list-queen_listrow_num.move_list_num queen_listrow_num.move_list_num;list-queen_listrow_num.move_listmove_num = i;list-queen_listrow_num.move_list_num+; list-queen_listrow_num.conflicts

28、= min_conflict_line_number; move_num = list-queen_listrow_num.move_list_num;if(move_num 1)if(move_num 5) move_num = 5;srand(time(NULL);rand_line_number = rand() % move_num;line_number = list-queen_listrow_num.move_listrand_line_number;return line_number;int min_conflicts(List list)int row_num; int m

29、in_confilict_position = 0; int check_result = 0;int pre_line = 0;init_Qconflict(); analysisQueen(list); for(max_step = 0;max_step MAX_STEP;max_step+)float start = clock();for(row_num = 0; row_num queen_listrow_num.result_position != min_confilict_position)pre_line = list-queen_listrow_num.result_pos

30、ition;list-queen_listrow_num.result_position = min_confilict_position;list-queen_listrow_num.change = true;update_conflict_info(row_num, pre_line, -1);update_conflict_info(row_num, min_confilict_position, 1);elselist-queen_listrow_num.change = false; list-list_change = judge_has_change(list); check_

31、result = get_result(list);if(check_result = 1)output(list);return 1; if(list-list_change = false)update_list(list); init_Qconflict(); analysisQueen(list);float end = clock();return 0; void update_list(List list)init_queen(list);bool judge_has_change(List list)for(int i = 0; i queen_listi.change = tr

32、ue)return true;return false;int get_result(List list)for(int i = 0; i queen_listi.conflicts 0)return 0;return 1;void init_Qconflict()for(int i = 0;i QUEEN_NUM; i+)for(int j = 0; j QUEEN_NUM; j+)Queen_line_conflictsij = 0; void analysisQueen(List list)int level = 0;int up_down = 0;int position = 0;for(int row_num = 0; row_num QUEEN_NUM; row_num+) for(int i = 0;i queen_listi.result_position;Queen_line_conflictsrow_numlevel+;up_down = abs(i - row_num);position = list-queen_listi.result_position - up_down;if(position = 0)Queen_line_conflictsrow_numposition+; position = list-queen_listi.re