[學(xué)習(xí)]算法設(shè)計與分析-作業(yè)-第5-6章-v

1、采用回溯法，編程求解下述3個問題，利用給定數(shù)據(jù)，驗證算法正確性,n皇后問題（局部搜索）圖的m著色問題（回溯）旅行商問題（回溯，分支限界）,n皇后問題,分析掌握講義ppt和“附件1.基于局部快速搜索的N皇后問題求解”中給出的“n皇后局部快速搜索”計算程序的原理、算法步驟、代碼結(jié)構(gòu)利用給定的程序，針對10個不同問題規(guī)模n，計算正確的n后排列方案。,注意： 根據(jù)實驗機(jī)器的實際運(yùn)行情況，選擇合適問題規(guī)模，但需要保持10組數(shù)據(jù)

2、。例如，如果問題規(guī)模n=500,000時，算法運(yùn)行時間已經(jīng)達(dá)到4小時左右，可以在5,000至500,000間取10個不同的n值?？疾爝@10個問題規(guī)模n下的算法運(yùn)行時間 此時，n可以取值：5,000 10,000 50,000 100,000 200,000 250,000 270,000 300,000400,00

3、0 500,000,要求,1. 對n的10個不同取值，編程統(tǒng)計程序運(yùn)行時間t(n)和為了得到正確解需要產(chǎn)生的初始隨機(jī)解個數(shù)m 2. 分析程序運(yùn)行時間t(n)、初始隨機(jī)解個數(shù)m隨問題規(guī)模n的變化規(guī)律 n～t(n)、 n～m注意： 1）采用程序設(shè)計語言提供的時間測量函數(shù)，測量程序運(yùn)行時間； 2）了解程序結(jié)構(gòu)，添加代碼，統(tǒng)計產(chǎn)生的初始隨機(jī)解個數(shù)m 3）如果由于問題規(guī)模n過小，無法測出程序準(zhǔn)確運(yùn)行時間，可適當(dāng)增

4、大n的數(shù)值,方法 根據(jù)資料/講義，算法在一個隨機(jī)解上的最壞復(fù)雜度為O(n3) 假設(shè)： t(n)=O(nk)，則 lgt(n) ～klgn， 通過對數(shù)據(jù)的線性回歸分析，以lgn為自變量x，以lgt(n)為因變量y，得到回歸表達(dá)式 y = k*x +b，判斷：1）階次k的范圍( ? ≤ k ≤ ?),2）t(n) ～ C nk,對數(shù)據(jù)的線性回歸分析,Step1. 計算數(shù)據(jù)對Step2. 以lgn為自變量

5、x，以lgt(n)為因變量yStep3. 利用Excel的”數(shù)據(jù)分析”功能，作出的散點圖，觀察lgn ～ lgt(n)>間的數(shù)據(jù)變化趨勢Step4. 利用Excel線性回歸分析函數(shù)，針對數(shù)據(jù)對，回歸分析，得到表達(dá)式 y = k*x +b，即 lgt(n) = k* lgn + bExcel線性回歸函數(shù)：參見百度文庫“excel——回歸分析”http://wenku.baidu.com/view/a

6、628ff6db84ae45c3b358c44.html,分析結(jié)果1. 算法運(yùn)行數(shù)據(jù)，記錄在（前一張）表格中2. 散點圖3. 線性回歸表達(dá)式lgt(n) = k* lgn + b,不許抄襲！,不同臺式機(jī)、筆記本電腦的硬件配置不同，在2臺不同機(jī)器上程序運(yùn)行時間t(n)不可能完全相同?。?！,圖的m著色問題,從昆明LTE網(wǎng)絡(luò)中，選取部分基站，計算基站間的距離，在部分基站間引入邊，得到1）圖1. n=22個基站頂點組成的圖2）圖3.

7、n=42個基站頂點組成的圖,說明：2個基站間如果無直接路徑，則鄰接矩陣中2個基站頂點間的權(quán)重為99999,圖1. 22個基站組成的無向圖,圖2. 30個基站組成的無向圖,圖3. 42個基站組成的無向圖,圖的m著色問題,,要求,,旅行商問題,針對昆明LTE網(wǎng)絡(luò)，選取部分基站，計算基站間的距離，在部分基站間引入邊，得到1）圖1. n=15個基站頂點組成的圖，以圖中基站頂點作為城市——從n=22的基站圖中，去除2組、7個位置相鄰的基站：2

8、, 12, 15; 4, 6, 8,18——對應(yīng)地，從22個基站頂點的鄰接矩陣(.xls)中，去除這7個基站對應(yīng)的行、列， 得到15個基站頂點的鄰接矩陣,圖1. 15個基站組成的無向圖,,,去除頂點{2,12,15}及關(guān)聯(lián)邊,去除頂點{6,4,8,18}及關(guān)聯(lián)邊,旅行商問題,2）圖2. n=20個基站頂點組成的圖，以圖中基站頂點作為城市——從n=22的基站圖中，去除2個位置相鄰的基站：4, 6——對應(yīng)地，從22個基站頂

9、點的鄰接矩陣(.xls)中，去除這2個基站對應(yīng)的行、列， 得到20個基站頂點的鄰接矩陣,圖2. 20個基站組成的無向圖,,去除頂點{6,4}及關(guān)聯(lián)邊,圖3. 22個城市組成的無向圖,圖4. 30個基站組成的無向圖,,旅行商問題（續(xù)）,參照教科書，編程實現(xiàn)回溯法、分支限界法，求解旅行商問題，并對比2個算法對同一規(guī)模問題的運(yùn)行時間參照圖1、圖2，針對指定起始城市，計算最短旅行路徑 1） 圖1 15個基站圖，起始城市

10、結(jié)點20 2） 圖2 20個基站圖，起始城市結(jié)點20,說明：圖中頂點數(shù)目為>22個基站時，可能導(dǎo)致：回溯法運(yùn)行時間較長，或分支限界法占用內(nèi)存空間過多，無法求出最終解，故不考慮頂點數(shù)目過多的圖。,要求,1. 修改完善程序，統(tǒng)計搜索過程中掃描過的搜索樹結(jié)點總數(shù)L2.修改完善程序，記錄程序運(yùn)行時間T3. 針對圖1、圖2，輸出采用回溯法、分支限界法得到的 1）從起始城市出發(fā)的最短旅行路徑 2）路徑總長度 3）掃描

11、過的搜索樹結(jié)點總數(shù)L 4）程序運(yùn)行時間T 結(jié)果記錄在下列表格中：,說明：如果時間充裕 （不做硬性要求），試著針對n=22個基站組成的無向圖，采用回溯法求解最短回路。n=22時，采用分支限界法求解時，可能需要搜索和記錄的活結(jié)點過多，導(dǎo)致內(nèi)存溢出。,作業(yè)提交要求,最遲至第19周，提交電子版，pdf格式 作業(yè)文檔內(nèi)容包括： 源程序代碼，運(yùn)行結(jié)果文檔名稱： 班號_學(xué)號_姓名_算法設(shè)計與分析_第5-6章