算法設計與分析-變治法

1、1 首先是首先是”變變“， 將問題的實例將問題的實例變形，變形，變得更容易求解；變得更容易求解； 思考：和思考：和分治分治與與減治減治的區(qū)別的區(qū)別 然后是然后是”治治“，對問題的實例進行求解。，對問題的實例進行求解。 變治法有三個變形變治法有三個變形: （1）實例化簡）實例化簡同樣問題同樣問題 （2）改變表現(xiàn)）改變表現(xiàn)同樣實例同樣實例 （3）問題化簡）問題化簡另一問題另一問題2 （1）實例化簡）實例化簡同樣問題同樣問題 6.1 預排序預排序 6.2 高斯消去法高斯消去法 6.3 平衡查找樹平衡查找樹AVL樹樹（2）改變表現(xiàn)）改變表現(xiàn)同樣實例同樣實例 6.3 2-3樹樹 6.4 堆和堆排序堆和堆

2、排序 6.5 霍納法則和二進制冪霍納法則和二進制冪（3）問題化簡）問題化簡另一問題另一問題 6.63 列表是列表是有序有序的話，許多關于列表的問題更容易求解。的話，許多關于列表的問題更容易求解。 因此很多問題需要因此很多問題需要先排序先排序，則該問題的時間效率依賴，則該問題的時間效率依賴于排序算法的效率。于排序算法的效率。 回憶前面所學的排序算法：回憶前面所學的排序算法： 插入排序最差插入排序最差(n2) 平均平均 (n2) 最優(yōu)最優(yōu) (n) 快速排序最差快速排序最差(n2) 平均平均(1.38nlog2n) 最優(yōu)最優(yōu)(nlog2n) 合并排序最差合并排序最差(nlog2n)選擇排序選擇排序(

3、n2)冒泡排序冒泡排序(n2)4 例例1、檢驗數(shù)組中元素的唯一性、檢驗數(shù)組中元素的唯一性 蠻力法如何做？時間效率是多少？蠻力法如何做？時間效率是多少？如果先排序，則如何檢查元素的唯一性？如果先排序，則如何檢查元素的唯一性？只需檢查相互緊挨的元素。只需檢查相互緊挨的元素。PresortElementUniqueness(A0.n-1) /先對數(shù)組排序再驗證唯一性先對數(shù)組排序再驗證唯一性 /輸入：數(shù)組輸入：數(shù)組A /輸出：若輸出：若A沒有相等的元素，返回沒有相等的元素，返回“true”,否則返回否則返回“false”. 對數(shù)組排序；對數(shù)組排序； for i=0 to n-2 do if Ai=Ai

4、+1 return false return true整個過程整個過程時間效率時間效率是多少？是多少？5 例例2、模式計算、模式計算 模式：模式：指數(shù)組列表中指數(shù)組列表中出現(xiàn)次數(shù)出現(xiàn)次數(shù)最多的最多的值值。 如如5,1,5,7,6,5,7中中5是模式是模式 所能想到的求模式的方法：所能想到的求模式的方法：用輔助列表列出所有元素及其出現(xiàn)頻率。用輔助列表列出所有元素及其出現(xiàn)頻率。時間效率如何分析？時間效率如何分析？采用排序的思想采用排序的思想先排序后計算相鄰接次數(shù)最多的等值元素。先排序后計算相鄰接次數(shù)最多的等值元素。時間效率如何分析？時間效率如何分析？6 思考：預排序還可以用在什么方面？思考：預排序

5、還可以用在什么方面？ 查找查找 分析順序查找和先排序再查找的時間效率分析順序查找和先排序再查找的時間效率 如果要在同一個列表中進行多次查找，在排序上如果要在同一個列表中進行多次查找，在排序上花費時間是值得的。花費時間是值得的。 課堂練習：課堂練習： 采用合并排序為預排序，折半查找，要做多少次采用合并排序為預排序，折半查找，要做多少次查找才能使得對一個由查找才能使得對一個由n個元素構成的數(shù)組所做個元素構成的數(shù)組所做的預排序是有意義的。的預排序是有意義的。7 預排序的其他應用：預排序的其他應用： 對點排序，拓撲排序對點排序，拓撲排序 課堂練習：課堂練習： P153 4 8 科學計算中通常需要解多個

