深謀遠慮以空間換取時間 中央大學資工系 江振瑞 教授

Presentation on theme: "深謀遠慮以空間換取時間 中央大學資工系 江振瑞 教授"— Presentation transcript:

1 深謀遠慮以空間換取時間 中央大學資工系 江振瑞 教授
動態規劃演算法 深謀遠慮以空間換取時間 中央大學資工系 江振瑞 教授 計畫周密而思慮深遠。《文選．賈誼．過秦論》：「深謀遠慮，行軍用兵之道。非及曩時之士也。」《西遊記．第二○回》：「大王深謀遠慮，說得有理。」也作「深謀遠猷」、「深圖遠慮」。 相似詞：深圖遠慮、深思熟慮相反詞：輕舉妄動、鼠目寸光 再說秦國的天下，既不小，也不弱。雍州肥沃的土地，殽山、函谷關的險固，還是和以前一樣。陳涉的地位，沒有比從前齊、楚、燕、趙、韓、魏、宋、衛、中山各國國君尊貴；鋤柄木杖，比不上鉤戟長矛的銳利；被流放充軍的士兵，也比不上九國的正規軍隊；深謀遠慮，行軍用兵的方法，也比不上昔日那些謀士將領。但是成敗不同，功業恰恰相反。假使把從前殽山之東的各國，來和陳涉比較長短大小，較量權勢力量，那簡直不可相提並論了。想當年秦國以小小的地方，千乘之國的力量，取得天下八州，使同等地位諸侯都向他稱臣，經過一百多年，然後才能把天下合併為一家，把殽山函谷關當作宮室；不料只有一個人起來發難，竟然宗廟被毀，君主死在敵人手中，為天下人所譏笑，這是什麼緣故呢？只因為今秦以武力取得天下，亦欲以武力治天下，而不施行仁義，不知取天下和守天下的形勢是完全不同的啊！（指取天下用武力，而治天下需用仁義。） 原文: 且夫天下非小弱也，雍州之地，崤函之固，自若也；陳涉之位，非尊於齊、楚、燕、趙、韓、魏、宋、衛、中 山之 君也；鋤櫌（音｜ㄡ；用來鏟平田地或擊碎石塊的農具）棘矜（棘，通「戟」；矜，矛柄） 非銛（ㄒ｜ㄢ；鋒利、銳利）於鉤戟長鎩（ㄕㄚ；長矛）也；謫戍之眾，非抗（可抗衡）於九國之師也；深謀遠慮，行軍用兵之道，非及曩時之士也；然而成敗異變，功業相反。試使山東之國，與陳涉度長絜（圍而量之）大，比權量力，則不可同年而語矣（陳勝的弱小實力與昔日的六國強大國力相比，簡直不可同日而語）；然秦以區區之地，致萬乘之權，招八州而朝同列，百有餘年矣；然後以六合為家，崤函為宮，一夫作難（陳涉撐竿而起）而七廟墮（指秦亡國），身死人手，為天下笑者，何也？仁義不施，而攻守之勢異也。 過秦論（上） 賈誼 　原文＆翻譯 09, Mar :55 過秦論（上） 賈誼  Tony私選的古文觀止 秦孝公據崤函之固，擁雍州之地，君臣固守，以窺周室；有席卷天下，包舉宇內（宇宙之內；指天下），囊括四海之意，並吞八荒（天下）之心。當是時也，商君佐之，內立法度，務耕織，修守戰之具，外連衡而鬥諸侯。於是秦人拱手而取西河之外。 孝公既沒，惠文、武、昭襄蒙故業。因遺策，南取漢中，西舉巴蜀，東割膏腴之地，北收要害之郡。諸侯恐懼，會盟而謀弱秦，不愛珍器重寶肥饒之地，以致天下之士，合從締交，相與為一。當此之時，齊有孟嘗，趙有平原，楚有春申，魏有信陵；此四君者，皆明智而忠信，寬厚而愛人，尊賢重士，約從離橫，兼韓、魏、燕、趙、齊、楚、宋、衛、中山之眾。於是六國之士，有寧越、徐尚、蘇秦、杜赫之屬為之謀；齊明、周最、陳軫、昭滑、樓綏、翟景、蘇厲、樂毅之徒通其意；吳起、孫臏、帶佗、兒良、王廖、田忌、廉頗、趙奢之倫制其兵。嘗以十倍之地，百萬之眾，叩關而攻秦。秦人開關延敵（迎敵），九國之師，逡巡（ㄑㄩㄣ　ㄒㄩㄣˊ；徘徊不前）遁逃而不敢進。秦無亡矢遺鏃之費，而天下諸侯已困矣。於是從散約解，爭割地而賂秦。秦有餘力而制其敝，追亡逐北，伏尸百萬，流血漂櫓（漂起的盾牌）；因利乘便，宰割天下，分裂河山，強國請服，弱國入朝。施及孝文王、莊襄王，享國日淺，國家無事。 及至秦王（秦始皇），續六世之餘烈，振長策而御宇內，吞二周而亡諸侯，履至尊而制六合，執捶拊（ㄔㄨㄟˊ　ㄈㄨˇ；一種鞭打的刑具。）以鞭笞天下，威振四海，南取百越之地以為桂林、象郡；百 越之 君，俯首繫頸，委命下吏；乃使蒙恬北築長城而守藩籬，卻匈奴七百餘里；胡人不敢南下而牧馬，士不敢彎弓而報怨。於是廢先王之道，焚百家之言，以愚黔首（百姓）；墮（ㄏㄨㄟ；破壞、毀壞）名城，殺豪俊，收天下之兵，聚之咸陽，銷鋒鍉（ㄉ｜ˊ；箭鏃、箭頭），鑄以為金人十二，以弱天下之民。然後踐華（華山）為城，因河（黃河）為池，據億丈之城（指華山），臨不測之谿（ㄑ｜；指黃河）以固。良將勁弩，守要害之處；信臣精卒，陳利兵而誰何？（誰敢怎樣？形容秦之強大）天下已定，秦王之心，自以為關中之固，金城千里，子孫帝王萬世之業也。 秦王既沒，餘威震於殊俗（風俗不同的遠方蠻夷）。然而陳涉，甕牖繩樞（甕牖，音ㄨㄥˋ　｜ㄡˇ；破甕為窗；繩樞，繩繫戶樞窗；形容貧窮人家）之子，甿隸（甿，音ㄇㄥˊ；田夫；隸，奴隸）之人，而遷徙之徒也，才能不及中人，非有仲尼、墨翟之賢，陶朱、猗頓之富，躡足（踏足）行伍之間，而倔起（奮起）阡陌之中，率罷散之卒，將數百之眾，轉而攻秦；斬木為兵，揭竿為旗，天下雲集而響應，贏糧（擔著量）而景從（影從），山東豪俊，遂並起而亡秦族矣。 且夫天下非小弱也，雍州之地，崤函之固，自若也；陳涉之位，非尊於齊、楚、燕、趙、韓、魏、宋、衛、中 山之 君也；鋤櫌（音｜ㄡ；用來鏟平田地或擊碎石塊的農具）棘矜（棘，通「戟」；矜，矛柄） 非銛（ㄒ｜ㄢ；鋒利、銳利）於鉤戟長鎩（ㄕㄚ；長矛）也；謫戍之眾，非抗（可抗衡）於九國之師也；深謀遠慮，行軍用兵之道，非及曩時之士也；然而成敗異變，功業相反。試使山東之國，與陳涉度長絜（圍而量之）大，比權量力，則不可同年而語矣（陳勝的弱小實力與昔日的六國強大國力相比，簡直不可同日而語）；然秦以區區之地，致萬乘之權，招八州而朝同列，百有餘年矣；然後以六合為家，崤函為宮，一夫作難（陳涉撐竿而起）而七廟墮（指秦亡國），身死人手，為天下笑者，何也？仁義不施，而攻守之勢異也。 from :古雅臺語人        秦孝公憑著殽山和函谷關的險固，坐擁雍州肥沃的土地，君臣上下一同伺機謀奪周朝的政權；有奪取天下，征服各國，統一四海的志向，併吞八方的野心。在這個時侯，商鞅輔佐他，在內政上，建立法律制度，專力發展農耕和紡織，整修攻守的裝備；在外交上，採用聯橫政策，使諸侯自相格鬥。於是，秦人輕易的取得了西河以外的土地。      秦孝公死後，惠文王、武王、昭襄王，繼承故舊的基業，遵照前人的策略，向南兼并了漢中，向西攻佔巴蜀，東邊割取了肥沃的土地，北邊占有險要的州郡。諸侯們都感到恐懼，會商聯盟，準備削弱秦國。不惜用珍奇的器物、貴重的財寶和肥美的土地，來招攬天下賢才，締結合縱的盟約，合成一體，聯合抗秦。在這個時候，齊國有孟嘗君，趙國有平原君，楚國有春申君，魏有信陵君；這四位公子，都是聰明睿智而且忠誠信實，寬容厚道而且愛護人民，又能尊敬賢士，他們約定合縱，來拆散連橫，會同韓、魏、燕、趙、齊、楚、宋、衛、中山九國的軍隊。那時，六國的賢士，有寧越、徐尚、蘇秦、杜赫這些人替各國謀劃；有齊明、周最、陳軫、昭滑、樓緩、翟景、蘇厲、樂毅這些人溝通各國的意見；有吳起、孫臏、帶佗、兒良、王廖、田忌、廉頗、趙奢這些人統率各國的軍隊。曾經以十倍於秦的土地，上百萬的兵力，進擊函谷關，攻打秦國。秦國的軍隊開關迎戰，九國的軍隊，都疑懼退卻，爭相逃亡而不敢前進。秦國沒有耗費一矢一鏃，天下的諸侯卻已經疲勞困頓了。於是合從的盟約解散了，各國爭相割地來賄賂秦國。秦國因此而有餘力制服疲憊的諸侯們，追逐那些逃亡敗北的軍隊，橫在地上的死屍多到百萬，流的血可以漂起盾牌。秦國藉著這有利的形勢，良好的時機，宰割天下諸侯，分裂諸侯的土地，於是強國請求降服，弱國入朝稱臣，傳到孝文王、莊襄王，在位當權的日子短，國家沒有什麼大事。      到了秦始皇，發揮了六世累積下來的功業，揮動長鞭以駕御天下，併吞東西二周，滅亡各國諸侯，登上皇帝的寶座，控制了上下四方，拿著刀杖，奴役天下人民，威風震動四海。向南佔領百越的土地，改為桂林、象郡。百越的君主都俯首稱臣，投降請罪，把生命交給獄吏處置。又派蒙恬到北方修築長城，防衛邊疆，擊退匈奴七百多里，讓胡人不敢南下來侵略，胡兵也不敢拉弓放箭來報仇。於是廢除先王的聖道，燒燬百家的書籍，來實施愚民政策。毀壞名城，殺戮天下英雄豪傑，沒收天下的兵器，聚集在咸陽，溶化刀茅箭頭，鑄造成十二個金人，以削弱民間的武力。然後以華山做城墎，把黃河當做護城河，憑據這樣的億丈高城，臨靠如此不測的深水，作為堅固的屏障。再加上優秀的將帥，強勁的弓弩，防守在險要的地方；親信的臣子，精銳的士卒，擺出鋒利的武器，又有誰敢怎麼樣呢？天下已經平定，秦始皇的心中，自以為關中的堅固，真像圍繞千里的金城，可以作為子孫萬世做皇帝的基業了。              秦始皇死後，遺留的聲威還可以使遠方的蠻夷震懼。然而陳涉，只不過是一個用破甕做窗、用草繩繫門軸的窮苦弟子，是個替人種田的僕役，是個被配發充軍的人，才能還比不上中等之人，沒有孔子、墨子的賢能，也沒有陶朱、猗頓的富裕。置身在軍隊之間，興起於田野之中，率領著疲憊散亂的士卒，帶領著數百人馬，反過來攻打秦國。砍伐樹木做兵器，高舉竹竿做旗誌，天下人像雲一樣聚集，應聲而起，挑著糧食，如影隨形般跟著他，殽山以東的英雄豪傑，就一齊起來將秦國消滅了。      再說秦國的天下，既不小，也不弱。雍州肥沃的土地，殽山、函谷關的險固，還是和以前一樣。陳涉的地位，沒有比從前齊、楚、燕、趙、韓、魏、宋、衛、中山各國國君尊貴；鋤柄木杖，比不上鉤戟長矛的銳利；被流放充軍的士兵，也比不上九國的正規軍隊；深謀遠慮，行軍用兵的方法，也比不上昔日那些謀士將領。但是成敗不同，功業恰恰相反。假使把從前殽山之東的各國，來和陳涉比較長短大小，較量權勢力量，那簡直不可相提並論了。想當年秦國以小小的地方，千乘之國的力量，取得天下八州，使同等地位諸侯都向他稱臣，經過一百多年，然後才能把天下合併為一家，把殽山函谷關當作宮室；不料只有一個人起來發難，竟然宗廟被毀，君主死在敵人手中，為天下人所譏笑，這是什麼緣故呢？只因為今秦以武力取得天下，亦欲以武力治天下，而不施行仁義，不知天下和守天下的形勢是完全不同的啊！（指取天下用武力，而治天下需用仁義。） From:

