計(jì)算機(jī)算法設(shè)計(jì)五大常用算法的分析及實(shí)例-文庫(kù)吧資料
2025-07-01 05:16本頁(yè)面
【正文】 問(wèn)題，設(shè)計(jì)算A[ i : j ], 1=i=j=n，所需的最少數(shù)乘次數(shù)為m[ i ][ j ]，則原問(wèn)題的最優(yōu)值為m[ 1 ][ n]。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可以用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。因此，矩陣連乘積計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。 以此次序，總的計(jì)算量為A[ 1 : k ]的計(jì)算量加上A[ k+1 : n ]的計(jì)算量， 再加上A[ 1 : k ]和A[ k+1 : n ]相稱的計(jì)算量?？疾煊?jì)算A[ 1: n]的最優(yōu)計(jì)算次序。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積(2) 算法設(shè)計(jì)①.分析最優(yōu)解的結(jié)構(gòu)設(shè)計(jì)求解具體問(wèn)題的動(dòng)態(tài)規(guī)劃算法的第一步是刻畫(huà)該問(wèn)題的最優(yōu)解的結(jié)構(gòu)特征。考察這n個(gè)矩陣的連乘積A1A2…An由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。 （3）以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值（2）遞歸的定義最優(yōu)解。（1）分析最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征。一般，只要解決問(wèn)題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫(xiě)出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。 (4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫(xiě)出。 (2)確定狀態(tài)和狀態(tài)變量：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問(wèn)題就無(wú)法求解。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。③有重疊子問(wèn)題：即子問(wèn)題之間是不獨(dú)立的，一個(gè)子問(wèn)題在下一階段決策中可能被多次使用到。② 無(wú)后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。與分治法最大的差別是：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解后得到的子問(wèn)題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解?；舅枷肱c分治法類似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子階段，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃基本思想動(dòng)態(tài)規(guī)劃過(guò)程中，每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。為了在遞歸處理的過(guò)程中使用同一個(gè)棋盤(pán)，將數(shù)組Board設(shè)為全局變量；②子棋盤(pán)：在棋盤(pán)數(shù)組Board[size][size]中，由子棋盤(pán)左上角的下標(biāo)tr、tc和棋盤(pán)邊長(zhǎng)s表示；③特殊方格：用Board[dr][dc]表示，dr和dc是該特殊方格在棋盤(pán)數(shù)組Board中的下標(biāo)；④L型骨牌：一個(gè)4k的棋盤(pán)中有一個(gè)特殊方格，所以用到L型骨牌的個(gè)數(shù)為( 1)/3將所有L型骨牌從1開(kāi)始連續(xù)編號(hào)，用一個(gè)全局整型變量tile表示，其初始值為0。 4中L型骨牌(2)：算法實(shí)現(xiàn) 棋盤(pán)覆蓋問(wèn)題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)： ①棋盤(pán)：用二維數(shù)組Board[size][size]表示一個(gè)棋盤(pán)， Board[0][0]是棋盤(pán)的左上角方格。 實(shí)例——棋盤(pán)覆蓋(1):問(wèn)題描述在一個(gè)2k2k（k≥0）個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其他方格不同，稱該方格為特殊方格，顯然，特殊方格在棋盤(pán)中出現(xiàn)的位置有4k種情形，因而就有 種不同的棋盤(pán)()。因此，當(dāng)P的規(guī)模不超過(guò)n0時(shí)，直接用算法Adhoc（P）求解。 遞歸與分治策略基本思想 其中，|P|表示問(wèn)題P的規(guī)模，n0為一閥值，表示問(wèn)題P的規(guī)模不超過(guò)n0，問(wèn)題已容易求解，不再分解。這樣就自然導(dǎo)致遞歸算法的產(chǎn)生。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。分治法的設(shè)計(jì)思想，是將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。一般只考慮最壞情況、最好情況和平均情況下的復(fù)雜度。如果分別用N、I和A表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。 算法復(fù)雜性分析算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為 時(shí)間復(fù)雜性，需要的空間資源的量稱為 空間復(fù)雜性。 表達(dá)算法的抽象機(jī)制高級(jí)程序設(shè)計(jì)語(yǔ)言的主要好處是：（1）高級(jí)語(yǔ)言更接近算法語(yǔ)言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作；（2）高級(jí)語(yǔ)言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì)出來(lái)的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；（3）高級(jí)語(yǔ)言不依賴于機(jī)器語(yǔ)言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而所寫(xiě)出來(lái)的程序可植性好、重用率高抽象數(shù)據(jù)類型是算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運(yùn)算。程序：是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。? 確定性：組成算法的每條指令清晰、無(wú)歧義。? 輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。通過(guò)對(duì)五中常用算法的單獨(dú)講解、綜合對(duì)比，分析出各種算法的特點(diǎn)以及適用領(lǐng)域，最后列舉相應(yīng)的算法實(shí)例，讓讀者對(duì)這五中常用算法有更深的了解。掌握算法、分析算法、將算
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1