6、變量的方程組，這些方程組科學計算中通常需要解多個變量的方程組，這些方程組當中最簡單的是線性方程組，也就是變量的次數(shù)均為當中最簡單的是線性方程組，也就是變量的次數(shù)均為1次的。次的。 求解線性方程的方法求解線性方程的方法 有利用高斯有利用高斯消元消元的直接法以及的直接法以及迭代法迭代法。體現(xiàn)的變治的思想：體現(xiàn)的變治的思想： 將方程組變成一個具有特殊性質的方程組將方程組變成一個具有特殊性質的方程組(上三角矩陣上三角矩陣)9 一般的線性方程組是指如下形式的方程組：一般的線性方程組是指如下形式的方程組：11 112 21121 122 2221 12 2n nn nmmmn nma xa xa xba

7、xa xa xba xa xa xb 1011121111212122222212000nnnnnnnnnnaaaaaaaaaaaaaaa 分消元過程和回代過程。消元過程將原方程組變分消元過程和回代過程。消元過程將原方程組變?yōu)樯先欠匠探M，回代過程得到方程組的解。為上三角方程組，回代過程得到方程組的解。1105412321321321xxxxxxxxx 2200333011120333011120111511411122/ 232121232/ 13122rrrrrr1 0 1 123xxx，回代后得12 GaussElimination(A1.n, b1.n) / 輸入：系數(shù)矩陣輸入：系數(shù)矩

8、陣A及常數(shù)項及常數(shù)項 b / 輸出：方程組的增廣矩陣等價的上三角矩陣輸出：方程組的增廣矩陣等價的上三角矩陣 for i=1 to n do Ain+1 =bi for i =1 to n-1 do for j= i+1 to n do for k = i to n+1 do Ajk = Ajk Aik*Aji/Aii13 高斯消元法的效率分析高斯消元法的效率分析 基本操作：乘法基本操作：乘法 執(zhí)行次數(shù)：易見，三重循環(huán)執(zhí)行次數(shù)：易見，三重循環(huán) C(n)(n3)14高斯消去法的高斯消去法的現(xiàn)代商業(yè)實現(xiàn)現(xiàn)代商業(yè)實現(xiàn)是以是以LU分解為基礎分解為基礎的。的。15 05412321321321xxxxxx

9、xxx111114112A12121012001L200330112U系數(shù)矩陣為系數(shù)矩陣為下三角矩陣下三角矩陣L，由主對角線上的，由主對角線上的1以及在高斯消去過程中行的乘數(shù)構成以及在高斯消去過程中行的乘數(shù)構成上三角矩陣上三角矩陣U是消去的結果是消去的結果可觀察出可觀察出兩個矩陣兩個矩陣的乘積的乘積LU等于等于A16記原方程組為記原方程組為 A X =b A=LU 則原方程組為則原方程組為LUX=b其求解轉化為兩個三角形方程組的求解：其求解轉化為兩個三角形方程組的求解： LY=b 下三角方程組下三角方程組 UX=Y 上三角方程組上三角方程組1705 21 3221121211yyyyyy22

10、333 1 2332321xxxxxx與與LY=b, UX=Y對應的方程組如下：對應的方程組如下：易得：易得： (y1,y2,y3)=(1,3,-2), (x1,x2,x3)=(1,0,-1)18 1 一旦的到矩陣一旦的到矩陣A的的LU分解，無論對于什么樣的分解，無論對于什么樣的右邊向量右邊向量b，我們都可以對方程組，我們都可以對方程組Ax=b求解，每求解，每次求一個。次求一個。 2 LU分解不需要額外的存儲空間分解不需要額外的存儲空間19111211112121222212221212100010001nnnnnnnnnnnnaaaxxxaaaxxxaaaxxx 逆矩陣的定義：求矩陣求矩陣