2 動態規劃演算法基本概念

3 動態規劃解題策略(1) 動態規劃演算法(dynamic programming algorithm)使用動態規劃策略(dynamic programming strategy)解決問題。它將原問題分解成一系列子問題(subproblems)，並依序解決子問題來解決原問題。為避免一再地解重複的子問 題，一旦解出子問題的解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，即直接從表格中取出其解答以節省計算時間，是一個「系統化」的、「節省不必要計算」的、「以空間換取時間」的演算法。 一個動態規劃演算法一般先解出最簡單的子問題，並以一定的程序持續運行直至求出原問題解答為止。

4 動態規劃解題策略(2) 動態規劃演算法將一個問題P分解為一系列的子問題P1 , P2, …, Pn-1, Pn，並作出一系列的決策D1, D2, …, Dn-1, Dn來解決問題。 若先完成i個到第j個(1ijn)決策(也就是Di, …, Dj)，則D1, …, Dj-1與Dj+1, …,Dn必須基於Di, …, Dj所產生的結果才可以得到問題的最佳解。這表示決策間必定有遞迴關係。

5 動態規劃與貪婪演算法之比較 比較: 二者都是透過一系列的決策以解決問題，但是有以下的不同點:
在貪婪演算法中，任何決策都是獨立(independent)的，都只要考慮區域最佳解(locally optimal)。這些區域最佳解最後會加成為全域最佳解(globally optimal solution)。 在動態規劃演算法中，決策是相依的(dependent)。每個決策必須考慮其他決策所產生的結果才能求得全域最佳解(globally optimal solution)。

