2022～ 2023學(xué)年度第一學(xué)期 研究生學(xué)位課《 算法設(shè)計(jì)與分析 》 期末大作業(yè)

2022級(jí)電子信息天理研究生

一、簡(jiǎn)答題

1．若，寫出用Θ、Ω和О描述f(n) 的漸進(jìn)表達(dá)。（7分）

答：
屬于T(n)=aT(n/b)+cn^{k的形式，其中cn}k表示問(wèn)題分解成子問(wèn)題和將子問(wèn)題的解合并成原問(wèn)題的解的時(shí)間。
此時(shí)a=9，b=3，k=1，cn^{k=n。所以f(n)=Θ(n}logb^a)=Ω(n)=O(n2)

2．求解某一問(wèn)題的算法1在最壞情形下的時(shí)間復(fù)雜度是，算法2在最壞情形下的時(shí)間復(fù)雜度是，且，則算法1與算法2在最壞情形下的時(shí)間代價(jià)消耗上的優(yōu)劣關(guān)系如何？（8分）

答：
對(duì)于T1來(lái)說(shuō)它表示隨著問(wèn)題規(guī)模n的增大，算法的執(zhí)行時(shí)間的增長(zhǎng)率與f(n)的增長(zhǎng)率相同，一般指的是最壞情況下的時(shí)間復(fù)雜度，也就是算法運(yùn)行時(shí)間的上界。而對(duì)于T2來(lái)說(shuō)，大Ω記號(hào)看成n的一類函數(shù)。n趨向無(wú)窮大時(shí)，T2(n)的增長(zhǎng)趨勢(shì)，始終超過(guò)g(n)。大Ω記號(hào)也表示為漸近下界，所以算法1的時(shí)間消耗要大于算法2。

3．圖的單源最短路徑問(wèn)題用Dijkstra算法求解時(shí)，若某些邊的權(quán)值為負(fù)數(shù)，先對(duì)圖中的每一條邊加上一個(gè)相同的充分大的正數(shù)使得每一條邊的權(quán)值非負(fù)，然后再用Dijkstra算法求解即可得到原問(wèn)題的解。若該方法可行，請(qǐng)說(shuō)明理由；若該方法不可行，請(qǐng)舉例說(shuō)明。（10）

答：
該方法可行，首先用Dijkstra算法求解單源最短路徑問(wèn)題時(shí)，若某些邊的權(quán)值為負(fù)數(shù)，Dijkstra算法是肯定失效的，但是如題中所提示的思想，先對(duì)圖中的每一條邊加上一個(gè)相同的充分大的正數(shù)使得每一條邊的權(quán)值非負(fù)，然后再用Dijkstra算法求解即可得到原問(wèn)題的解。
（1）核心思想：利用約翰遜Johnson算法來(lái)輔助Dijkstra算法進(jìn)行求解。所以核心算法為約翰遜Johnson算法來(lái)計(jì)算出每條邊加上的充分大的正數(shù)。
（2）翰遜Johnson算法流程：Johnson算法的核心是對(duì)所有邊權(quán)重重新標(biāo)記。新標(biāo)號(hào)的邊權(quán)轉(zhuǎn)化為非負(fù)的，從而使得Dijkstra算法在新圖上可用。
①建立超級(jí)源點(diǎn) src 向所有的點(diǎn)連一條權(quán)重為 0 的有向邊（這樣其他點(diǎn)不會(huì)走到 src）。
②以 src 為源點(diǎn)跑 Bellman-Ford 確定圖中是否有負(fù)環(huán)并確定 h[i] 的值，有負(fù)環(huán)直接結(jié)束。
③以每一個(gè)原圖中的點(diǎn)為起點(diǎn)，以 w(u,v)+h[u]?h[v] 為邊的權(quán)重跑 V 次 Dijkstra。
④得到的距離數(shù)組 dis[u][v] 需要 ?h[u]+h[v] 才能得出真實(shí)的距離，注意特殊處理無(wú)法走到的情況的值。
（3）算法詳細(xì)步驟：
這里我們引入一個(gè)類似于勢(shì)能和每個(gè)結(jié)點(diǎn)綁定的值h[i]，考慮邊<u,v>權(quán)重為w<u,v>，重新標(biāo)記邊權(quán)為：
，這樣標(biāo)記的好處是對(duì)于一條路徑v0，v1，…,vn，原圖的長(zhǎng)度為：sum=w(v0，v1)+w(v1，v2)+…+w(vn-1，vn)，而新圖的長(zhǎng)度為:

