《可視化計算》第章基本算法和策略(B)

.,第3章基本算法和策略PARTB,可視化計算,.,2,基本策略,算法設(shè)計過程中，發(fā)現(xiàn)問題、分析問題及解決問題的思路、步驟與其他學(xué)科中的方法是一致的，就是尋找規(guī)律計算機科學(xué)家在算法研究過程中總結(jié)了一些具有普遍意義的算法策略和一些可循的規(guī)律，能夠幫助我們較快地找到算法,.,3,基本策略,貪心策略分治策略回溯策略動態(tài)規(guī)劃將遞歸算法轉(zhuǎn)成非遞歸實現(xiàn),.,4,貪心策略,貪心算法在對問題求解時，總是做出在當前看來是最好的選擇，因此它僅僅是某種意義上的局部最優(yōu)解但在相當廣泛范圍內(nèi)，對許多問題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解“鼠目寸光”是對貪心算法的最好描述,.,5,貪心算法的特點,以當前情況為基礎(chǔ)根據(jù)某個偏好原則作最優(yōu)選擇，而不考慮各種可能的整體情況省去了為尋找最優(yōu)解要窮盡所有可能而必須耗費的大量時間采用自頂向下,以迭代的方法做出相關(guān)的貪心選擇每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題,.,6,貪心算法的特點,通過每一步貪心選擇,可得到問題的一個局部最優(yōu)解但由此得到的全局解卻不一定都是是最優(yōu)的,.,7,求解數(shù)字三角形,有任意一個數(shù)字三角形，只能自第一層(頂層)向下行走,且只能走下接的相鄰兩個結(jié)點如第三層的1只能走第四層的3或1問能否找到一條路徑，使得路徑上的權(quán)值之和最大？,.,8,貪心法求解的算法設(shè)計,使用文件保存三角形的層數(shù)和所有數(shù)據(jù)描述一個n層的三角形，需要(n*（n+1）)/2個數(shù)據(jù)和一個描述層次的數(shù)據(jù);使用二維數(shù)組a，保存數(shù)字三角形的所有數(shù)據(jù)二維數(shù)組的大小為N*N，當然，其中有一半的元素為空值0;,.,9,貪心法求解的算法設(shè)計,使用line，colum兩個變量在二維數(shù)組中，作為數(shù)字定位的指針；x作為保存權(quán)值累計的變量；line的值同時用來控制路徑行走的循環(huán),.,10,流程圖,.,11,分治策略,分治法（DivideandConquer）的基本思想是，將一個較大規(guī)模的問題分解為若干個較小規(guī)模的子問題，找出子問題的解，然后把各個子問題的解合并,從而得到整個問題的解分治法的分（Divide）是指將較大的問題劃分為若干個較小的問題，然后用遞歸法求解子問題；分治法的治（Conquer）是指從小問題的解來構(gòu)建大問題的解,.,12,分治策略,分治法算法中至少包含有兩次遞歸過程，只有一個遞歸過程的算法在嚴格意義上不能算作分治算法,.,13,求用分治法進行冪運算降序求解,在公鑰加密的RSA算法中將高次冪運算轉(zhuǎn)換為低次冪運算可以加快加密和解密的計算過程，從而提高了RSA算法的運算速度算法一：采用遞推循環(huán)的方式實現(xiàn)類似a*b的計算過程；算法二：采用遞歸方式實現(xiàn)分治算法：a*b=(a*a)*(b/2)b=偶數(shù)a*b=a*(a*(b-1)b=奇數(shù),.,14,分治法的計算效率,以求520為例，使用分治方法與不使用分治方法的遞歸算法比較，分治法可以節(jié)省近三分之二時間,.,15,分治方法乘冪運算流程圖,.,16,回溯策略,如果問題的規(guī)模（數(shù)量）是按指數(shù)速度增加的，那么這些算法的能力將受到一定的限制在這種情況下，回溯法（Backtracking）也許是一個更好的選擇回溯法也叫窮盡搜索法（Brute-ForceSearch），其基本思想是嘗試分步地去解決一個問題,.,17,現(xiàn)有n種物品，對1=i=n，已知第i種物品的重量為正整數(shù)Wi，價值為正整數(shù)Vi，背包能承受的最大載重量為正整數(shù)W現(xiàn)要求找出這n種物品的一個子集，使得子集中物品的總重量不超過W且總價值盡量大,0-1背包問題的數(shù)學(xué)描述,.,18,設(shè)有物件n項，重量為w(5,3,2),價值v(9,7,8)，如果背包只能裝5斤，求可以放背包的物品最大價值。使用回溯算法，決策樹的建樹過程為：深度有限，左側(cè)優(yōu)先，左側(cè)分支不取東西，右側(cè)取當前物件,0-1背包問題求解,（3，5，0）,（2，3，8）,（2，5，0）,（1，2，7）,（1，5，0）,（1，3，8）,i：紅色，表示物品的編號aw：綠色，當前可用空間V：藍色，當前物品價值,（1，0，15）,（-，3，8）,（-，5，0）,（-，0，9）,（-，2，7）,（-，-3，16）,（-，-2，17）,.,19,k元組的概念,元組(tuple)是一種有窮序列，k個元素的序列稱為k元組。與集合不同，集合不考慮元素的順序，但元組中的元素有嚴格的順序規(guī)定在0-1背包問題中的決策樹中的元素和重量為w(5,3,2),價值v(9,7,8)，皆為三元組k元組的概念在下一章的有限狀態(tài)機和圖靈機中還會用到,.,20,0-1背包回溯算法的main子圖,建議測試案例從簡單的方案開始,.,21,0-1背包問題-回溯法求解流程圖,.,22,0-1背包回溯算法說明,Maxvalue是一個遞歸實現(xiàn)的子程序，其中的主要傳遞參數(shù)如下：w：項目物體的重量數(shù)組v：項目物體的價值數(shù)組length_of(w)：重量數(shù)組的長度，也是最后一個物件下標，遍歷循環(huán)的開始點，直到第一個元素max_weight：背包的最大容量：最后的返回值，即背包中物體的價值,.,23,動態(tài)規(guī)劃,計算Fibonacci數(shù)列的第n項：當項數(shù)大于2時，F(xiàn)（n）=F（n-1）+F（n-2）如果計算Fibonacci數(shù)列第n項，這需要計算從第3項到第n-1項隨著n值的增大，遞歸解法的算法時間復(fù)雜性會按幾何級數(shù)增長這類問題的關(guān)鍵是子問題（sub-problem）有重疊，因而分治法并不適合于此類問題的求解,.,24,動態(tài)規(guī)劃,基本思想是：如果一個較大問題可以被分解為若干個子問題，并且子問題有重疊，那么，可以將每個子問題的解存放到一個表中，然后通過查表來解決問題，減少不必要的重復(fù)計算動態(tài)規(guī)劃是20世紀50年代美國數(shù)學(xué)家RichardBellman提出的在這個術(shù)語中，Programming與編程沒有關(guān)系，而是規(guī)劃和設(shè)計的意思,.,25,動態(tài)規(guī)劃解Fibonacci數(shù)列第n項,.,26,算法說明,算法遞歸子程序中的三個傳遞參數(shù)的作用分別是：a：第n項的輸入?yún)?shù)b：第n項的結(jié)果輸出c：計算過程中的中間結(jié)果存留數(shù)組（也就是一個線形表）在計算過程中，每次計算的結(jié)果都保存在c數(shù)組中，出現(xiàn)重疊子問題時，直接到c數(shù)組中調(diào)取結(jié)果,.,27,動態(tài)規(guī)劃的分析,要消除計算過程中的重復(fù)性過程，動態(tài)規(guī)劃是比較好的選擇這也是計算機科學(xué)中，進行問題求解的重要途徑之一由于動態(tài)規(guī)劃需要保存中間計算結(jié)果，勢必占用較大的內(nèi)存空間（這點貪心法就完全不同），但時間復(fù)雜性則會降低這就是所謂“空間換時間“的策略,.,28,動態(tài)規(guī)劃的分析,動態(tài)規(guī)劃與貪心法不同的地方，它是一種最優(yōu)化算法當所有的解空間可以遍歷的前提下，利用動態(tài)規(guī)劃的思想保存所有可能的解再通過比較就可以得到最優(yōu)的解實現(xiàn)原理非常簡單，但非常實用，也是計算機科學(xué)中最常用的算法策略請設(shè)計使用動態(tài)規(guī)劃求解數(shù)字三角形,.,29,將遞歸算法轉(zhuǎn)成非遞歸的實現(xiàn),遞歸是計算機科學(xué)中非常重要的概念，其主要優(yōu)點是遞歸的代碼量比非遞歸的代碼量少，算法可以設(shè)計的非常簡潔這是由于遞歸所使用的方式是函數(shù)調(diào)用這在計算機算法實現(xiàn)中屬于非常自然的棧結(jié)構(gòu)不需要記錄位置信息，不需要添加控制語句這些工作都由函數(shù)調(diào)用的特性自行解決,.,30,遞歸算法的弱點,遞歸算法的執(zhí)行效率比一般非遞歸的執(zhí)行效率要低因為遞歸的實質(zhì)既然是函數(shù)調(diào)用，而函數(shù)調(diào)用必然要進行線程?？臻g的分配，記錄每一次函數(shù)調(diào)用前的狀態(tài)等工作，開銷是比較大的這個情況讀者可以自行應(yīng)用遞歸實現(xiàn)漢諾塔案例，輸入不同的鐵餅數(shù)，運行并觀察,.,31,非遞歸算法的特點,非遞歸算法則不需要進行這些工作（線程棧空間的分配等）因為非遞歸使用額外的變量記錄當前所處的位置信息，以及額外的控制語句遞歸與非遞歸調(diào)用最主要區(qū)別就是在函數(shù)調(diào)用上,.,32,遞歸與非遞歸策略思想,因此對解決某些問題時，希望用遞歸算法分析問題，但用非遞歸算法解決問題這就需要把遞歸算法轉(zhuǎn)換為非遞歸算法,.,33,遞歸算法轉(zhuǎn)化為非遞歸算法,有如下三種基本方法：通過分析，跳過分解過程，直接用循環(huán)結(jié)構(gòu)的算法實現(xiàn)求解過程。自己用棧模擬系統(tǒng)的運行棧，通過分析只保存必須保存的信息，從而用非遞歸算法替代遞歸算法利用棧保存參數(shù)，由于棧的后進先出特性吻合遞歸算法的執(zhí)行過程，因而可以用非遞歸算法替代遞歸算法,.,34,使用非遞歸方法實現(xiàn)漢諾塔算法,.,35,算法說明,將三個柱子分別命名為na1，na2，na3，初始狀態(tài)，所有的盤子都在na1上，三個柱子按逆時針方向排列成一個圓環(huán)其中存在一個規(guī)律，當對于規(guī)模為n的漢諾塔問題時：1奇數(shù)編號盤子總是移動移動到它后的第2個柱子上；2偶數(shù)編號的盤子總是移動移動到它的后第1個柱子上,.,36,基本算法策略的討論,最優(yōu)化和非最優(yōu)化：什么不去追求最優(yōu)化的解？因為存在一個解空間的規(guī)模問題，如果在規(guī)定時間里，可以找到所有的解，那么選出其中的最優(yōu)解；但是，如果不可能（有許多O(2n）以上時間復(fù)雜度的問題)，那么，只好退而求其次，用次優(yōu)解來解決問題而貪心策略就是求次優(yōu)解的常用思,.,37,基本算法策略的討論,時間換空間（或空間換時間）大部分遞歸算法編寫簡單，但運行的時間會隨著問題規(guī)模的增長而急劇增長而分治方法，一般要花費較多的時間將問題劃分成為較小規(guī)模，增加了程序的復(fù)雜性；遞歸程序的非傳參實現(xiàn)，也是如此但較為復(fù)雜的算法，卻換來幾何級數(shù)的運行時間節(jié)省,.,38,基本算法策略的討論,回溯策略所解的一些問題往往是不能用數(shù)學(xué)公式去直接求解的它需要通過一個過程，此過程要經(jīng)過若干個步驟才能完成，每一個步驟又分為若干種可能；同時，為了完成任務(wù)，還必須遵守一些規(guī)則和約束；對于這樣一類問題，一般采用搜索的方法來解決，回溯法就是搜索算法中的一種控制策略，它能夠解決許多搜索中問題,.,39,基本算法策略的討論,使用遞歸算法的思路分析問題，但用非遞歸算法解決問題。使用遞歸的思路分析問題，可以得到簡便、可行但運行效率低下的