6 使用動態規劃解題策略的演算法 最長共同子序列演算法 最大連續子序列和動態規劃演算法 0/1 背包動態規劃演算法 子集合加總演算法
最小編輯成本演算法 多階圖最小成本路徑演算法 Bellman-Ford最短路徑演算法 Floyd-Warshall最短路徑演算法 矩陣鏈乘積演算法 最佳二元搜尋樹演算法

7 最長共同子序列演算法

8 最長共同子序列 以下我們說明最長共同子序列(Longest common subsequence, LCS or LCSS)相關背景知識
令X為一個由若干符號依序排列組成的序列(sequence)，則X的子序列(subsequence)為從X刪除0個或多個符號(不必要為連續性的)的序列 例: 令X = b a c a d，則ad, ac, bac, acad, bacad, bcd等與空序列都是A的子序列 例: 序列X = b a c a d 與 Y = a c c b a d c b 的共同子序列(common subsequence)有: ad, ac, bac, acad等 例: 序列X與Y的最長共同子序列(longest common subsequence)為: a c a d

9 最長共同子序列應用: DNA序列比對 DNA = {A|C|G|T}* (A: 腺嘌呤; C: 胞嘧啶; G: 鳥嘌呤; T: 胸腺嘧啶)
S1=ACCGGTCGAGTGCGGCCGAAGCCGGCCGAA S2=GTCGTTCGGAATGCCGTTGCTGTAAA Q: S1與S2是否為相似的DNA序列? A: 這問題可以由找出S1與S2的最長共同子序列來解決。 腺嘌呤（A） 胸腺嘧啶（T） 胞嘧啶（C） 鳥嘌呤（G）

10 最長共同子序列應用: 化身路徑群組 化身路徑群組(Avatar Path Clustering):
由於相似的個性，興趣或習慣，網路虛擬環境(Networked Virtual Environment, NVE)或巨量多人線上遊戲(Massively Multiplayer Online Game, MMOG)的用戶或化身(avatar)可能具有相似的行為模式，導致在虛擬世界中有著類似的化身路徑。 我們希望將類似的化身歸類為一個群組，並為他們找到代表性路徑(representative path, RP)。 參考論文: Jehn-Ruey Jiang, Ching-Chuan Huang, and Chung-Hsien Tsai, “Avatar Path Clustering in Networked Virtual Environments," in Proc. of the 4th International Workshop on Peer-to-Peer Networked Virtual Environments (P2PNVE 2010), 2010. 下圖來源: Huiguang Liang, Ransi Nilaksha Silva, Wei Tsang Ooi, Mehul Motani, “Avatar mobility in user-created networked virtual worlds: measurements, analysis, and implications,” Multimedia Tools and Applications, v.45 n.1-3, p , October 2009. In order to verify the proposed avatar path clustering method in NVE, the study refers to the movement data of avatars gathered by [6] from Second Life. Second Life has a number of avatar motion paths on different regions. Each Region is the 256x256(unit2) of the virtual world, the AOI range of avatar is 16(unit). Each record includes avatar location data in the region within 24 hours(as seen in Figure 5). Data format for each location data includes date, time, user ID, and avatar location. Interval for data collection is approximately 10 seconds. Thus, the motion path of avatars is composed of a data series. The gathered avatar location data [6] is from the free will of players in the virtual world. This enabled it to correspond best with the actual avatar movements in NVE.