經(jīng)過(guò)處理后，我們發(fā)現(xiàn)原圖與新圖路徑長(zhǎng)度的差值其實(shí)只與起止位置有關(guān)，與路徑無(wú)關(guān)，原圖的路徑和新圖的最短路徑的選擇是等價(jià)的。
（4）算法評(píng)估：
① 空間復(fù)雜度：Bellman-Ford 我們只需要一個(gè)額外的 h 數(shù)組，Dijkstra 需要 O(V) 的空間不贅述。如果每一輪我們都直接將求出的最短路都輸出而不是存在一個(gè) O(V2) 的數(shù)組中的話，那么額外空間就是 O(V) 的，存圖的空間為 O(V+E) 總復(fù)雜度為 O(V+E)。
② 時(shí)間復(fù)雜度：Bellman-Ford 為 O(VE) 。如果使用優(yōu)化的 Dijkstra 則總復(fù)雜度為 O(V(E+V)logE)。

4．人們希望通過(guò)一系列的貨幣兌換能夠從1元某種貨幣換得大于1元的同種貨幣（例如：美元->日元->加元->歐元->美元），這種操作俗稱“套匯”. 因此要解決的問(wèn)題是：①?gòu)哪骋还潭ㄘ泿懦霭l(fā)，能否找到這樣的貨幣序列，達(dá)到獲得收益的目的；②求能夠得到最大收益的貨幣序列. 要求： 1)用圖模型來(lái)準(zhǔn)確地建模描述該問(wèn)題；2)分析一下若采用窮舉法解該問(wèn)題應(yīng)付出的最大計(jì)算量(可對(duì)n=8時(shí)計(jì)算).（10）

答：

步驟一：

構(gòu)造圖G=（V，E），其中頂點(diǎn)為n種貨幣Ci1，Ci2…Cin，設(shè)有關(guān)兌換率的矩陣為R，R[i，j]表示一單位貨幣ci能夠兌換cj的單位數(shù)。由題可得：R[i1，i2]，R[i2，i3]…R[iR-1,i R],R[iR,i1]>1,即：

1/（R[i1，i2]*R[i2，i3]…R[iR-1,iR]*R[iR,i1]）<1

兩邊取對(duì)數(shù)得：

lg（1/R[i1,i2]）+lg（1/R[i2,i3]）+…+lg（1/R[iR-1,iR]）+lg（1/R[iR,i1]）<0

則可設(shè)邊（i1，i2）的權(quán)值為lg（1/R[i1,i2]），即為-lg（R[i1,i2]），此問(wèn)題即轉(zhuǎn)換為尋找一個(gè)負(fù)回路Ci1，Ci2…Cik，Ci1使得 -（lgR[i1,i2]+lgR[i2,i3]+…lgR[iR,i1]）<0，可以使用Floyd算法求解，此時(shí)最壞的時(shí)間復(fù)雜度為O（n^3）

步驟二：
假設(shè)需要兌換的貨幣為Ci，則一共有C81=8種選擇，然后選擇第一次兌換的貨幣公有C71=7種選擇，依次選擇，最后選擇到C1，此時(shí)的復(fù)雜度為C（8！），若采用窮舉法解決該問(wèn)題是，時(shí)間復(fù)雜度為O（n?。?。

