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

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

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

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

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

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

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

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

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

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

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

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