11 最長共同子序列應用: 化身路徑群組(續) 在第二人生(Second Life, SL)贈品島(Freebies Island)的兩條路徑有多相似？

12 最長共同子序列應用: 化身路徑群組(續) 將化身路徑轉為序列:
將虛擬世界切割為方格(grid cell)，並針對化身路徑每隔固定時間取樣，找出其所在方格編號形成序列。 In LCSS-DC, the entire virtual world is divided into numbered square cells whose length is of the AOI diameter. According to the cell numbers that the sample points of a path resides in, the path is represented by a sequence of cell numbers. Note that consecutive identical cell numbers in the sequence will be merged to be one number. For example, in Figure 3(a), path A is represented as <60, 61, 62, 63, 55, 47, 39, 31, 32>, and path B, <60, 61, 62, 54, 62, 63, 64>. C60.C61.C62.C63.C55.C47.C39.C31.C32 首先我們將整個虛擬環境切割成數塊長寬(假設每個使用者擁有相同且固定的AOI半徑下，長度設定成AOI直徑，使得使用者的視野有重疊)相等的格子，每一個格子都有它的代號，而每一條路徑從開始到結束依序跨越數個不同的格子，我們在路徑跨越到不同的格子的時候為路徑序列增加一個格子代號，因此每一條路徑都可以以格子的代號當作序列的元素來表示 SeqA:C60.C61.C62.C63.C55.C47.C39.C31.C32

13 最長共同子序列應用: 化身路徑群組(續) 找出兩條路徑對應的最長共同子序列以衡量其相似程度。
SeqA :C60.C61.C62.C63.C55.C47.C39.C31.C32 SeqB :C60.C61.C62.C54.C62.C63.C64 LCSSAB :C60.C61.C62. C63 找出兩條路徑對應的最長共同子序列以衡量其相似程度。 After using LCSS algorithm to calculate the length of the paths, clustering is performed. LCSS-DC uses a pair of similar path thresholds THa and THb, instead of the similar path radius used in ADOCP-DC, as parameters of clustering. Path Pi takes path Pj as its similar path if Eqs. (3) and (4) are satisfied. In Eqs. (3) and (4), Seqi and Seqj are the cell sequences of Pi and Pj, respectively, and LCSSij is the longest common subsequence of Seqi and Seqj, and SSeqji is the sub-sequence of path Pj containing the whole LCSSij. Like ADOCP-DC, LCSS-DC also adopts the density-based clustering mechanism for clustering paths. When a path has many enough similar paths, it is regarded as a core path and become a candidate of representative paths. Note that the similarity relationship between two paths is asymmetric. To take paths in Figure 3(a) as examples, path B may take path A as a similar path, but not vise versa. The asymmetry is to avoid the case that dissimilar paths appear in the cluster. For example, if path A in Figure 3(b) considers both paths B and C to be similar, then path A is likely to be the representative path of the cluster covering paths A, B and C. It is obvious that such a cluster contains two very dissimilar paths, B and C.

14 最長共同子序列問題 以下我們定義最長共同子序列(Longest Common Subsequence, LCS)問題：
給定兩個序列X = <x1,x2,...,xm>, Y = <y1,y2,...,yn>，找出X和Y的最長共同子序列長度

15 最長共同子序列問題 暴力法時間複雜度 產生序列X(或Y)的所有子序列，然後檢查每個子序列是否也是序列Y(或X)的子序列，然後儲存下最長的子序列並輸出。複雜度為: n * 2m = O(2m) 或 m * 2n = O(2n ) Q1: 如何產生一個序列的所有子序列? Q2: 如何檢查一個序列是否為另一個序列的子序列?

16 最長共同子序列問題 子問題的遞迴關係 ì ï c [ i , j ] = í c [ i - 1 , j - 1 ] + 1 x =y ï
我們定義Xi = < x1,x2,...,xi >及Yj = <y1,y2,...,yj>。令c [i, j]是Xi 和Yj 的LCS的長度，則我們有以下遞迴關係: ì if i= or j= ï c [ i , j ] = í c [ i - 1 , j - 1 ] + 1 if i,j> and x =y i j ï max{ c [ i , j - 1 ], c [ i - 1 , j ]} if i,j> and x y î i j

17 最長共同子序列演算法 Algorithm 最長共同子序列演算法
Input: 兩個序列X = <x1,x2,...,xm>, Y = <y1,y2,...,yn> Input: X和Y的最長共同子序列長度 1 m  length[X] 2 n  length[Y] 3 for i  1 to m do 4 c[i, 0]  0 5 for j  1 to n do 6 c[0, j]  0

18 7 for i  1 to m do for j  1 to n do if xi = yj then c[i, j]  c[i-1, j-1]+1 b[i, j]  “” //for both i-1 and j-1 else if c[i–1, j]  c[i, j-1] then c[i, j]  c[i-1, j] b[i, j]  “” //for i-1 else c[i, j]  c[i, j-1] b[i, j]  “” //for j-1 only 17 return c and b

19 最長共同子序列演算法 執行範例 X=ABCBDAB Y=BDCABA

20 最長共同子序列演算法 時間複雜度 行7的外層for迴圈一共有m次迭代 行8的內層for迴圈一共有n次迭代 行9-16的if敘述需要常數時間
因此總時間複雜度為O(mn) ，而非暴力法的 O(2m)或 O(2n)

21 最長共同子序列演算法 如何找出最長共同子序列
PRINT_LCS(b, X, i, j ) 1 if i = 0 or j = 0 then 2 return 3 if b[i, j] = “” then 4 PRINT_LCS(b, X, i-1, j-1) 5 print xi 6 else if b[i, j] = “” then 7 PRINT_LCS(b, X, i-1, j) 8 else PRINT_LCS(b, X, i, j-1) 時間複雜度: O(m+n) 藉由呼叫PRINT_LCS(b, X, length[X], length[Y])函數來印出 LCS

22 最大連續子序列和動態規劃演算法

