|
基本概念 1、算法：規則的有序有限集合; 規則是有確切含義而無二義性. 2、算法的基本特征： 可終止性;算法必須在有限時間內終止; 正確性;算法必須正確描述問題的求解過程; 可行性：算法必須是可實施的; 算法可以有0個或0個以上的輸入; 算法必須有1個或1個以上的輸出 算法的描述規則采用自然語言或算法流程控制采用結構化程序的基本控制結構(順序、 選擇 、重復)描述.形式語言描述; 算法與程序的關系1.程序可以不一定滿足可終止性。但算法必須在有限時間內結束; 2.程序可以沒有輸出,而算法則必須有輸出; 3.算法是面向問題求解的過程描述，程序則是算法的實現. 復雜度算法復雜度：評價算法優劣的唯一標準。由時間復雜度和空間復雜度構成. 時間復雜度:算法執行所花費的時間; 空間復雜度:算法執行所占用的內存. 設n為問題的大小(即問題所處理元素的 個數),則時間復雜度函數記為T(n),空間復雜讀S(n)。 復雜度分析事前分析是算法分析的重要步驟，是在算法實現之前進行時間和空間復雜度分析。 時間復雜度分析：就是對已設計好的算法進行有效的時間。 采用的基本方法是按照算法的控制結構進行分析，首先確定問題求解的基本操作，然后按照三種控制結構分別進行基本操作數與問題處理量的關系，確定出問題的時間復雜度函數。 時間復雜度分析時間復雜度分為最壞情況的復雜度和平均情況的復雜度。 在這里對時間復雜度分析我們只進行最壞情況的復雜度分析，基本方法如下所述： 每條規則的時間復雜度直接確定 順序結構：采用加法法則；重復結構：采用乘法法則；分支結構：采用取最大值法則。 最壞情況和平均情況分析最壞情況分析：在時間復雜度分析中，最壞情況是指在所有大小為n的輸入中，選擇代價最大的狀態進行分析而獲得的時間復雜度; 平均情況分析：平均情況分析是指在所有大小為n的輸入中，首先確定每個輸入出現的概率，針對每個輸入及其出現的概率的進行分析而獲得的時間復雜度. 基本運算 定義：如果算法中的一個元運算具有最高頻度，所有其它元運算頻度均在它的頻度的常數倍數之內，則稱這個元運算為基本運算。 在分析搜索和排序算法時，若元素比較為元運算，則為基本運算。 時間復雜度描述時間復雜度采用量級關系描述。 設時間復雜度函數為T(n), 則將T(n)描述為T(n) =O(f(n))，其含義為當n趨于無窮大時，T(n)和f(n)的比為一個不等于0的常數。 一般情況下f(n)為一個簡單函數，通常有以下形式：C,n,long(n),n!,n的冪等等一些描述簡單的函數. 遞歸方程求解的方法展開遞推式； 代入法；利用已知方程的解代入； 利用生成函數求解；生成函數是組合數學的一種方法； 歸納法在算法復雜度分析中是一種常用的求解方法，根據算法的流程，可構造復雜度函數。 分治方法的基本思想當被求解的問題規模n較大，不能直接求解時，可以將該問題分成若干個規模較小的子問題； 若子問題仍不能求解，則繼續進行劃分，直到子問題可直接求解； 最后由子問題的解歸并出原問題的解。 分治方法的基本模式Divde & conquer(n) {if (n<=n0) qwt(n); else {Divide n into subinstances n1,n2,…,nm; for ( i=1,i<=m,i++) yi=Divde & conquer(ni);} return merge(y1,y2,…,ym);} 動態規劃動態規劃和分治法相似,也是把待求解問題劃分成若干個子問題,先求解子問題,然后,從這些子問題的解得到原問題的解.所不同的是動態規劃所分解的子問題不是獨立的. 動態規劃通常用于求解最優性質的問題 最佳原理:不論以前狀態如何,當前狀態的值取決于它的所有直接前驅的狀態; 最優化原理：給出一個最優的決策序列，每一個子序列自身必須上最優的決策序列 基本思想動態規劃采用最佳原理,對問題從初始狀態逐步求解,找出最優解.描述如下: 1)找出最優解的性質,并描述其結構; 2)遞歸地定義最優值; 3自底向上計算最優值，記錄相關信息，最終構造最優最優解； 4）根據記錄信息，最終構造最優最優解； 最優策略動態規劃可以找出問題的最幼解，但是獲取最佳解的計算過程復雜且計算量很大，幾乎是列出所有解，才能找出最佳解。 對于任意問題，通常會存在一類約束條件和一些輸入，任何滿足這些約束條件的子集可以稱為問題的一個可能解。最佳解則是滿足目標函數達到最大值或最小值的一個可能解。 基本思想最優策略也是一個多步決策方法.每一步的選擇都使得能構成問題的一個可能解，同時使目標函數值的增速加快(目標函數最大)或減小(目標函數最小),這種選擇過程以一些最優化度量為根據. 最優化度量的選擇方法也稱為貪心法. 回溯法一般方法:回溯法的基本策略是搜索(按深度優先進行). 回溯法將問題的解表示成一個n元式(x1,x2,…,xn),其中每個xi取自某一初值集合si，稱(x1,x2,…,xn)為問題的解向量. 回溯法求解問題的過程需要滿足某種條件(稱為約束條件)或者使問題的解滿足判定函數B(x1,x2,…,xn)極大化(或極小化),希望求出約束條件或者判定函數某個解向量或所有解向量. 解空間:包含問題所有解的一棵樹稱為解的狀態空間樹; 從根結點出發搜索解的狀態空間樹,對于每一個結點,判定該結點是否滿足約束條件和判定函數,若滿足,則進入一個孩子樹繼續搜索,否則返回其雙親結點,進入其另一個孩子樹進行搜索,直到求出問題所要求的解. 算法描述 1）對于n元式(x1,x2,…,xn),定義每一個分量的取值范圍； 2）定義約束條件P(X)和判定函數B(X)； 3）設i=1; 4)對第i個元素賦一個可能值;使X =( x1,x2,…,x i);若所有可能值已經全部使用,則 i --; 重復4; 5)當P(X)和B(X)為真時. i ++;進入6,否則i --: 返回4: 6)由X =(x i)構造x i +1:返回5: 7)直到求出一個(或所有)滿足約束條件P(X)和判定函數B(X)的解。 遞歸算法Backseach(i) {if (i>n) output(X); else {X=(xi); while B(X)&&P(X) i++;Backseach(i)} 分支限界對于回溯法而言，是要對解的狀態空間樹的所有分支進行搜索，這樣時間復雜度是一個與樹上的結點總數和樹的深度的乘積。 分支限界的目的是通過一個限界函數選取合適的活結點，進行搜索，以加快速度，提高算法的效率。 基本思想定義一個限界函數 1、從初始結點開始，先計算該結點的限界值; 2、以該結點為當前活結點，生成它的所有可能的后繼結點，計算各結點的限界值，按某個(升/降)序列進入活結點隊列; 3、取活結點隊列隊頭元素為當前活結點，返回2; 4、直到隊空(找出問題的一個解或無解).
| 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