5．什么是哈夫曼（Huffman）樹，簡(jiǎn)述哈夫曼編碼過(guò)程，哈夫曼編碼過(guò)程是按照什么算法設(shè)計(jì)方法設(shè)計(jì)的？有n個(gè)葉節(jié)點(diǎn)的哈夫曼樹一定有多少個(gè)節(jié)點(diǎn)并給出簡(jiǎn)單證明。（10分）

答：

（1）哈夫曼（Huffman）樹：哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹。所謂樹的帶權(quán)路徑長(zhǎng)度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。
（2）哈夫曼編碼過(guò)程：哈夫曼編碼是基于哈夫曼樹而產(chǎn)生的一種編碼，如果已經(jīng)構(gòu)建完成哈夫曼樹后，哈夫曼編碼就是左子樹上的為0，右子樹上的為1，從根節(jié)點(diǎn)掃描下來(lái)到葉子節(jié)點(diǎn)，編碼完成后此過(guò)程稱為哈夫曼編碼過(guò)程，而輸出的值為哈夫曼編碼。
（3）哈弗曼樹編碼過(guò)程的算法設(shè)計(jì)方法：運(yùn)用特定的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編碼。哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹─即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無(wú)損耗壓縮。這一術(shù)語(yǔ)是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來(lái)的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的）。這種方法是由David.A.Huffman發(fā)展起來(lái)的。
（4）有n個(gè)葉節(jié)點(diǎn)的哈夫曼樹一定有2n-1個(gè)節(jié)點(diǎn)
證明：
兩個(gè)節(jié)點(diǎn)合成一個(gè)節(jié)點(diǎn)，變成一個(gè)結(jié)點(diǎn)，兩個(gè)葉子結(jié)點(diǎn)(兩個(gè)葉結(jié)點(diǎn)，一個(gè)根結(jié)點(diǎn),共三個(gè)結(jié)點(diǎn))滿足2n-1；這棵樹與另一個(gè)節(jié)點(diǎn)又組成一棵樹，這樣增加了兩個(gè)結(jié)點(diǎn)，多了一個(gè)葉結(jié)點(diǎn)，又滿足2n-1；這樣繼續(xù)下去，都是多兩個(gè)結(jié)點(diǎn)，多一個(gè)葉子結(jié)點(diǎn)。所以滿足一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)。

6．簡(jiǎn)述動(dòng)態(tài)規(guī)劃的基本原理和方法，說(shuō)明使用動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)求解算法的適用問(wèn)題的特點(diǎn)和基本步驟。簡(jiǎn)述用動(dòng)態(tài)規(guī)劃方法與分治方法所設(shè)計(jì)的算法的共同點(diǎn)和不同點(diǎn)。（10分）