23

24

25 多階圖最小成本路徑演算法

26 多階圖最小成本路徑問題 (multi-stage graph minimum-cost path problem)
多階圖G=(V,E) 是有向圖(directed graph)，其節點被分割成 k2 個兩兩互斥集(disjoint sets) Pi,1 i  k。 此外，若<x,y>是E的邊，則xPi 且 yPi+i ,1 i <k，每個邊都有一個加權(weight)wi,i+1 (或稱為成本或距離)。 其中集合 P1 和 Pk 都僅包含一節點(node or vertex)。 多階圖問題是要找出從 P1 中的源點(source)s 到Pk中的標點(target) t 的最小成本路徑(minimum-cost path)。 每一個集合Pi ,1 i  k被定義為圖中的第i階(stage)。

27 貪婪演算法無法解決 多階圖最小成本路徑問題
例如： 貪婪演算法無法解決此問題: S A D T = 23. 最短路徑為: S C F T = 9. 就像分期買商品一樣，都分三期付款，最終都可以得到商品的產權。有的付款方式第一期要繳1萬，有的要繳2萬，有的要繳5萬。但是依照不同的第一期繳法，則在第二期甚或第三期都有不同的繳款選擇，而造成繳款總額的不同。 就像買房子一樣，分三期付款，最終都可以得到房子的產權。有的付款方式第一期要繳1萬，有的要繳2萬，有的要繳5萬。但是依照不同的第一期繳法，則在第二期甚或第三期都有不同的繳款選擇，而造成總繳款數的不同。

28 動態規劃遞迴關係 (1) d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)}

29 動態規劃遞迴關係 (2) d(A, T) = min{4+d(D, T), 11+d(E, T)}

30 動態規劃遞迴關係 (3) (下式省略邊界條件值d(T, T)=0)
d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18. d(C, T) = min{ 2+d(F, T) } = 2+2 = 4. d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9.

31 解決多階圖最小成本路徑問題的動態規劃演算法
Algorithm 多階圖最小成本路徑演算法 Input:具n個頂點(vertices)的k階多階圖G(V, E), 其中V= i=1..k Pi , PiPj= for ij, P1={s},Pk={t}, <x,y>E (xPi  yPi+i), <x,y>的權重為w[x,y] Output: path[1..k], d[s]，其中path[1..k]紀錄第1階(節點1)到第k階(節點n)的最 小成本路徑，d[s]紀錄最小成本路徑總成本 d[t]=0; d[x]= for xt; //陣列d[x]儲存節點x到標點t的最小距離(distance) for ik-1 to 1 do //由第k-1階到第1階 for every node x in Pi do for every edge (x, y)E do //實作d[x]=min(x,y)E {w[x,y]+d[y]} if (d[x]>w[x,y]+d[y]) do d[x]=w[x,y]+d[y] next[x]=y //代表在最短路徑中節點x的下節點為y path[1]=s;path[k]=t; //path[j]表示路徑中第j階的節點 for j2 to k-1 do path[j]next[path[j-1]]; return path[s],d[s]

32 Bellman-Ford 最短路徑演算法

33 Bellman-Ford最短路徑演算法介紹
與Dijkstra演算法相同，Bellman-Ford演算 法也是屬於求取單一源節點至全部終節點 的一至全最短路徑演算法。 但是與Dijkstra演算法不同的是，Bellman- Ford演算法可以檢查圖是否有負加權循環 (cycle)，因此在具有負加權(negative weight)邊的圖也可以正確的執行。

34 Bellman-Ford最短路徑演算法介紹(續)
Bellman-Ford最短路徑演算法採用動態規劃策略解 決問題。一開始在第1次迭代先求出所有屬於1-邊 路徑(1-edge path)的最短路徑，並將其最短路徑距 離儲存在陣列中；然後基於這個儲存結果在第2次 迭代針對每個邊，由始點(starting node)往外調整到 止點(ending node)的最短路徑距離，可以得出所有 屬於2-邊路徑(2-edge path)的最短路徑；…。依此 類推則在第n-1次迭代可以求出所有屬於(n-1)-邊路 徑((n-1)-edge path)的最短路徑。因為具n個節點的 圖最長的路徑具有n-1個邊，因此第n-1次迭代求出 的路徑已經是最終的正確結果了。

35 Bellman-Ford最短路徑演算法 Algorithm Bellman-Ford最短路徑演算法
Input: 給定一個加權有向圖(weighted digraph)G=(V, E)，及一個來源(source)節點s。G各邊的加權值以w[x][y]表示，其中x 及y為邊的二個節點。 Output: 對每一個頂點u而言，傳回一個由s到u的最短路徑距離(累積邊加權)d[u]。 d[s]←0; d[u]←∞ for each u≠s for i←1 to |V|-1 do for 每一個G的邊(u, x)　do if d[x] > d[u] + w[u][x] then d[x]← d[x] + w[u][x] for 每一個G的邊(u, x) do //檢查有無負循環(negative-weight cycle) if d[x] > d[u] + w[u][x] then return false //代表有負循環，無法產生正確結果 return d

36 Bellman-Ford最短路徑演算法複雜度
假設G一共有n個節點，m個邊(也就是|V|=n, |E|=m) 行2-5的外層for迴圈一共有n-1次迭代 行3-5的內層for迴圈一共有m次迭代 行4-5為內層if指令，針對每個邊(u, x)依據目前的d[u]值調整d[x] 行6-7的for迴圈在求出(n-1)邊路徑之後再針對每個邊(u, x)依據目前的d[u]值調整d[x]，若有任何調整產生則表示有一個n邊路徑(也就是循環) 因此總時間複雜度為行2-5的外層for迴圈n-1次迭代次數與 行3-5的內層for迴圈m次迭代相乘得O(n  m)= O(|V|  |E|)

37 Bellman-Ford最短路徑演算法 執行範例
(a)是初始狀態，(b)是first iteration之後的狀況，(c)跟(d)類推。 塗成藍色的虛線邊是對應的Predecessor graph所有的邊， 點內的數字代表d[v]，是現存最短路徑， 綠色的點代表已經將該點的所有邊Relax過了。