11、A 的逆矩陣，如何轉換的逆矩陣，如何轉換20求矩陣求矩陣 A 的逆矩陣，轉化為求解的逆矩陣，轉化為求解n個方程組個方程組 A Xj =bj 其中，其中， bj是單位矩陣是單位矩陣的第的第j列，而列，而Xj 則是逆矩陣的第則是逆矩陣的第j列。列。10001000121n階矩陣的行列式的計算由遞歸公式定義：階矩陣的行列式的計算由遞歸公式定義： 其中，其中， n=1時，時，det A=a11，若，若j為奇數(shù)，為奇數(shù)，sj=1， 若若j為偶數(shù)，為偶數(shù)，sj=-1例如例如n=3的情形如下：的情形如下：11121322232123212221222311121332333133313231323311 2

12、2 3312 23 3121 32 1331 22 1321 12 3332 23 11aaaaaaaaaaaaaaaaaaaaaaaaaa aa a aa a aa a aa a aa a anjjjAsA1detdet22 按照定義計算高階行列式是不可能的。按照定義計算高階行列式是不可能的。 可利用高斯消元法：可利用高斯消元法： 矩陣矩陣A的行列式的行列式=消元后上三角矩陣的行列式消元后上三角矩陣的行列式 =對角線上元素之乘積。對角線上元素之乘積。例如，上式中例如，上式中 det A=2 3 2=1220033011211111411223 課堂練習：課堂練習： 考慮高斯消去法的反向替換的

13、運行時間效率類型考慮高斯消去法的反向替換的運行時間效率類型是多少？是多少？24二叉查找樹是一種重要的數(shù)據(jù)結構二叉查找樹是一種重要的數(shù)據(jù)結構看書看書p162-163，思考下列問題：，思考下列問題：1 二叉查找樹的特點是？二叉查找樹的特點是？2 在平均情況下，查找，插入，刪除的效率是？在平均情況下，查找，插入，刪除的效率是？3 最差情況是一種什么情況？最差情況是一種什么情況？4 最差情況效率是多少？最差情況效率是多少？25把一個集合變換成一棵二叉查找樹是把一個集合變換成一棵二叉查找樹是改變表現(xiàn)技改變表現(xiàn)技術術的一個實例的一個實例好處是：好處是：在平均情況下，查找，插入，刪除的效率是在平均情況下，查

14、找，插入，刪除的效率是(logn)最差情況下，最差情況下， (n)，退化成線性的情況，退化成線性的情況26 考慮一種既能夠保留經(jīng)典二叉查找樹的好特性考慮一種既能夠保留經(jīng)典二叉查找樹的好特性 又能夠避免它退化到最差情況的數(shù)據(jù)結構又能夠避免它退化到最差情況的數(shù)據(jù)結構 兩種方法：兩種方法： 實例化簡：實例化簡：不平衡二叉查找樹變?yōu)槠胶獾男问讲黄胶舛娌檎覙渥優(yōu)槠胶獾男问?改變表現(xiàn)：改變表現(xiàn)：允許一棵查找樹的單個節(jié)點中不止包允許一棵查找樹的單個節(jié)點中不止包含一個元素。含一個元素。27 看書看書p163,p166回憶及思考下面問題回憶及思考下面問題 1 AVL樹的概念樹的概念 2 AVL樹查找效率與什么

15、相關？樹查找效率與什么相關？ 3 最差情況最差情況28 n個節(jié)點的個節(jié)點的AVL樹的高度樹的高度h 對于隨機鍵的列表構造的對于隨機鍵的列表構造的AVL樹，得到它的平均高度的樹，得到它的平均高度的精確公式被證明是有難度的。精確公式被證明是有難度的。 實驗表明，這個高度大約是實驗表明，這個高度大約是1.01log2n+0.1 在平均情況下，查找一棵在平均情況下，查找一棵AVL樹需要的比較次數(shù)和用折樹需要的比較次數(shù)和用折半查找一個有序數(shù)組是幾乎相同的。半查找一個有序數(shù)組是幾乎相同的。 在最差情況下查找和插入的效率屬于在最差情況下查找和插入的效率屬于(logn) 缺點：缺點： 頻繁的旋轉，維護平衡以及