答：
（1）動(dòng)態(tài)規(guī)劃的基本原理和方法：
① 將原問(wèn)題分解為n個(gè)子問(wèn)題：將原問(wèn)題分解為若干個(gè)子問(wèn)題，子問(wèn)題和原問(wèn)題形式相同或者類似，只不過(guò)規(guī)模變小，當(dāng)子問(wèn)題全部解決時(shí)，原問(wèn)題即解決。子問(wèn)題的解一旦求出就被保存，所以每個(gè)子問(wèn)題只需要求解一次。
② 確定狀態(tài)：用動(dòng)態(tài)規(guī)劃解決問(wèn)題，經(jīng)常碰到的情況是，K個(gè)整形變量能構(gòu)成一個(gè)狀態(tài)，我們用一個(gè)K維的數(shù)組來(lái)存儲(chǔ)各個(gè)狀態(tài)的值。注意這里的值并不一定是一個(gè)數(shù)，而可能是結(jié)構(gòu)體等。一個(gè)狀態(tài)下的值通常是一個(gè)或者多個(gè)子問(wèn)題的解。
③ 確定一些初始狀態(tài)（邊界條件）的值：如果使用記憶化搜索，即設(shè)置遞歸出口，如果使用遞推，就需要將這些值填入dp數(shù)組。
④ 確定狀態(tài)轉(zhuǎn)移方程：求出不同狀態(tài)之間是如何遷移的，即如何從一個(gè)或者多個(gè)值已知的狀態(tài)，求出另一個(gè)狀態(tài)的值。狀態(tài)的遷移通?？梢杂眠f推公式表示，該公式就是狀態(tài)遷移方程。
（2）動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)求解算法的適用問(wèn)題的特點(diǎn)：
① 問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)：如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，我們就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
② 無(wú)后效性：當(dāng)前的若干個(gè)狀態(tài)值一旦確定，則此后過(guò)程的演變就只和這若干個(gè)狀態(tài)的值有關(guān)，和之前是采取那種手段、哪條路徑演變到當(dāng)前的這若干個(gè)狀態(tài)無(wú)關(guān)。事實(shí)上，不滿足無(wú)后效性的問(wèn)題分解是寫不出狀態(tài)轉(zhuǎn)移方程的。不過(guò)這也與我們分劃問(wèn)題涉及狀態(tài)的藝術(shù)有關(guān)。
（3）動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)求解算法的適用問(wèn)題的基本步驟：
① 劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段。注意這若干個(gè)階段一定要是有序的或者是可排序的（即無(wú)后向性），否則問(wèn)題就無(wú)法用動(dòng)態(tài)規(guī)劃求解。
② 選擇狀態(tài)：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。
③ 確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來(lái)了。但事實(shí)上，我們常常是反過(guò)來(lái)做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來(lái)確定決策。
④ 寫出規(guī)劃方程（包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。一般說(shuō)來(lái)，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡(jiǎn)單的。動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。根據(jù)動(dòng)態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最優(yōu)值，但是一般將其改為遞推計(jì)算。實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃，而是按以下幾個(gè)步驟進(jìn)行：
（i）分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。
（ii）遞歸地定義最優(yōu)值。
（iii）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。
（iiii）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。
（4）動(dòng)態(tài)規(guī)劃方法與分治方法所設(shè)計(jì)的算法的共同點(diǎn)和不同點(diǎn)：
① 相同點(diǎn)：動(dòng)態(tài)規(guī)劃通常用于求解最優(yōu)解問(wèn)題，與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。
② 不同點(diǎn)：分治法是將原問(wèn)題分解為多個(gè)子問(wèn)題，利用遞歸對(duì)各個(gè)子問(wèn)題獨(dú)立求解，最后利用各子問(wèn)題的解進(jìn)行合并形成原問(wèn)題的解。分治法將分解后的子問(wèn)題看成是相互獨(dú)立的。若用分治法來(lái)解這類問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，有些子問(wèn)題會(huì)被重復(fù)計(jì)算多次。而動(dòng)態(tài)規(guī)劃的做法是將已解決子問(wèn)題的答案保存下來(lái)，動(dòng)態(tài)規(guī)劃將分解后的子問(wèn)題理解為相互間有聯(lián)系，有重疊的部分。在需要子問(wèn)題答案的時(shí)候便可直接獲得，而不需要重復(fù)計(jì)算，這樣就可以避免大量的重復(fù)計(jì)算，提高效率。

二、算法的設(shè)計(jì)與分析問(wèn)題（共45分）

1.判別一個(gè)算法優(yōu)劣的基本準(zhǔn)則有哪些?按照這些準(zhǔn)則要求,設(shè)計(jì)一個(gè)計(jì)算多項(xiàng)式數(shù)值的盡可能好的算法，并指出其算法時(shí)間復(fù)雜度（17分）.