38 Floyd-Warshall 最短路徑演算法

39 Floyd-Warshall最短路徑演算法介紹
與Dijkstra演算法與Bellman-Ford演算法不同的是， Floyd-Warshall演算法可以求出全部節點配對的最 短路徑，是一個全配對最短路徑(all-pair shortest path)演算法。 Floyd-Warshall演算法可以處理有負邊的圖，但是 不能用以檢查有負迴圈的圖。

40 Floyd-Warshall最短路徑演算法介紹(續)
Floyd-Warshall演算法採用動態規劃策略解決問題，利用一個n×n(n為節點總數)的二維陣列d來記錄每一節點配對間的最短路徑成本或距離(distance) 。 在啟始(initial)狀況時， d[i][j]=w[i][j]，for each i and j。 (w[i][j]=0，for i=j; w[i][j]=, for (i, j)E; w[i][j]=the weight of (i, j) for (i, j) E) Floyd-Warshall演算法執行時會不斷的更新陣列d。在第k次更新陣列d時，表示d中所紀錄的最短路徑是經由編號小於或等於k的節點當作中間節點所造成的。因此，當第n次更新陣列d時，則表示d中所紀錄的最短路徑是可以經由所有節點當作中間節點所造成的，這也就是演算法所需要的結果。

41 Floyd-Warshall最短路徑演算法
Algorithm Floyd-Warshall最短路徑演算法 Input：G為一個加權圖有向(weighted digraph)， G中各邊的加權值以w[x][y]表示，x 及y為邊的二個頂點。 Output：G中的每一個節點配對的最短路徑距離d[x][y]，及對應的路徑前節點p[x][y]，其中x及y為邊的二個節點 d[i][j]w[i][j], for each i and j P[i][j]i, for each i and j for(k←1 to n) do //假設節點的編號由1至n for(i←1 to n) do for(j←1 to n) do if (d[i][j]>d[i][k]+d[k][j]) d[i][j]←d[i][k]+d[k][j] p[i][j]←p[k][j] return d, p

42 Floyd-Warshall演算法討論 可以使用一個前節點陣列(predecessor matrix)p紀錄每個節點在最短路徑上的前節點。初始化p[i,j]時，若i=j或(i,j)∉E則初始為NIL()，否則初始為i。 等執行完演算法後，則可藉由前節點陣列來建立出由任意節點到其他任意節點的最短路徑。

43 Floyd-Warshall最短路徑演算法範例: 陣列初始化
s a b c d 6  3 2 4 1 5 d[i][j] s a b c d  p[i][j] G(V, E)

44 Floyd-Warshall最短路徑演算法複雜度
假設G一共有n個節點(也就是|V|=n) 行3的外層for迴圈一共有n次迭代 行4的中層for迴圈一共有n次迭代 行5的內層for迴圈一共有n次迭代 行6-8的if敘述的執行為常數時間 因此總時間複雜度為O(n3)=O(|V|3)

45 矩陣鏈乘積演算法

46 矩陣鏈乘積 (matrix-chain product)
Q: 如何以最少的純量(scalar)乘法，算出A1…An的矩陣鏈乘積? A: 加上括號指定計算矩陣乘積最佳順序 舉例:

47 二個矩陣相乘的演算法 MATRIX MULTIPLY(A,B) 1 if columns[A] rows[B]
2 then error “不相容的矩陣大小” 3 else for to rows[A] for to columns[B] 5 for to columns[A] 7 8 return C

48 二個矩陣相乘時間複雜度: 假設 A 是一個 的矩陣，B 是一個 的矩陣， 那個 A x B 的時間複雜度為 。

49 矩陣相乘執行順序非常關鍵 假設 是個 的矩陣, 是一個 的矩陣, 是一個 的矩陣。 那麼算出 需要 次的純量相乘。 然而算出 卻需要

50 矩陣鏈乘積問題 (matrix-chain product problem)
給定一長度為n的矩陣鏈 ，對於i=1,2,…,n而言，矩陣Ai 的維度為 pi-1pi。找出一種方式對 進行完全括號(fully parenthesized)以最少的純量乘法求出矩陣鏈乘積。 若一個矩陣鏈乘積為完全括號，則其包含單一矩陣或為兩個完全括號矩陣鏈乘積的相乘。 Given a chain of n matrices, where for i=0,1,…,n, matrix Ai has dimension pi-1pi, fully parenthesize the product in a way that minimizes the number of scalar multiplications. A product of matrices is fully parenthesized if it is either a single matrix, or a product of two fully parenthesized matrix product, surrounded by parentheses.

51 矩陣鏈乘積問題 窮舉所有不同的括號方式: 不同括號方式總數相當於將矩陣鏈在第k個矩陣之後與第k+1個矩陣之前，使用括號分為二組後再計算其結果，而1kn-1。我們可得: 實際上，P(n)為卡塔蘭數(Catalan number)=Cn-1 =O(2n)

52 卡塔蘭數(Catalan number) 卡塔蘭數是以比利時的數學家歐仁查理卡塔蘭(Eugène Charles Catalan, 1814–1894)命名。 卡塔蘭數的一般項公式為 

53 矩陣鏈乘積演算法解題思維 步驟1:找出子問題切割方式
Step 1: The structure of an optimal parenthesization

54 矩陣鏈乘積演算法解題思維步驟 2: 找出子問題遞迴關係
定義 m[i, j]= 計算 所需的最小相乘數。 目標為求得 m[1, n]

55 矩陣鏈乘積演算法解題思維步驟 3: 以表格儲存計算過的資訊
與其一再地遇到相同問題而重複遞迴求解，取而代之地我們利用一表格化的(tabular)、由下而上(bottom-up)的方式來計算最低成本。 過程利用一輔助表格m[1..n, 1..n] 來紀錄最小成本m[i, j] ，並利用另一個輔助表格s[1..n, 1..n]來記錄哪一個指標 k 造就了m[i, j]的最小成本。 Step 3: Computing the optimal costs Instead of computing the solution to the recurrence recursively, we compute the optimal cost by using a tabular, bottom-up approach. The procedure uses an auxiliary table m[1..n, 1..n] for storing the m[i, j] costs and an auxiliary table s[1..n, 1..n] that records which index of k achieved the optimal cost in computing m[i, j].