16、總體上的復雜性頻繁的旋轉，維護平衡以及總體上的復雜性3277. 1)2(log4405. 1log22nhn29 2-3樹是一種樹是一種特殊特殊的高度平衡樹，允許結點的高度平衡樹，允許結點最多最多包含包含兩兩個個關鍵字。兩類結點：關鍵字。兩類結點：2-node、3-node。樹中所有葉子必須位于樹中所有葉子必須位于同一層同一層。k k k2k1,k22-node3-node30 看書理解看書理解 1 搜索算法搜索算法p167 2 插入算法插入算法p16831 搜索算法搜索算法 如果待搜索樹的根是如果待搜索樹的根是2-node型結點，搜索操作型結點，搜索操作與二叉搜索樹搜索操作相同；與二叉搜索樹

17、搜索操作相同； 如果待搜索樹的根是如果待搜索樹的根是3-node型結點，最多只需型結點，最多只需要比較兩次就可以知道是搜索成功還是需要向要比較兩次就可以知道是搜索成功還是需要向3棵子樹繼續(xù)遞歸搜索?？米訕淅^續(xù)遞歸搜索。32 插入算法：插入算法： 當一個結點當一個結點x需要插入到需要插入到2-3樹中的時候，總是根據(jù)它樹中的時候，總是根據(jù)它的大小關系，把其插入到葉結點中。的大小關系，把其插入到葉結點中。 插入前首先調用搜索算法找到待插入的葉結點，如插入前首先調用搜索算法找到待插入的葉結點，如果該葉結點是果該葉結點是2-node型的，則直接插入即可；型的，則直接插入即可； 如果該葉結點是如果該葉結點

18、是3-node型的，在按序插入到葉結點后，型的，在按序插入到葉結點后，需要把葉結點拆分（因為插入后使得葉結點的關鍵需要把葉結點拆分（因為插入后使得葉結點的關鍵字個數(shù)為字個數(shù)為3，不滿足，不滿足2-3樹的要求）。樹的要求）。 拆分過程首先在三個關鍵字挑選值在中間的關鍵字，拆分過程首先在三個關鍵字挑選值在中間的關鍵字，提到上一層，或者作為新結點，或者插入原來的內提到上一層，或者作為新結點，或者插入原來的內結點中；關鍵字最小的作為左子樹，關鍵字最大的結點中；關鍵字最小的作為左子樹，關鍵字最大的作為右子樹。如果內結點的插入導致結點過大，按作為右子樹。如果內結點的插入導致結點過大，按照上述規(guī)則繼續(xù)拆分。

19、照上述規(guī)則繼續(xù)拆分。33 操作效率與什么相關？操作效率與什么相關？ 樹高樹高h 若有若有n個關鍵字，構成一棵全部由個關鍵字，構成一棵全部由2節(jié)點構成的滿樹，節(jié)點構成的滿樹，n與與h之間之間的關系為？的關系為？ 若有若有n個關鍵字，構成一棵全部由個關鍵字，構成一棵全部由3節(jié)點構成的滿樹，節(jié)點構成的滿樹，n與與h之間之間的關系為？的關系為？ 所以高度的范圍是：所以高度的范圍是： 無論在最差還是平均，查找，插入和刪除時間效率都是對數(shù)類型無論在最差還是平均，查找，插入和刪除時間效率都是對數(shù)類型1=124221hhn1) 1(log1) 1(log23nhn1=2 1 2 3 .2 32(1 3 . 3

20、 )31hhhn 34 看書看書p170-p173回憶及理解回憶及理解 1 堆的定義堆的定義 2 堆的構建方法堆的構建方法 3 自底向上構造法的時間效率自底向上構造法的時間效率 4 自頂向下構造法的時間效率自頂向下構造法的時間效率 5 堆中刪除元素的算法堆中刪除元素的算法35 1 堆的定義堆的定義 堆是一棵二叉樹，樹中節(jié)點包含鍵，滿足下堆是一棵二叉樹，樹中節(jié)點包含鍵，滿足下面兩個條件：面兩個條件： 樹的形狀：二叉樹樹的形狀：二叉樹 父母：每個節(jié)點的鍵都要大于或等于它子女父母：每個節(jié)點的鍵都要大于或等于它子女的鍵。的鍵。36首先把數(shù)組按序填充到堆中各個結點首先把數(shù)組按序填充到堆中各個結點然后按照

21、自下而上，從右至左的順序，從最后的父然后按照自下而上，從右至左的順序，從最后的父母節(jié)點開始，到根為止，檢查這些節(jié)點的值是否母節(jié)點開始，到根為止，檢查這些節(jié)點的值是否都滿足子結點比父結點小的約束條件。都滿足子結點比父結點小的約束條件。如果不滿足則調換父子結點的位置，然后再檢查在如果不滿足則調換父子結點的位置，然后再檢查在新的位置上，是不是滿足父母優(yōu)勢要求。新的位置上，是不是滿足父母優(yōu)勢要求。用自底向上法為用自底向上法為1，8，6，5，3，7，4構造一個堆構造一個堆37 最壞情況最壞情況 每個位于樹的第每個位于樹的第i層的鍵都會移動到葉子層層的鍵都會移動到葉子層h中中 移動到下一層需要進行幾次比較

22、？移動到下一層需要進行幾次比較？ 兩次。位于第兩次。位于第i層的鍵移到葉子層層的鍵移到葉子層h需要幾次比較？需要幾次比較？ 需要需要2(h-i)次鍵值比較。次鍵值比較。 因此有下式：因此有下式： 結論結論:一個規(guī)模為一個規(guī)模為n的堆只需不到的堆只需不到2n次比較就能構造完次比較就能構造完成成 10210i)1(log(22)(2)(2)(hiihiworstnnihihnC層的鍵第38 將包含新鍵將包含新鍵K附加在當前堆的最后一個葉子后面附加在當前堆的最后一個葉子后面 將新鍵和父母比較交換將新鍵和父母比較交換 這個鍵向上走，直到它不大于它的父母為止這個鍵向上走，直到它不大于它的父母為止用自頂向

23、下法為用自頂向下法為1，8，6，5，3，7，4構造一個堆構造一個堆 思考一個新鍵插入思考一個新鍵插入i個元素構成的堆的比較次數(shù)個元素構成的堆的比較次數(shù) N個規(guī)模問題的比較次數(shù)個規(guī)模問題的比較次數(shù)39 只考慮刪除根中的鍵只考慮刪除根中的鍵 把待刪除結點與堆中最后一個鍵把待刪除結點與堆中最后一個鍵K對調。對調。 執(zhí)行刪除操作并把堆的大小減一。執(zhí)行刪除操作并把堆的大小減一。 對刪除后的堆進行調整直到滿足堆的約束條件。對刪除后的堆進行調整直到滿足堆的約束條件。 刪除的效率分析：刪除的效率分析： 取決于交換和規(guī)模減一后，樹的取決于交換和規(guī)模減一后，樹的堆化堆化所需的鍵值所需的鍵值比較次數(shù)。比較次數(shù)。 因

24、為鍵值比較次數(shù)不可能超過堆的高度的兩倍，因為鍵值比較次數(shù)不可能超過堆的高度的兩倍，刪除的時間也是屬于對數(shù)類型的。刪除的時間也是屬于對數(shù)類型的。 40 堆排序主要包括兩個步驟：堆排序主要包括兩個步驟： (1)對于給定的數(shù)組構造相應的堆。對于給定的數(shù)組構造相應的堆。 (2)對所構造的堆執(zhí)行對所構造的堆執(zhí)行n-1次刪除堆的根結點的操次刪除堆的根結點的操作，把刪除得到的結點保存在給定數(shù)組中。作，把刪除得到的結點保存在給定數(shù)組中。 41 用堆排序對數(shù)組用堆排序對數(shù)組2，9，7，6，5，8排序排序 步驟步驟1：構造堆：構造堆 2,9,7,6,5,8 2,9,8,6,5,7 2,9,8,6,5,7 9,2,

25、8,6,5,7 9,6,8,2,5,742 步驟步驟2：刪除根結點：刪除根結點 9,6,8,2,5,7 7,6,8,2,5 8,6,7,2,5 5,6,7,2 7,6,5,2 2,6,5 6,5,2 5,2 2 43 1 構造堆的效率是多少？構造堆的效率是多少？ O(n) 2 刪除最大鍵及后續(xù)的效率刪除最大鍵及后續(xù)的效率 O(nlogn) 評價：評價： 堆排序不需任何額外的存儲空間堆排序不需任何額外的存儲空間 針對隨機文件的實驗指出，堆排序比快速排序運針對隨機文件的實驗指出，堆排序比快速排序運行的慢，但和合并排序還是有競爭力的。行的慢，但和合并排序還是有競爭力的。44 實例化簡實例化簡-AVL

26、樹樹 查找效率最壞查找效率最壞 平均平均 改變表現(xiàn)改變表現(xiàn)-2-3樹樹 查找效率最壞，平均查找效率最壞，平均 堆堆 兩種構造方法的效率兩種構造方法的效率 刪除的效率刪除的效率 堆排序堆排序 效率效率456.5.1 Horner法則法則 計算計算n次多項式的值的算法。次多項式的值的算法。 例如，例如，n=4, 直接計算，需要多少次乘法？直接計算，需要多少次乘法？ 4+3+2+1=10=n(n-1)/2次乘法，次乘法， 用如下用如下Horner/秦九韶算法只需要秦九韶算法只需要4=n次乘法：次乘法：5) 1) 3) 12( 532)(234xxxxxxxxxp465) 1)3) 12( 532)(

27、234xxxxxxxxxp當當x=3時，計算時，計算p(x)系數(shù)系數(shù)2-131-5X=3223+(-1)=553+3=18518+1=55553+(-5)=160霍納法則的有趣特性霍納法則的有趣特性該算法在計算該算法在計算p(x)在某些點在某些點x0上的值所產(chǎn)生的上的值所產(chǎn)生的中間數(shù)字中間數(shù)字恰好可以恰好可以作為作為p(x)除以除以x-x0的商的系數(shù)的商的系數(shù)，而算法的最后結果，除了等于，而算法的最后結果，除了等于p(x0)以外，還等于這個除法的余數(shù)。以外，還等于這個除法的余數(shù)。即，當即，當x0=3時時 p(x)=2x4-x3-3x2+x-5 除以除以x-3為為2x3+5x2+18x+55 和

28、和 16047 6.5.2 二進制冪二進制冪 計算計算an的算法，有兩種方法：的算法，有兩種方法： n的二進制中間結果1101aa2*a=a3(a6)2*a=a13(a2)2=a6n的二進制中間結果1101aaa*a4=a5a5*a8=a13a8a4a2a2i的值48問題化簡是一個重要的解題策略問題化簡是一個重要的解題策略如解析幾何的根本思想是把幾何問題化為代數(shù)問如解析幾何的根本思想是把幾何問題化為代數(shù)問題題49原問題：原問題： 求能夠被求能夠被m和和n整除的最小整數(shù)記為整除的最小整數(shù)記為lcm(m,n)常用算法：常用算法： m和和n所有公共質因數(shù)乘以所有公共質因數(shù)乘以m的不在的不在n中的質因

29、數(shù)，中的質因數(shù)，再乘以再乘以n不在不在m中的質因數(shù)中的質因數(shù) 24=2223 60=2235 lcm(24,60)=(223)25=120缺陷：缺陷： 需要連續(xù)素數(shù)的表需要連續(xù)素數(shù)的表50關聯(lián)關聯(lián) m和和n的的最大公約數(shù)最大公約數(shù)gcd(m,n)是是m和和n所有公共質所有公共質因子的積。因子的積。并且并且lcm(m,n)=mn/gcd(m,n)問題化簡問題化簡 轉換為求最大公約數(shù)轉換為求最大公約數(shù)gcd(m,n)的高效的歐幾里德的高效的歐幾里德算法算法51原問題：原問題： 計算圖中兩個頂點之間的路徑數(shù)量計算圖中兩個頂點之間的路徑數(shù)量問題化簡：問題化簡： 可利用鄰接矩陣，可以證明：可利用鄰接矩陣

30、，可以證明： 圖圖G中頂點中頂點vi到頂點到頂點vj之間長度為之間長度為k的路徑數(shù)的路徑數(shù)量等于量等于AK的第的第(i,j)個元素個元素，其中，其中A是圖是圖G的的鄰接矩陣。鄰接矩陣。52原問題：原問題： 求函數(shù)的最大值或最小值求函數(shù)的最大值或最小值 問題化簡：問題化簡： 已知函數(shù)的最大值的算法已知函數(shù)的最大值的算法 求其最小值求其最小值 min f(x)=-max-f(x) 函數(shù)最優(yōu)化：函數(shù)最優(yōu)化： 把最優(yōu)化問題轉化為函數(shù)極值問題，再由把最優(yōu)化問題轉化為函數(shù)極值問題，再由 f(x)=0求臨界點。求臨界點。53許多許多決策優(yōu)化問題決策優(yōu)化問題可以轉化為可以轉化為線性規(guī)劃線性規(guī)劃問題。問題。例子

31、：進行例子：進行1億美元的投資。該筆錢分成億美元的投資。該筆錢分成3種類型種類型的投資：股票、債券和現(xiàn)金。預期收益各是的投資：股票、債券和現(xiàn)金。預期收益各是10%，7%，3%。并且投資在股票上的資金不能超過債。并且投資在股票上的資金不能超過債券的券的1/3，現(xiàn)金投資至少相當于股票和債券投資，現(xiàn)金投資至少相當于股票和債券投資總額的總額的25%。這筆投資如何才能最大化收益？。這筆投資如何才能最大化收益？54線性規(guī)劃問題是一個線性規(guī)劃問題是一個多變量線性函數(shù)多變量線性函數(shù)的最優(yōu)化問的最優(yōu)化問題。題。這些變量要滿足的約束是以這些變量要滿足的約束是以線性等式線性等式或或線性不等線性不等式式的形式出現(xiàn)。的

32、形式出現(xiàn)?？梢詾楦鞣N應用建模，如排班，交通和通信網(wǎng)絡可以為各種應用建模，如排班，交通和通信網(wǎng)絡規(guī)劃，石油勘探和提純。規(guī)劃，石油勘探和提純。解線性規(guī)劃問題的算法：解線性規(guī)劃問題的算法： 單純形法單純形法 Karmarkar算法算法55 整數(shù)線性規(guī)劃問題：把變量的值限定在整數(shù)。整數(shù)線性規(guī)劃問題：把變量的值限定在整數(shù)。 目前還沒有一個已知的多項式級的求解算法。目前還沒有一個已知的多項式級的求解算法。56 許多問題用圖表示后，求解很容易。通常用圖的許多問題用圖表示后，求解很容易。通常用圖的頂頂點點表示問題的表示問題的狀態(tài)狀態(tài)，邊邊表示狀態(tài)之間的可能表示狀態(tài)之間的可能轉變轉變。表。表示問題的圖稱為示問題的圖稱為狀態(tài)空間圖狀態(tài)空間圖。 例如例如過河問題過河問題： 一個農(nóng)夫希望用一條小船把一只一個農(nóng)夫希望用一條小船把一只狼狼，一頭，一頭羊羊，一籃，一籃白菜白菜從河的北岸渡到河的南岸，由于船小只能夠容納從河的北岸渡到河的南