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

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