56 矩陣鏈乘積演算法MATRIX_CHAIN_ORDER
MATRIX_CHAIN_ORDER(p) 1 n  length[p] –1 2 for i  1 to n 3 do m[i, i]  0 4 for l  2 to n 5 do for i  1 to n – l + 1 6 do j  i + l – 1 m[i, j]   for k  i to j – 1 9 do q  m[i, k] + m[k+1, j]+ pi-1pkpj if q < m[i, j] then m[i, j]  q s[i, j]  k 13 return m and s 時間複雜度:

57 例子:

58 在n=6時， MATRIX-CHAIN-ORDER所計算出的
m 與 s 表格

59 m[2,5]= min{ m[2,2]+m[3,5]+p1p2p5= 1520=13000, m[2,3]+m[4,5]+p1p3p5= 520=7125, m[2,4]+m[5,5]+p1p4p5= 1020=11374 } =7125

60 印出最佳括號方式 PRINT_OPTIMAL_PARENS(s, i, j) 1 if i=j 2 then print “A”i
3 else print “(“ PRINT_OPTIMAL_PARENS(s, i, s[i,j]) PRINT_OPTIMAL_PARENS(s, s[i,j]+1, j) print “)” 例:

61 最小編輯成本演算法

62 最小編輯成本 (Minimum Edit Cost, MEC)問題
也稱為最小編輯距離 (Minimum Edit Distance, MED)問題 給定字串A=a1a2…am及字串B=b1b2...bn, MEC問題是要找到成本最低的一連串的編輯操作將字串A轉為字串B。可以使用的操作及其成本如下所述: 操作1: 由字串A刪除一個字元 (Cost1) 操作2: 在字串A插入一個字元 (Cost2) 操作3: 在字串A將一個字元換成另一個字元 (Cost3)

63 最小編輯成本 (Minimum Edit Cost, MEC)問題 (cont.)
MEC問題可以使用動態規劃演算法解決，在陣列c[i, j]中儲存將A的子字串a1a2...ai 轉為B的子字串b1b2...bj 的最小成本，其中 0  i  m 且 0  j  n。 c[i, j]的遞迴關係及其邊界條件是動態規劃演算法的設計核心。

64 最小編輯成本 (Minimum Edit Cost, MEC)問題 (cont.)
c[i, j]的遞迴關係 a1a2...ai  b1b2...bj 𝑐 𝑖, 𝑗 = 𝑐 𝑖−1, 𝑗− 𝑖𝑓 𝑎 𝑖 = 𝑏 𝑗 𝑚𝑖𝑛 𝑐 𝑖−1, 𝑗 +Cost 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑐 𝑖, 𝑗−1 +Cost 𝑐 𝑖−1, 𝑗−1 +Cost3

65 最小編輯成本 (Minimum Edit Cost, MEC)問題 (cont.)
c[i, j]的邊界條件 c[m, n] 就是解答 a1a2...ai  Null Null  b1b2...bj 𝑐 𝑖,0 =𝑖×cost1 , 𝑓𝑜𝑟 0≤𝑖≤𝑚 𝑐 0,𝑗 =𝑗×cost2 , 𝑓𝑜𝑟 0≤𝑗≤𝑛

66 最佳二元搜尋樹演算法

67 最佳二元搜尋樹 Optimal binary search trees
給定一個有n個不同鍵(key)的已排序的序列(sorted sequence)K=<k1,k2,…,kn>，其中k1<k2<…<kn，而且每個鍵ki都伴隨著一個可能被搜尋機率pi (1in)；另外，有些搜尋無法在K中的鍵找到，因此，還有n+1個假鍵(dummy key) d0,d1,d2,…,dn，其中d0代表所有小於k1的鍵，dn代表所有大於kn的鍵，而其他鍵di則代表介於ki與ki+1的鍵。每個假鍵di都伴隨一個機率qi (0in)。 如何在上述的給定條件下，建立一個最佳二元搜尋樹(optimal binary search tree)，使其具有最小期望搜尋成本(smallest expected search cost)。

68 最佳二元搜尋樹 Optimal binary search trees
cost:2.75 最佳!! cost:2.80

69 預期成本 在T中搜索的預期成本是 根(root)的深度(depth)為0

70 最佳二元搜尋樹的期望搜索成本

71 最佳化二元搜尋樹的結構 考慮一個二元搜索樹的任意子樹。它必須包含在一個連續範圍鍵 ki, ...,kj(1  i  j  n)。此外，包含鍵值 ki, ..., kj的一個子樹也必須包含假鍵di-1, ..., dj為它的葉節點。 如果一個最佳化二元搜尋樹T 有一個子樹T’包含鍵值ki, ...,kj ，那麼對於鍵ki, ...,kj和假鍵di-1, ..., dj所對應的子問題而言，子樹T’必須是最佳化的。

72 期望搜索成本 令e[i, j]代表一個包含鍵ki,…,kj與假鍵di-1,…,dj最佳二元搜尋樹的期望搜索成本，其中i1，jn，ji-1。 我們最終想要求出e[1, n]。 可以直接求得的起始值為e[i, i-1]=qi-1，因為e[i, i-1]代表一個僅包含假鍵di-1最佳二元搜尋樹的期望搜索成本。

73 遞迴解 (recursive solution)
j j = + w ( i , j ) å p å q 令  w[i, j] = w[i, j – 1] + pj+qj l l l = i l = i - 1 如果包含ki,…,kj的最佳化樹的根位於kr ，那麼 e[i, j]=pr+(e[i, r-1]+w(i, r-1))+(e[r+1, j]+w(r+1, j)) = - + + + e [ i , r 1 ] e [ r 1 , j ] w ( i , j)

74 遞迴解 (recursive solution)
q if j = i - 1, ì i - 1 e [ i , j ] = í min { e [ i , r - 1 ] + e [ r + 1 , j ] + w ( i , j )} if i j . î i r j

