人工智能課程報(bào)告--分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和a_算法求解“羅馬利亞度假問題”-資料下載頁(yè)
2025-05-16 03:16本頁(yè)面
【正文】 )，最壞的情況是 O（ m*n^3）。 對(duì)于 GA 算法的時(shí)間復(fù)雜度，最好情況是 O(n^3)，最壞的情況是 O（ p*n^3）。 回溯法： void backtrack(int column) //以列作為判斷點(diǎn) { int row,i,j。 double secs, ms。 BK_stop =clock()。 ms = (double)(BK_stop BK_start)。 if(ms20xx0) //回溯法運(yùn)行超過 20s 就退出 { printf(BackT_Queen Calculations took more than 20 seconds !\n)。 exit(0)。 } if ( column==BK_Q_num) { BK_end = clock () 。 secs = (double)(BK_end BK_start) / CLOCKS_PER_SEC 。 printf(Back_Queen Calculations took %.3lf second%s.\n, secs, (secs 1 ? : s))。 exit(0)。 } else //放置第 column 列上的皇后，從第一行開始試探放置 for (row=0。rowBK_Q_num。row++) { Queen[column] = row。 if ( isSafe(Queen,column)) backtrack(column+1)。 //該點(diǎn)安全，向第 column 列遞歸 } } 人工智能課程報(bào)告 19 CSP 的最小沖突法： void Min_Conflict_Queens () { int i, j,Min。 Mf_Queens temp。 //從第一列開始尋找該列沖突數(shù)最小的皇后所在行，循環(huán)執(zhí)行每一列 for(i=0。iCSP_Q_num。i++) { temp = Min_conflictsQ。 UpdateConflictNum(amp。temp) 。 //更新該行皇后在每一列形成的新的棋面的總沖突數(shù) Min = RAND_MAX。 for(j=0。jCSP_Q_num。j++) { [i] = j。 UpdateColumn (amp。temp, i) 。 //更新棋盤第 i 列皇后放在 j 行的沖突度 if([i] Min) //把沖突數(shù)小的棋盤賦給 Min_conflictsQ { Min = [i]。 Min_conflictsQ = temp。 } if([i] == Min) //如果沖突數(shù)相等，則隨機(jī)更新棋盤 Min_conflictsQ = rand() % 2 ? Min_conflictsQ : temp。 } } } GA 算法： // 雙親遺傳中的變異算子 // 對(duì)種群中的最優(yōu)兩個(gè)個(gè)體保留，并局部變異看是否可以達(dá)到結(jié)果 void MultiMutate (Population* p) { int i, j, swap 。 int worst 。 Population baby 。 worst = 0 。 for (i = 0 。 i GA_Q_num 。 i++) if (peachFitness[i] peachFitness[worst]) worst = i 。 if(peachFitness[worst] == GA_Q_num1) return。 人工智能課程報(bào)告 20 baby = *p 。 for (i = 0 。 i GA_Q_num / 4 。 i++) { j = rand() % GA_Q_num 。 swap = [worst] 。 [worst] = [j] 。 [j] = swap 。 UpdateFitnessScore(amp。baby) 。 if ( punitFitness || (double)rand() / RAND_MAX M_Critical) { *p = baby 。 break 。 } } } // 采取輪盤賭局規(guī)則進(jìn)行雙親的選擇 // 即被選到的概率與適應(yīng)度呈正比 （越是優(yōu)越的個(gè)體基因越容易被保留下來） int RouletteWheelSelection() { int selection = 0。 int i 。 double slice = (double)rand() / RAND_MAX。 double addFitness = 0。 for(i = 0。 i m_size 。 i++) { addFitness += (double)m_population[i].unitFitness / m_totFitness 。 if(addFitness slice) { selection = i。 break。 } } return selection。 } // 雜交 father , mother， 產(chǎn)生的子代保存在 baby 中 void CrossOverFM (Population father, Population mother, Population *baby) { 人工智能課程報(bào)告 21 int flag[MAX_QUEENS] 。 int pos1, pos2, tmp 。 int i, j 。 // 隨機(jī)產(chǎn)生兩個(gè)基因斷點(diǎn) do { pos1 = rand() % GA_Q_num 。 pos2 = rand() % GA_Q_num 。 } while (pos1 == pos2) 。 if (pos1 pos2) { tmp = pos1 。 pos1 = pos2 。 pos2 = tmp。 } for (j = 0 。 j GA_Q_num 。 j ++) flag[j] = 0 。 for (j = pos1。 j = pos2。 j++) flag[[j]] = 1 。 for(i = 0, j = 0 。 i GA_Q_num 。 i++) { if (i pos1 || i pos2) { while (flag[[j]]) j++ 。 //保證每個(gè)皇后都不在同一行 babyqueen[i] = [j] 。 j ++ 。 } else babyqueen[i] = [i] 。 } UpdateFitnessScore (baby) 。 } // 雜交產(chǎn)生子代 void CrossOver () { int i 。 int father, mother 。 Population p[30 + MAX_QUEENS / 10] 。 int count 。 // 計(jì)算總共的 Fitness， 用于輪盤賭局規(guī)則時(shí)候的選擇 m_totFitness = 0 。 for (i = 0 。 i m_size 。 i++) m_totFitness += m_population[i].unitFitness 。 for (count = 0 。 count m_size 2 。 count++) { father = RouletteWheelSelection () 。 人工智能課程報(bào)告 22 mother = RouletteWheelSelection () 。 CrossOverFM (m_population[father], m_population[mother], amp。p[count]) 。 // 雜交 ,后代保存 } // 將結(jié)果覆蓋回原種群，加上原種群中適應(yīng)度最高的兩個(gè)個(gè)體組成新的進(jìn)化后的種群 for (count = 0 。 count m_size 2 。 count++) m_population[count+2] = p[count] 。 }
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1