人工智能課程設計報告(編輯修改稿)
2024-08-30 09:47 本頁面
【文章內容簡介】 ptimal_col)]++。 R[row] = optimal_col。 if (col[cur_col] == 1 amp。amp。 col[optimal_col] == 1 amp。amp。 pdiag[GetP(row, optimal_col)] == 1 amp。amp。 cdiag[GetC(row, optimal_col)] == 1) { return Qualify()。//qualify相對更耗時，所以只在滿足上面基本條件后才檢查 } } //否則當前點就是最佳點，一切都保持不變 return false。//如果都沒變的話，肯定不滿足終止條件，否則上一次就應該返回true并終止了}//檢查沖突bool CSP_Queens::Qualify(){ for (int i = 0。 i N。 i++){ if (col[R[i]] != 1 || pdiag[GetP(i, R[i])] != 1 || cdiag[GetC(i, R[i])] != 1) { return false。 } } return true。}//最終用戶調用函數(shù)，numOfQueens為輸入皇后數(shù)，PrintChessBoard判斷是否輸出棋盤表示int CSP_Queens::CSPAlgorithms(bool PrintChessBord){ srand((unsigned)time(NULL))。 Init()。 if (Qualify()) {//運氣很好，初始化后就滿足終止條件 if (PrintChessBord)Print_result()。 return 0。 } bool end = false。 while (!end) { for (int i = 0。 i N。 i++) { if (Adjust_row(i)) { end = true。 break。 } } } if (PrintChessBord)Print_result()。 return 0。}=4時不同算法的比較=8時不同算法比較結果分析回溯法在皇后數(shù)目較小的，很占優(yōu)勢，它的速度非常的快，但隨著皇后數(shù)目的增加，回溯法顯得很不實用，在n=35時，用回溯法已不能較好的解決n皇后問題。 遺傳算法優(yōu)點是能很好的處理約束，能很好的跳出局部最優(yōu)，最終得到全局最優(yōu)解，全局搜索能力強；缺點是收斂較慢，局部搜索能力較弱，運行時間中等，且容易受n值的影響。遺傳算法的運行時間在n很小時沒有回溯法快，但是隨著n值的增加，遺產算法的優(yōu)點也就顯現(xiàn)出來，它能夠解決回溯法不能解決的問題。CSP最小沖突法是一種始終都比較快的算法，它的運行時間與皇后是個數(shù)沒有必然的聯(lián)系，而且在n很大時，它顯現(xiàn)出來運行時間短，效率高的優(yōu)勢，但它的缺點是會出現(xiàn)山脊、高原，86%的時間會卡住。總的來說，CSP最小沖突法較簡單，也比較快，在皇后的個數(shù)較多時體現(xiàn)出來效率最高，處理多約束大規(guī)模問題時往往不能得到較好的解。 總的來說，回溯在n值很小時，效率很高，但其求解范圍很小，超過35基本就解不出來，遺傳算法求解范圍適中。在n值很大(100)時，前兩者都不能再解決，此時，CSP最小沖突法的效率最高，且與n值沒有必然的聯(lián)系。總結 通過此次課程實習不僅大大加深了我對幾種經典搜索算法的理解，而且?guī)椭液芎玫膹土暳岁犃小⒍褩?、圖、文件讀寫這幾部分的內容，使我對幾種基本的數(shù)據結構類型的運用更加熟練。在解決這些問題的過程中我不但很好的鞏固了數(shù)據結構的相關知識，而且提高了編程及程序調試能力，增強了自己編程的信心。 總之，在這次課程實習過程中我是實實在在學到了一些課堂上學不到的東西，同時也提高了實踐能力。同時在這個過程中也暴露了自己的不少問題，在今后的學習過程成也會更加有針對性。最后還要感謝老師的悉心指導，解答我編程過程中的疑問、指出我程序中的不足，及提出可行的解決方法，讓我的程序的功能更加完善。CSP算法源代碼：//pragma onceclass CSP_Queens{public: //構造函數(shù)，numOfQueens為輸入皇后數(shù)， CSP_Queens(int numOfQueens)。 ~CSP_Queens()。private: //row[i]表示當前擺放方式下第i行的皇后數(shù)， int *row。 //col[i]表示當前擺放方式下第i列的皇后沖突數(shù) int *col。 int N。 //放置N個皇后在N*N棋盤上 //從左上到右下的對角線上rowcol值是相同的，但是這個值有可能是負值，最小為(N1)， //所以可以做個偏移，統(tǒng)一加上N1，這樣這個值就在[0,2*N2]范圍內，將這個值作為該對角線的編號 //pdiag[i]表示當前擺放方式下編號為i的對角線上的皇后數(shù) int *pdiag。//principal diagonal,主對角線，左上到右下（表示和主對角線平行的2N1條對角線） //從右上到左下的對角線row+col的值相同，取值范圍為[0, 2 * N 2]，2*N1條，作為對角線編號 //cdiag[i]表示編號為i的對角線上的皇后數(shù) int *cdiag。//counter diagonal,副對角線 //R[]用來存儲皇后放置
環(huán)評公示相關推薦
鄂ICP備17016276號-1