75 最佳二元搜尋樹演算法OPTIMAL-BST
OPTIMAL-BST(p,q,n) 1 for i  1 to n + 1 2 e[i, i – 1]  qi-1 3 w[i, i – 1]  qi-1 4 for l  1 to n 5 for i  1 to n – l + 1 j  i + l – 1 e[i, j]   w[i, j]  w[i, j – 1] + pj+qj

76 9 for r  i to j t  e[i, r –1]+e[r +1, j]+w[i, j] if t < e[i, j] then e[i, j]  t root[i, j]  r 14 return e and root OPTIMAL-BST 演算法時間複雜度 (n3)

77 OPTIMAL-BST計算表格(陣列)e[i,j], w[i,j], 及root[i,j]的過程

78 0/1 背包動態規劃演算法

79 0/1 背包問題 0/1 knapsack problem
n個物品， 帶著重量 w1, w2, , wn, 值 (利潤) v1, v2, , vn, 背包載重容量 (capacity) W, 欲最大化 , 限制條件為  W, xi = 0 or 1, 1in。 (令 S={1,…,n}且T={i | xi=1}S)

80 暴力法解決方案 (brute force solution)
0/1背包問題(或簡稱背包問題)是一個最佳化問題(optimization problem)。 我們可以一一試過S集合所有2n個子集合來解這問題，其時間複雜為O(2n)。 問題: 有任何解決方案比暴力法更好嗎? 回答: 有。我們可以利用動態規劃(dynamic programming, DP) ，用空間(表格或陣列)以換取時間(trade space for time)。

81 表格(陣列) 我們建構一個陣列V[0..n, 0..W]。
元素V[i, w], 1in, 且 0wW, 將儲存來自物品1,2,…,i的任何子集合的最大合併價值，而這些物品的合併重量為w。 如果我們可以計算陣列中的所有元素，那麼元素V[n, W]儲存的值為物品1,2,…,n中的任一子集合，此子集合中的物品可以放入容量W的背包中，而具有最大的合併價值。

82 遞迴關係 初始化設定(initial settings): V[0, w]=0 for 0wW
若wiw，則 V[i, w]=max(V[i-1, w], vi+V[i-1, w-wi]) 否則，V[i, w]=V[i-1, w] for 0in and 0wW

83 使用迭代(iteration)而非遞迴(recursion) 由下而上(bottom-up)計算V[i, w]
由下而上的計算：逐行的計算表格，使用

84 超多項式時間：O(c^f(n))，其中c為大於1的常數，f(n)大於常數，小於線性。
時間複雜度：O(nW)

85 備註： 最後的輸出為: 這方法並沒有告訴我們最佳解是由哪個S={1,2,3,4}的子集合所產生的(在這個例子中為子集合{2,4})

86 前面提到的用於計算V[i, w]的演算法，並沒有記錄那些物品所形成的子集合可以形成最佳解。
為了計算出實際形成最佳解的子集合，我們增加一個輔助的布林陣列keep[i, w]，若第 i 個物品在子集合中，則設其值為 1，否則設其值為 0。

87 若 keep[n, W]為1，則 n∈𝑇，我們可以重複這種討論來計算 keep[n-1, W-wn]
因此，以下的碼可以輸出T中的元素。

88

89 0/1背包決策問題是經典的NPC問題。 (0/1背包問題是經典的NP-hard問題)。
解0/1背包問題的DP演算法時間複雜度為O(nW) 這是多項式時間嗎? 時間複雜度O(nW)是偽多項式時間(pseudo-polynomial time)。

90 子集合加總演算法

91

92

93 多項式及偽多項式時間 多項式時間(polynomial time): 計算時間T(n)不大於問題規模n的多項式。也就是T(n)=O(nk)，k為常數。 偽多項式時間(pseudo-polynomial time): 如果時間複雜度是輸入數值(numeric value of the input)的多項式，但卻是輸入長度(the length of the input)的指數函數，那麼稱其為偽多項式時間。 深層定義: 一個問題的輸入規模(input size)為將整個輸入表達出來的位元數(The size of the input to a problem is the number of bits required to write out that input.) Source: The size of the input to a problem is the number of bits required to write out that input. For example, if the input to a sorting algorithm is an array of 32-bit integers, then the size of the input would be 32n, where n is the number of entries in the array.   If you use something like selection sort to do this, the runtime, as a function of the number of input elements in the array, will be O(n2). But how does n, the number of elements in the input array, correspond to the the number of bits of input? As mentioned earlier, the number of bits of input will be x = 32n. Therefore, if we express the runtime of the algorithm in terms of x rather than n, we get that the runtime is O(x2), and so the algorithm runs in polynomial time. Things break down, however, when we start talking about algorithms that operate on numbers. Let's consider the problem of testing whether a number is prime or not. Given a number n, you can test if n is prime using the following algorithm: function isPrime(n): for i from 2 to n - 1: if (n mod i) = 0, return false return true So what's the time complexity of this code? Well, that inner loop runs O(n) times and each time does some amount of work to compute n mod i (as a really conservative upper bound, this can certainly be done in time O(n3)). Therefore, this overall algorithm runs in time O(n4) and possibly a lot faster. Unfortunately, we don't. Remember, the formal definition of time complexity talks about the complexity of the algorithm as a function of the number of bits of input. Our algorithm runs in time O(n4), but what is that as a function of the number of input bits? Well, writing out the number n takes O(log n) bits. Therefore, if we let x be the number of bits required to write out the input n, the runtime of this algorithm is actually O(24x), which is not a polynomial in x.

94 弱NPC問題 與 強NPC問題 一個具有偽多項式時間複雜度的NPC問題稱之為弱NPC問題(weakly NPC problem)。
若一個NPC問題被證明除非P=NP，不然不可能有偽多項式時間複雜度的解，則稱之為強NPC問題(strongly NPC problem)。 背包問題是弱NPC問題。子集合加總問題(subset sum problem)也是弱NPC問題。 強NP-hard問題與弱NP-hard問題也可以同樣的方式定義。

95 The End