（1）算法優(yōu)劣的基本準(zhǔn)則：
①正確性、可讀性、健壯性：對(duì)不合理輸入的反映能力和處理能力
②時(shí)間復(fù)雜度：估算程序指令的執(zhí)行次數(shù)（執(zhí)行時(shí)間）
③空間復(fù)雜度：估算所需占用的存儲(chǔ)空間
一個(gè)好的算法要好，執(zhí)行次數(shù)越少，所占用的存儲(chǔ)空間越小，也就是時(shí)間復(fù)雜度要低，空間復(fù)雜度也要低。
（2）算法設(shè)計(jì)：
方法一（直觀累加算法）：
① 核心思想：
根據(jù)多項(xiàng)式的直觀方法運(yùn)用累加“+=”和C++中冪函數(shù)“pow（）”進(jìn)行求解。
核心for循環(huán){
P（x）+=下標(biāo)為i的系數(shù) * x^i；
}
② C++核心代碼：

double  polynomialsum( int n；double a[]；double x)
{
  double P=0；
  for(int i = 0； i <= n； i++)
      P += a[i] * pow(x,i)；
  return P；
}

③ 算法評(píng)估：直觀累加算法比較直接且容易想到，但是正是因?yàn)槿绱?，?dǎo)致時(shí)間復(fù)雜度太大，為O（xn），為多項(xiàng)式的max次數(shù)，當(dāng)多項(xiàng)式數(shù)據(jù)很大的時(shí)候，算法效率很差。
方法二（類遞歸算法）：
① 核心思想：將已知多項(xiàng)式進(jìn)行化簡(jiǎn)，每一步提出x，并進(jìn)行分離。于是此多項(xiàng)式求和問(wèn)題變成從內(nèi)向外循環(huán)，推導(dǎo)過(guò)程如下：

② 核心for循環(huán){
P（x）=逆序系數(shù)+ x * s；
}
③ C++核心代碼：

double polynomialsum(int n；double a[]；double x)
{
  double P = 0；
  for(int i = n； i >= 0； i--)
    P = a[i] + x * P；
}

④詳細(xì)代碼：

#include<stdio.h>
#include<time.h>
#include<math.h>
clock_t start,stop;
double duration;
#define maxn 10
double f1(int n,double a[],dobule x);
double f2(int n,double a[],dobule x);
int main(){
int i;
double a[maxn]
for(i=0;i<maxn;i++){
a[i]=(double)i;
}
start=clock();
f2(maxn-1,a,1.1);
stop=clock();
duration=((double)(stop-start))/CLK_TCK;
printf(“ticks1=%f\n”,(double)(stop-start));
printf(“duration2=%6.2e\n”,duration);
return 0;
}
double f1(int n , double a[],double x){
int i;
double p=a[n]
for(i=n;i>0;i--){
p=a[i-1]+x*p;
}
return p;
}

⑤ 算法評(píng)估：輸入時(shí)注意要按指數(shù)遞減逆向輸入各個(gè)單項(xiàng)式的系數(shù)（an、an-1…a1、a0），類遞歸算法將復(fù)雜的方法一的時(shí)間復(fù)雜度縮短為線性時(shí)間，算法時(shí)間復(fù)雜度：O（n），是一種比較優(yōu)秀的算法。

2.已知: 有向圖表示由個(gè)用戶結(jié)點(diǎn)組成的網(wǎng)絡(luò). 若結(jié)點(diǎn)相鄰,則可靠性函數(shù)表示從結(jié)點(diǎn)向結(jié)點(diǎn)傳送數(shù)據(jù)成功的概率, ，顯然，從結(jié)點(diǎn)經(jīng)過(guò)結(jié)點(diǎn)向結(jié)點(diǎn)傳送數(shù)據(jù)成功的概率(可靠性值)應(yīng)為. 要求: 設(shè)計(jì)一個(gè)有效算法,求從結(jié)點(diǎn)向該網(wǎng)上其它結(jié)點(diǎn)傳送數(shù)據(jù)的最可靠(即傳送數(shù)據(jù)成功的概率最大)路徑（18分）.

