算法_開發(fā)模式_設(shè)計模式

《算法_開發(fā)模式_設(shè)計模式》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、算法有以下幾種1?分治算法：分治算法的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題，這些子問題相互獨立且與原問題性質(zhì)相同。求岀了問題的解，就可得到原問題的解。2?貪心算法：在對問題求解吋，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。3.動態(tài)規(guī)劃算法：動態(tài)規(guī)劃的實質(zhì)是分治思想和解決兀余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的了問題，并存儲子問題的解而避免計算重復(fù)的了問題，以解決最優(yōu)化問題的算法策略。動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題,并通過求解子問題產(chǎn)住一個全局最優(yōu)解

2、。具屮貪心法的當(dāng)前選擇可能要依賴己經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個了問題是獨立的（即不包含公共的了了問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的思如果當(dāng)前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其小最優(yōu)（最人或最?。┲档慕?。若存在若干個取最優(yōu)值

3、的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨立,（亦即各子問題町包含公共的子子問題）也允許具通過自身子問題的解作出選擇，該方法對每一個了問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計算。因此，動態(tài)規(guī)劃法所針對的問題有一?個顯著的特征，即它所對應(yīng)的子問題樹屮的子問題呈現(xiàn)大雖:的重復(fù)。動態(tài)規(guī)劃法的關(guān)鍵就在于，対于重復(fù)出現(xiàn)的子問題，只在第一次遇到吋加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。4?回溯算法：回溯法是一個既帶有系統(tǒng)性乂帶有跳躍性的的搜索算法。它在包含問題的

4、所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索。凹溯法在用來求問題的所有解時，要凹溯到根，幾根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。其基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間

5、。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前擴展結(jié)點就成為死結(jié)點。換句話說，這個結(jié)點不再是一個活結(jié)點。此吋，應(yīng)往冋移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間小搜索，直至找到所耍求的解或解空間中已沒有活結(jié)點時為止。算法策略間的關(guān)系1、對問題進行分解的算法策略一一分治法與動態(tài)規(guī)劃法共同點：（1）分治法與動態(tài)規(guī)劃法實際上都是遞歸思想的運用（2）二者的根本策略都是對問題進行分

6、解，找到大規(guī)模少小規(guī)模的關(guān)系，然后通過解小規(guī)模的解，得出大規(guī)模的解不同點：適用于分治法的問題分解成子問題后，各子問題間無公共子問題，而動態(tài)規(guī)劃法相反。動態(tài)規(guī)劃法=分治算法思想+解決了問題間的冗余情況2、多階段逐步解決問題的策略貪心算法和動態(tài)規(guī)劃法貪心算法：每一步都根據(jù)策略得到一?個結(jié)果，并傳遞到下一步，自頂向下，一步一?步地做出貪心決策。動態(tài)規(guī)劃算法：毎一步?jīng)Q策得到的不是一個唯一結(jié)果，而是一組中間結(jié)果（且這些結(jié)果在以后各步可能得到多次引用），只是每一步都使問題的規(guī)模逐步縮小，最終得到問題的一個結(jié)果。開發(fā)模式目錄瀑布模式螺旋模型快速原型模式增量模式噴泉模型演化模型瀑布模式特點：?階段間具有順序

7、性和依賴性：O前一階段完成后，才能開始后一階段on了一階段的輸出文木為后一階段的輸入文木?推遲實現(xiàn)的觀點?質(zhì)量保證：O每個階段必須交付出合格的文檔缺點:?開始需要把需求做到最全?懼怕用戶測試小的反饋，懼怕需求變更?mux圖42帶反饋的渓布履型3螺旋模型限制條件：?適應(yīng)于內(nèi)部的大規(guī)模軟件開發(fā):螺旋模型強調(diào)風(fēng)險分析，許多客戶都無法接受和相信這種分析因此?適合于大規(guī)模軟件項目（執(zhí)行風(fēng)險分析將大大影響項目的利潤，進行