算法設(shè)計(jì)與分析-作業(yè)-第4章

1、 編程實(shí)現(xiàn)下述4個(gè)算法，利用給定數(shù)據(jù)，驗(yàn)證算法正確性 基于貪心法的凸多邊形三角剖分 哈夫曼編碼 單源最短路徑 最小生成樹基于貪心法的凸多邊形三角剖分-參見第3章ppt 利用： 1. “附件3-1.21個(gè)基站凸多邊形數(shù)據(jù)” 2. “附件3-2.29個(gè)基站凸多邊形數(shù)據(jù)” 給出的21凸多邊形頂點(diǎn)數(shù)據(jù)、 29凸多邊形頂點(diǎn)數(shù)據(jù)，以頂點(diǎn)間的地理距離作為連接2個(gè)頂點(diǎn)的邊、弦的權(quán)值，對(duì)這2個(gè)凸多邊形采用貪心法進(jìn)行三角剖分。算法要求：自上而下，（遞歸）分治，一分為三算法要求：自上而下，（遞歸）分治，一分為三凸多邊形三角剖分 21凸多邊形構(gòu)造方法 根據(jù)xx市td-lte網(wǎng)絡(luò)配置數(shù)據(jù)，選取全部基站enodeb； 以

2、這些基站作為平面點(diǎn)，構(gòu)造平面點(diǎn)集的凸包，得到具有21個(gè)頂點(diǎn)的凸21邊形 動(dòng)態(tài)規(guī)劃最優(yōu)三角剖分（學(xué)生作業(yè)樣例）凸多邊形三角剖分 29凸多邊形構(gòu)造方法 根據(jù)xx市td-lte網(wǎng)絡(luò)配置數(shù)據(jù)，選取部分基站enodeb； 以這些基站作為平面點(diǎn)，構(gòu)造平面點(diǎn)集的凸包，得到具有29個(gè)頂點(diǎn)的凸29邊形 動(dòng)態(tài)規(guī)劃最優(yōu)三角剖分（學(xué)生作業(yè)樣例）動(dòng)態(tài)規(guī)劃凸多邊形最優(yōu)三角剖分 . 窮搜0606006min 0 16()kkijttkt kw v v vij k=3k=1由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使tij值達(dá)到最小的位置由此，tij可遞歸地定義為：時(shí)間復(fù)

3、雜性o(n3)，當(dāng)n較大時(shí)，算法運(yùn)行時(shí)間較長(zhǎng)jijivvvwjktkitjitjkijki)(1min019void minweighttriangulation(int n，type * t, int *s) for (int i = 1; i = n; i+) tii = 0; for (int r = 2; r = n; r+) /*第1層循環(huán) for (int i = 1; i = n-r+1; i+) /*第2層循環(huán) int j= i + r 1 tii = ti+1j + w(i-1, i, j) sii =i; for (int k =i+1; k i+r-1; k+) int

4、u=tik + tk+1j + w(i-1,k,j); if (utij) tij) =u; sij) =k; 利用啟發(fā)式信息，在第2層循環(huán)內(nèi)部，直接選取某個(gè)vk，避免第3層循環(huán)，算法時(shí)間復(fù)雜性降為o(n2)z找到更好的劃分，并記錄結(jié)果t: 記錄子問題最優(yōu)值s：記錄子問題最優(yōu)劃分點(diǎn) 子問題vi、vj, 子問題規(guī)模r=j-i+1自下而上，不同規(guī)模r的子問題ii+1j貪心法凸多邊形三角剖分 自上而下，（遞歸）分治，貪心 避免求解過多子問題 根據(jù)啟發(fā)式信息選取斷點(diǎn)vk： 選取使dist(v0, vk) + dist(vk,vn) 最小的vk 自上而下遞歸分治法，自上而下遞歸分治法，采用固定(貪心)分

5、解方式：一分為三、一分一分為三、一分為二為二v0v1v2v3v4v5v6v0v1v2v3v4v5v6step1. v0v1v2v3v4v5v6=v0v1v2v3+ v0v3v6 +v3v4v5v6step2. v3v4v5v6 =v3v5v6 +v3v4v5不需要生成子問題不需要生成子問題v4v5v6優(yōu)點(diǎn)：避免生成過多不需要的、沒優(yōu)點(diǎn)：避免生成過多不需要的、沒有出現(xiàn)在最終剖分結(jié)果中的子問題有出現(xiàn)在最終剖分結(jié)果中的子問題遞歸分治法，遞歸分治法，一分為三、一分為二，分解標(biāo)準(zhǔn)一分為三、一分為二，分解標(biāo)準(zhǔn)貪心策略：貪心策略：v0v1v2v3v4v5v6對(duì)七邊形v0v1v2v3v4v5v6，從非起點(diǎn)、終

6、點(diǎn)v1v2v3v4v5這5個(gè)頂點(diǎn)中選擇vk，如v3，使三角形v0vkv6的三邊權(quán)重之和最小/最大v0v1v2v3v4v5v6對(duì)四邊形v3v4v5v6，從v4v5這2個(gè)頂點(diǎn)中選擇vk，如v5，使三角形v3vkv6的三邊權(quán)重之和最小/最大貪心法凸多邊形三角剖分 要求 1. 做圖表示結(jié)果 2. 計(jì)算三角剖分對(duì)應(yīng)的目標(biāo)值邊長(zhǎng)弦長(zhǎng)總和 3. 與第3章基于動(dòng)態(tài)規(guī)劃的最優(yōu)三角剖分結(jié)果進(jìn)行比較目標(biāo)值、剖分形狀 哈夫曼編碼 利用 “附件2.哈夫曼編碼輸入文本”給出的文本信息，統(tǒng)計(jì)26個(gè)英文字母及#出現(xiàn)的頻率； 對(duì)a, b, c,.,x, y, z, #，設(shè)計(jì)哈夫曼編碼； 按照哈夫曼編碼，對(duì)輸入文本重新編碼； 計(jì)

7、算采用哈夫曼編碼，輸入文本需要的存儲(chǔ)比特?cái)?shù)，并與定長(zhǎng)編碼方式需要的存儲(chǔ)比特?cái)?shù)進(jìn)行比較。附件2.哈夫曼編碼輸入文本內(nèi)容informally, an algorithm is any welldefined 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

8、the input into the 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 a specific computational procedure for achieving that input/out

9、put 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 the given computational problem. an incorrect algorithm might not halt at all on some input instances, or it might halt with an answer other than

10、 the desired one. contrary to what one might expect, incorrect algorithms can 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 correct

11、algorithms. 空格、標(biāo)點(diǎn)符號(hào)用”#“替換要求 給出如下結(jié)果 1. a, b, c,.,x, y, z, #中各成員在文本中的出現(xiàn)頻率和哈夫曼編碼 2. 采用哈夫曼編碼、定長(zhǎng)編碼，輸入文本需要的存儲(chǔ)比特?cái)?shù)單源最短路徑 從昆明lte網(wǎng)絡(luò)中，選取部分基站，計(jì)算基站間的距離，在部分基站間引入邊，得到1）22個(gè)基站頂點(diǎn)組成的圖2）42個(gè)基站頂點(diǎn)組成的圖 源點(diǎn)基站id： 567443終點(diǎn)基站id： 3310914681819112217716121421101321539520終點(diǎn)基站id： 565667源點(diǎn)基站id： 56584513342232744029221320241112363810

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