算法設(shè)計(jì)：
（1）核心思路：
結(jié)合最短路徑思想和概率乘法原理，最短路徑選取Floyd算法，再結(jié)合數(shù)理統(tǒng)計(jì)的概率乘積知識(shí)。在有向圖G中的每條邊分別用可靠性函數(shù)r(a,b)來(lái)計(jì)算出結(jié)點(diǎn)a向結(jié)點(diǎn)b傳送數(shù)據(jù)成功的概率來(lái)當(dāng)這條邊的權(quán)值，權(quán)值代表的是概率，權(quán)值為0代表兩個(gè)用戶節(jié)點(diǎn)之間不能傳送數(shù)據(jù)，所以一開始的初始化都賦值為0，自身與自身可以傳送數(shù)據(jù)，然后就是使用Floyd算法找出從結(jié)點(diǎn)s向該網(wǎng)上其他結(jié)點(diǎn)傳送數(shù)據(jù)的最可靠的路徑。
（2）算法思想：
已知網(wǎng)絡(luò)G上各節(jié)點(diǎn)有向路（或路）的完好概率為0<=r(a，b)<=1，下面過(guò)程中出現(xiàn)的頂點(diǎn)設(shè)為S，S1，S2，…Sk，T。設(shè)一條由頂點(diǎn)S到頂點(diǎn)T的有向路（或路）所經(jīng)過(guò)的頂點(diǎn)序號(hào)依次為{S，S1，S2，…Sk，T}，則這條路所經(jīng)過(guò)的各弧的完好概率分別為rss1,rs1s2,…,rskT。這條路的總完好概率rST是它經(jīng)過(guò)的所有?。ɑ蜻叄┩旰酶怕实某朔e。因此，目標(biāo)可以轉(zhuǎn)換為尋找一條使rST取極大值的有向路（或路）的問(wèn)題。在網(wǎng)絡(luò)G中，其完好概率rij有特殊的規(guī)定：當(dāng)i=j時(shí)，rij=1；當(dāng)vivj不屬于E時(shí)，rij=0。從而，可定義的完好概率矩陣A=（rij）n*n，其中rij為頂點(diǎn)vi與vj之間邊的完好概率。當(dāng)網(wǎng)絡(luò)中某兩點(diǎn)不臨接時(shí)，約定其完好概率為0：

這樣所求問(wèn)題就轉(zhuǎn)換成在矩陣A=（rij）nn上找從頂點(diǎn)S至頂點(diǎn)T的最短路徑問(wèn)題。因此最大可靠路徑的算法是最短路徑算法的一個(gè)變種，所以可以使用Floyd標(biāo)號(hào)法由上述矩陣A=（rij）nn來(lái)求出S到T的最短路，從而，所求出的這條最短路徑就是原網(wǎng)絡(luò)的最大可靠路，其可靠概率為rST=exp（-dST），其中dST為矩陣A中從S到T的最短路經(jīng)長(zhǎng).
（3）核心算法：

function [P p f]=p_pathf(A)
[m n]=size(A);
f=0;f=0表示找到路，否則f=1
B=zeros(m,n);
for i=1:m對(duì)原矩陣進(jìn)行轉(zhuǎn)換
    for j=1:n
        if A(i,j)>0&A(i,j)<1
            B(i,j)=-log(A(i,j));
        elseif A(i,j)==0
            B(i,j)=inf;
        end
    end
end
[P d]=Floyd(B);利用Floyd算法求最短路
if d<inf
    p=1;
    for i=1:(length(P)-1)
        p=p*A(P(i),P(i+1));計(jì)算最短路徑的完好概率
    end
    p;
else
    p=0;
    P=0;
    f=1;
end

