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

1、編程實現(xiàn)下述4個算法，利用給定數(shù)據(jù)，驗證算法正確性,基于貪心法的凸多邊形三角剖分哈夫曼編碼單源最短路徑最小生成樹,基于貪心法的凸多邊形三角剖分-參見第3章ppt,利用： 1. “附件3-1.21個基站凸多邊形數(shù)據(jù)” 2. “附件3-2.29個基站凸多邊形數(shù)據(jù)” 給出的21凸多邊形頂點數(shù)據(jù)、 29凸多邊形頂點數(shù)據(jù)，以頂點間的地理距離作為連接2個頂點的邊、弦的權(quán)值，對這2個凸多邊形采用

2、貪心法進行三角剖分。算法要求：自上而下，（遞歸）分治，一分為三,凸多邊形三角剖分,21凸多邊形構(gòu)造方法 根據(jù)xx市TD-LTE網(wǎng)絡(luò)配置數(shù)據(jù)，選取全部基站eNODEB； 以這些基站作為平面點，構(gòu)造平面點集的凸包，得到具有21個頂點的凸21邊形,動態(tài)規(guī)劃最優(yōu)三角剖分（學(xué)生作業(yè)樣例）,凸多邊形三角剖分,29凸多邊形構(gòu)造方法 根據(jù)xx市TD-LTE網(wǎng)絡(luò)配置數(shù)據(jù)，選取部分基站eNODEB； 以這些基站作為平面

3、點，構(gòu)造平面點集的凸包，得到具有29個頂點的凸29邊形,動態(tài)規(guī)劃最優(yōu)三角剖分（學(xué)生作業(yè)樣例）,動態(tài)規(guī)劃凸多邊形最優(yōu)三角剖分,,,.,,,窮搜,,,k=3,k=1,由于在計算時還不知道k的確切位置，而k的所有可能位置只有j-i個，因此可以在這j-i個位置中選出使t[i][j]值達到最小的位置由此，t[i][j]可遞歸地定義為：時間復(fù)雜性O(shè)(n3)，當n較大時，算法運行時間較長,,9,void MinWeightTria