3.試用動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)一個(gè)算法求解下述人力資源計(jì)劃問(wèn)題（10分） 考慮某企業(yè)有一個(gè)工程必須要在T個(gè)單位時(shí)段內(nèi)完成（每個(gè)單位時(shí)段可以看成是一日、一周或一個(gè)月，這T個(gè)單位時(shí)段稱之為一個(gè)人力資源計(jì)劃周期），這一工程項(xiàng)目每個(gè)時(shí)間段t()對(duì)雇員需求量是，企業(yè)的目標(biāo)是在計(jì)劃周期內(nèi)制定一個(gè)最優(yōu)的招聘或解聘這類雇員的人力資源計(jì)劃，使得在計(jì)劃周期內(nèi)每一個(gè)時(shí)間段中，雇員的人數(shù)能滿足該工程項(xiàng)目對(duì)雇員的需求，并且整個(gè)計(jì)劃期企業(yè)的人力資源費(fèi)用最省。其中： 1）：每一單位時(shí)間段企業(yè)付給每名雇員的工資費(fèi)用； 2）：每招聘一個(gè)雇員的招聘費(fèi)用； 3）：每解聘一名雇員的解聘費(fèi)用； 4）：表示第t個(gè)時(shí)間段企業(yè)中該類雇員的人數(shù)（）； 5）：表示第t個(gè)時(shí)間段末（）招聘該類雇員的人數(shù)（）或解聘該類雇員的人數(shù)（）； 6）在該工程項(xiàng)目開始即計(jì)劃周期開始之前，企業(yè)中該類雇員的人數(shù)是； 7）為了適當(dāng)保留一些雇員以備企業(yè)以后的正常運(yùn)轉(zhuǎn)，為以后的工程項(xiàng)目做準(zhǔn)備，因此在第T個(gè)單位時(shí)段末，不考慮招聘或解聘雇員，即在第T階段雇員的人數(shù)是。 該問(wèn)題的最優(yōu)控制數(shù)學(xué)模型描述如下： t=0,1,2, …，T－1 t=1,2,3, …，T 可以證明該問(wèn)題的最優(yōu)狀態(tài)軌線（即最優(yōu)人力計(jì)劃方案中每一個(gè)時(shí)間段企業(yè)中該類雇員的人數(shù)）滿足，其中。 要求：用動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)一個(gè)求解最優(yōu)控制軌線（招解聘策略方案）和最優(yōu)狀態(tài)軌線的算法，要求：1）寫出其動(dòng)態(tài)規(guī)劃算法的遞歸公式（包括記錄最優(yōu)控制軌線表達(dá)式）；2）用偽代碼寫出算法的具體步驟；3）指出算法的時(shí)間復(fù)雜度；4）用動(dòng)態(tài)規(guī)劃算法計(jì)算計(jì)算下列實(shí)例；5）能否設(shè)計(jì)一個(gè)比動(dòng)態(tài)規(guī)劃效率更高的算法求解該問(wèn)題？若能，寫出該算法并計(jì)算下列實(shí)例。 實(shí)例的參數(shù)見下表: T 15 1 3 4 1 8 t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 5 4 5 6 16 12 5 8 3 4 2 2 8 7

（1）動(dòng)態(tài)規(guī)劃算法的遞歸公式：
對(duì)于人力資源計(jì)劃問(wèn)題（HR planning issues），階段計(jì)劃按計(jì)劃時(shí)間自然劃分，狀態(tài)定義為每階段開始時(shí)的狀態(tài)Xk（t）,決策為每個(gè)時(shí)間階段的人數(shù)Uk（t），記每個(gè)階段的需求量（已知量）為Dk（t），則狀態(tài)轉(zhuǎn)移方程為：

已知：α：每一單位時(shí)間段企業(yè)付給每名雇員的工資費(fèi)用，β：每招聘一個(gè)雇員的招聘費(fèi)用，γ：每解聘一名雇員的解聘費(fèi)用。設(shè)最終公司的雇員人數(shù)描述為：
該問(wèn)題的最優(yōu)控?cái)?shù)學(xué)模型為：

最優(yōu)值函數(shù)：
其中允許決策集合Uk由每階段的最大雇員數(shù)決定。終端條件為：

（2）偽代碼：
① 變量標(biāo)識(shí)：
T：人力資源計(jì)劃。
Xpeople[]：當(dāng)數(shù)組元素為正代表招聘，負(fù)代表解聘。
Demand：每個(gè)時(shí)間段需要的最少人數(shù)。
X0：初始人數(shù)。
XT：終止人數(shù)。
a：每一單位時(shí)間段企業(yè)付給每名雇員的工資費(fèi)用。
b：每招聘一個(gè)雇員的招聘費(fèi)用。
r：每解聘一名雇員的解聘費(fèi)用。
② 核心代碼：

public static void optimum(int T, int[] Demand, int X0, int XT, int a, int b, int r) {
        // 動(dòng)態(tài)規(guī)劃從后往前推
        URecruitment = new int[T + 1];
        // URecruitment[T] = 0;
        XPeople = new int[T + 1];
        XPeople[T] = XT;
        XPeople[0] = X0;
        int DTmax = Math.max(Arrays.stream(Demand).max().getAsInt(), XT);
        int[][] dp = new int[T + 1][Math.max(DTmax, XT) + 1];
        Demand[T] = XT;
        dp[T][XT] = XT * a;
        for (int i = T - 1; i >= 0; i--) {
            int Number = Demand[T - 1];
            if (i == 0) {
                Number = X0;
            }
            int minSub = Integer.MAX_VALUE;
            for (Number = Number; Number <= DTmax; Number++) {
                int sub = XPeople[i + 1] * a + (Number - XPeople[i + 1]) > 0
                        ? (Number - XPeople[i + 1]) * r :
                        (XPeople[i + 1] - Number) * b;
                dp[i][Number] = sub + dp[i + 1][XPeople[i + 1]];
                if (minSub > sub && Number >= Demand[i]) {
                    minSub = sub;
                    URecruitment[i] = XPeople[i + 1] - Number;
                    XPeople[i] = Number;
                }
            }
        }
    }

（3）時(shí)間復(fù)雜度：O（T*M）
（4）運(yùn)行結(jié)果：

（5）創(chuàng)新算法：
對(duì)于本題，我們還可以使用貪心算法去實(shí)現(xiàn)，所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。在動(dòng)態(tài)規(guī)劃算法中，每步所作的選擇往往依賴于相關(guān)子問(wèn)題的解。因而只有在解出相關(guān)子問(wèn)題后，才能作出選擇。而在貪心算法中，僅在當(dāng)前狀態(tài)下作出最好選擇，即局部最優(yōu)選擇。然后再去解作出這個(gè)選擇后產(chǎn)生的相應(yīng)的子問(wèn)題。貪心算法所作的貪心選擇可以依賴于以往所作過(guò)的選擇，但決不依賴于將來(lái)所作的選擇，也不依賴于子問(wèn)題的解。正是由于這種差別，動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行,以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題。
對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的一個(gè)整體最優(yōu)解。通?？梢杂梦覀?cè)谧C明活動(dòng)安排問(wèn)題的貪心選擇性質(zhì)時(shí)所采用的方法來(lái)證明。首先考察問(wèn)題的一個(gè)整體最優(yōu)解，并證明可修改這個(gè)最優(yōu)解，使其以貪心選擇開始。而且作了貪心選擇后，原問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的類似子問(wèn)題。然后，用數(shù)學(xué)歸納法證明，通過(guò)每一步作貪心選擇，最終可得到問(wèn)題的一個(gè)整體最優(yōu)解。其中，證明貪心選擇后的問(wèn)題簡(jiǎn)化為規(guī)模更小的類似子問(wèn)題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-805492.html

到了這里，關(guān)于天津理工大學(xué)研究生學(xué)位課《算法設(shè)計(jì)與分析》期末大作業(yè)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！