4、ngulation(int n，Type ** t, int **s){ for (int i = 1; i <= n; i++) t[i][i] = 0; for (int r = 2; r <= n; r++) /*第1層循環(huán) for (int i = 1; i <= n-r+1; i++) {/*第2層循環(huán)

5、int j= i + r – 1 t[i][i] = t[i+1][j] + w(i-1, i, j) s[i][i] =i; for (int k =i+1; k <i+r-1; k++) { int u=t[i][k] + t[k+1][

6、j] + W(i-1,k,j); if (u<t[i][j]) {t[i][j]) =u; s[i][j]) =k; } } }},利用啟發(fā)式信息，在第2層循環(huán)內(nèi)部，直接選取某個vk，避免第3層循環(huán)，算法時間復(fù)雜性降為O(n2),Z找到更好的劃分，并記錄結(jié)果,t: 記錄子問題最優(yōu)值s：記錄子問題最優(yōu)劃分點,子問題vi、…、vj

7、, 子問題規(guī)模r=j-i+1,自下而上，不同規(guī)模r的子問題,,,,,,,,i,i+1,j,,,貪心法凸多邊形三角剖分,自上而下，（遞歸）分治，貪心 避免求解過多子問題根據(jù)啟發(fā)式信息選取斷點vk： 選取使dist(v0, vk) + dist(vk,vn) 最小的vk,自上而下遞歸分治法，采用固定(貪心)分解方式：一分為三、一分為二,v0,v1,v2,v3,v4,v5,v6,v0,v1,v2,v3,v4,

8、v5,v6,step1. {v0v1v2v3v4v5v6}={v0v1v2v3}+ {v0v3v6} +{v3v4v5v6,step2. {v3v4v5v6} ={v3v5v6} +{v3v4v5},不需要生成子問題{v4v5v6},,優(yōu)點：避免生成過多不需要的、沒有出現(xiàn)在最終剖分結(jié)果中的子問題,遞歸分治法，一分為三、一分為二，分解標準—貪心策略：,v0,v1,v2,v3,v4,v5,v6,對七邊形{v0v1v2v3v4v5v6

9、}，從非起點、終點v1v2v3v4v5這5個頂點中選擇vk，如v3，使三角形{v0vkv6}的三邊權(quán)重之和最小/最大,v0,v1,v2,v3,v4,v5,v6,對四邊形{v3v4v5v6}，從v4v5這2個頂點中選擇vk，如v5，使三角形{v3vkv6}的三邊權(quán)重之和最小/最大,貪心法凸多邊形三角剖分,要求 1. 做圖表示結(jié)果 2. 計算三角剖分對應(yīng)的目標值——邊長弦長總和 3. 與第3章基于動態(tài)規(guī)劃的最優(yōu)三角剖分結(jié)果進行比

10、較——目標值、剖分形狀,哈夫曼編碼,利用 “附件2.哈夫曼編碼輸入文本”給出的文本信息，統(tǒng)計26個英文字母及#出現(xiàn)的頻率；對{a, b, c,..,x, y, z, #}，設(shè)計哈夫曼編碼；按照哈夫曼編碼，對輸入文本重新編碼；計算采用哈夫曼編碼，輸入文本需要的存儲比特數(shù)，并與定長編碼方式需要的存儲比特數(shù)進行比較。,附件2.哈夫曼編碼輸入文本內(nèi)容,Informally, an algorithm is any welldefi

11、ned computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the

12、 output.We can also view an algorithm as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes

13、a specific computational procedure for achieving that input/output relationship.An algorithm is said to be correct if, for every input instance, it halts with the correct output. We say that a correct algorithm solves t

14、he given computational problem. An incorrect algorithm might not halt at all on some input instances, or it might halt with an answer other than the desired one. Contrary to what one might expect, incorrect algorithms ca

15、n sometimes be useful, if their error rate can be controlled. We shall see an example of this in Chapter when we study algorithms for finding large prime numbers. Ordinarily, however, we shall be concerned only with corr

16、ect algorithms.空格、標點符號用”#“替換,要求,給出如下結(jié)果1. {a, b, c,..,x, y, z, #}中各成員在文本中的出現(xiàn)頻率和哈夫曼編碼2. 采用哈夫曼編碼、定長編碼，輸入文本需要的存儲比特數(shù),單源最短路徑,從昆明LTE網(wǎng)絡(luò)中，選取部分基站，計算基站間的距離，在部分基站間引入邊，得到1）22個基站頂點組成的圖2）42個基站頂點組成的圖,,,源點基站ID： 567443,終點基站ID： 33109,

17、1,4,6,8,18,19,11,22,17,7,16,12,14,21,10,13,2,15,3,9,5,20,,,終點基站ID： 565667,源點基站ID： 565845,1,33,42,23,27,4,40,29,22,13,20,24,11,12,36,38,10,7,39,3,17,15,30,9,8,18,19,21,34,26,32,41,37,14,28,2,5,25,35,6,31,16,單源最短路徑,對22個基站頂

18、點組成的圖，以基站567443為源點，1. 計算567443到其它各點的單源最短路徑； 2.計算567443到33109的最短路徑 對42個基站頂點組成的圖，以基站565845為源點， 1. 計算565845到其它各點的單源最短路徑； 2. 計算565845到565667的最短路徑,最小生成樹,從昆明LTE網(wǎng)絡(luò)中，選取部分基站，計算基站間的距離，在部分基站間引入邊，得到1）22個基站頂點組成的圖2）42個基站頂點

19、組成的圖,,,1,33,42,23,27,4,40,29,22,13,20,24,11,12,36,38,10,7,39,3,17,15,30,9,8,18,19,21,34,26,32,41,37,14,28,2,5,25,35,6,31,16,最小生成樹,生成這2個圖的最小生成樹要求：采用K算法，或P算法；給出最小生成樹的成本/代價/耗費cost做圖，呈現(xiàn)出最小生成樹, 可以在原圖上，用紅色、粗線條，標記最小生成