第一篇：算法設計與分析學習心得

算法設計與分析學習心得

班級：物聯網1201 姓名：劉瀟 學號：1030612129

一、實驗內容：

這學期的算法與設計課，老師布置了這四個問題，分別是貨郎擔問題，動態生成二維數組，對話框下拉列表，排序問題。

二、學習掌握：

基本程序描述：

（1）貨郎擔問題：貨郎擔問題屬于易于描述但難于解決的著名難題之一，至今世界上還有不少人在研究它。貨郎擔問題要從圖g的所有周游路線中求取具有最小成本的周游路線，而由始點出發的周游路線一共有（n一1）！條，即等于除始結點外的n一1個結點的排列數，因此貨郎擔問題是一個排列問題。貨郎擔的程序實現了利用窮舉法解決貨郎擔問題，可以在城市個數和各地費用給定的情況下利用窮舉法逐一計算出每一條路線的費用，并從中選出費用最小的路線。從而求出問題的解

（2）費用矩陣：費用矩陣的主要內容是動態生成二維數組。首先由鍵盤輸入自然數，費用矩陣的元素由隨機數產生，并取整，把生成的矩陣存放在二維數組中，最后把矩陣內容輸出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是對包含具有約束條件的最優化問題的所有可行解的解（數目有限）空間進行搜索。該算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集，并為每個子集內的解計算一個下界或上界。動態生成二維n*n的數組程序利用指針表示數組的行和列，并逐一分配空間，在輸入n的數值后，系統自動分配空間，生成n*n的數組，并產生隨機數填充數組，最后將結果輸入到指定文件中。

（3）Mfc：在下拉列表框中添加內容程序，在下拉列表對應的函數中利用addstring添加需要的內容。首先定義下拉列表框為ccombox型，并定義其屬性名，利用addstring函數可以任意添加需要的內容。a排序問題:快速排序的運行時間與劃分是否對稱有關，其最壞情況發生在劃分過程中產生的兩個區域分別包含n-1個元素和1個元素的時候。其算法的時間復雜度為O(n 2),在最好的情況下每次劃分的基準恰好為中值，可得其算法時間復雜度為O(n㏒n)。算法的實現和理解和代碼實現完全是兩回事，想要完全掌握一種算法，需要動手實踐，用代碼實現，才能理解透徹，真正掌握。b對話框下拉列表：這個項目簡單易懂，輕松實現。三.疑問與總結：

貨郎擔的問題，我認為窮舉法相對比而言是比較初級的方法，費時耗力，適合在練習時選用，但是在實際問題中不建議采用。克魯斯卡爾或者普里姆算法求取最小生成樹的方法來解決貨郎擔的問題是更適合現實解決問題的。我認為程序可以用switch函數來將函數分成幾個部分更人性化，比如分為解決問題的的選項，輸出結果選項，退出程序選項等。再有就是費用矩陣的值可以從文件中讀取，而結果也可以直接放在指定文件中，這樣在實際應用中比較廣泛。

動態生成二維數組的程序我認為如果按照規范性，我的方法是中規中矩的，畢竟再向下延伸，生成三維的數組，需要三層的指針來實現。但是就程序的簡化程度和計算機處理時間來說，我認為這樣雙層指針的算法有些太占用內存，畢竟要給行和列各分配n個空間。我通過與同學的交流，我發現可以用1位數組來實現二維的n*n的數組。首先分配n*n的空間，然后通過循環在一行的數據達到n時自動換行。這樣程序得到了一定的簡化，并且減少了一定的內存使用。我認為這種方法是比較貼合實際的。

四.心得體會

在計算機軟件專業中，算法分析與設計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數據結構這個公式。算法的學習對于培養一個人的邏輯思維能力是有極大幫助的，它可以培養我們養成思考分析問題，解決問題的能力。

如果一個算法有缺陷，或不適合某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜性和時間復雜度來衡量。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。計算機系統中的操作系統、語言編譯系統、數據庫管理系統以及各種各樣的計算機應用系統中的軟件，都必須使用具體的算法來實現。算法設計與分析是計算機科學與技術的一個核心問題。因此，學習算法無疑會增強自己的競爭力，提高自己的修為，為自己增彩。

第二篇：數據結構算法設計與分析

數據結構算法設計與分析、計算機網絡、計算機組成原理、操作系統原理、編譯原理、數據庫原理及應用、軟件工程、軟件測試等計算機基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、Oracle、XML程序設計、計算機網絡、SSH（Struts+Spring+Hibernate）框架、Java EE程序設計、Ajax程序設計、Linux+PHP+MySQL程序設計、Android手機開發、UML系統分析與設計、性能測試、自動化軟件測試、軟件質量保證、畢業設計及項目綜合實訓等。

數據結構、計算機網絡、計算機組成原理、操作系統原理、編譯原理、數據庫原理及應用、金融學概論、西方經濟學等基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、J2EE程序設計、SQL Server數據庫、Oracle數據庫、Linux操作系統、UML系統分析與設計、軟件工程、XML程序設計、SSH框架、金融市場學、ERP財務管理、管理信息系統、投資銀行學、商業銀行學、國際金融管理、畢業設計及項目綜合實訓等專業課程。

數據結構、計算機網絡、計算機組成原理、操作系統原理、數據庫原理及應用、軟件工程、軟件測試等計算機基礎理論課程；

網頁制作、程序設計Java、JSP程序設計、J2EE程序設計、XML程序設計、Ajax程序設計、SSH框架、Android手機開發、Linux+PHP+MySQL程序設計、SQL Server數據庫、Linux操作系統、UML系統分析與設計、軟件項目管理、行業標準與規范、IT服務管理、IT職業英語、畢業設計及項目綜合實訓等專業課程

第三篇：算法設計與分析試題1

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

算法設計與分析試題1

一、單選題（每題2分，共40分）1、0518號臺風“達維”過后，要對各個單位捐款救災情況進行分組制表，并進行積分排序，一般使用的專業電子處理軟件有（B）

A、powerpoing B、Excel C、Word D、Visual Basic

2、一位愛好程序設計的同學，想通過程序設計解決“韓信點兵”的問題，他制定的如下工作過程中，更恰當的是（C）

A、設計算法，編寫程序，提出問題，運行程序，得到答案

B、分析問題，編寫程序，設計算法，運行程序，得到答案

C、分析問題，設計算法，編寫程序，運行程序，得到答案

D、設計算法，提出問題，編寫程序，運行程序，得到答案

3、交通警察到達案發現場，一般按照下列哪種思路開展工作（D）

①觀察、分析現場 ②收集必要的信息 ③進行判斷、推理 ④按一定的方法和步驟解決

A、②①③④ B、①③②④ C、③①②④ D、①②③④

4、下面說法正確的是（A）

A、算法+數據結構=程序 B、算法就是程序

C、數據結構就是程序 D、算法包括數據結構

5、下列常量說明中，符合語法的是（D）

A、CONST color=red B、CONST const=10*5

C、CONST xl：=3.9； D、CONST color=”abcd”

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

6、VB中將兩個字符串連接起來的運算符有：+和&，那么“123”+45結果是（A）

A、168 B、12345 C、”123” D、45

7、字符串”ABCD”和字符串”DCBA”進行比較，如果讓比較的結果為真，應選用關系運算符（B）

A、> B、< C、= D、>=

8、設a，b，c，d，e均為整型變量，且a=13，b=2，c=10，d=3，e=2，則表達式“a-b*c d MOD e”的值是(A)

A、13 B、-7 C、ll D、0

9、已知A，B，C，D是簡單變量，且都已有互不相同的值，執行語句B=8；A=C；D=A；D=B；后，其值相等的變量是（B）

A、A，D B、A，C C、C，B D、B，A

10、結構化程序設計由三種基本結構組成，下面哪個不屬于這三種基本結構（B）

A、順序結構 B、輸入、輸出結構 C、選擇結構 D、循環結構

11、下列結果為真的關系表達式是（C）

A、”A”<100 B、23.5<20 C、23<45 AND 72>8 D、5

12、以下運算符中運算優先級最高的是（D）

A、+ B、OR C、> D、13、整除運算時，若運算量為實數，則先取整，后相除，結果為整型或長整型。下列哪種是整除運算符（D）

A、+ B、Mod C、/ D、精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

14、VB結束程序的運行可以單擊程序窗體的“關閉”按鈕，或單擊VB工具欄上的“結果”按鈕，哪種是“結束”按鈕（B）

A、B、C、D、15、圖標控件屬于哪種基本控件（B）

A、標簽 B、文本框 C、按鈕 D、圖像

16、要交換變量A和B之值，應使用的語句組是(B)

A、A=B；B=C；C=A B、C=A；A=B；B=C

C、A=B；B=A D、C=A；B=A；B=C

17、執行下面的程序段后，x 的值為(A)

x=5

For i=1 To 20 Step 2

x=x+i5

Next i

A、21 B、22 C、23 D、24

18、在窗體上畫一個命令按鈕，然后編寫如下事件過程：

Private Sub Command1_Click()

Dim I as integer,j as integer,x as integer

x=4

For i=1 To 4

For j =1 To 3

x=x+6

Next j

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

Next i

Print x

End Sub

程序運行后，單擊命令按鈕，程序循環次數是(B)

A、4 B、12 C、3 D、6

19、在窗體上畫一個命令按鈕，然后編寫如下事件過程：

Prevate Sub Command1_Click()

Dim a as integer,b as integer, x as integer

x=0

Do Until x=-1

a = InputBox(“請輸入A的值”)

a = Val(a)

b = InputBox(“請輸入B的值”)

b = Val(b)

x = InputBox(“請輸入x的值”)

x = cint(x)

a = a+b+x

Loop

Print a

End Sub

程序運行后，單擊命令按鈕，依次在輸入對話框中輸入5、4、3、2、1、-1，則輸出結果為(A)

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

A、2 B、3 C、14 D、15

20、在窗體上畫一個文本框（其中Name屬性為Text1），然后編寫如下事件過程：

Private Sub Form_Load()

Dim i as integer,sum as integer

Text1.Text=“"

For i=1 To 10

Sum=Sum+i

Next i

Text1.caption=Sum

End Sub

上述程序的運行結果是(C)

A、在文本框Text1中輸出55

B、在文本框Text1中輸出0

C、出錯

D、在文本框Text1中輸出不定值

二、多選題（每題2分，共20分）

1、算法描述可以有多種表達方法，下面哪些方法可以描述“水仙花數問題”的算法(ABC)

A、自然語言 B、流程圖 C、偽代碼 D、機器語言

2、程序設計語言的發展經歷哪幾個過程(ABC)

A、機器語言 B、匯編語言 C、高級語言 D、自然語言

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

3、“閏年問題”的算法可以用哪些語言實現(ABCD)

A、Basic B、Pascal C、C++ D、C 語言

4、算法應該具有哪些重要的特征(ABCD)

A、有窮性 B、確定性 C、輸入、輸出 D、可行性

5、“今有物不知其數，三三數之余二，五五數之余三，七七數之余二，問物幾何？”這個問題屬于(ABD)

A、“韓信點兵問題” B、“鬼谷算法問題” C、“水仙花數問題” D、“閏年問題”

6、編制計算機程序解決問題的過程有：描述問題、算法設計、編寫計算機程序和調試等，其中，對算法描述正確的是(AD)

A、算法是解決問題的步驟

B、解題的步驟是有限的 C、算法就是解題的算式

D、算法是可以被表述和實現

7、以下屬非法用戶自定義標識符（常量和變量命名）的是(ACD)

A、8ad B、ad C、_ad D、const

8、為了便于數據的表示與處理，VB提供哪幾種基本數據類型(ABCD)

A、數值型 B、字符串型 C、布爾型 D、日期型

9、日期型數據專門用來處理日期和時間，哪種屬于日期型數據(AB)

A、#2005/10/23# B、#2005/01/02# C、2005/10/23 D、“2005/1/2”

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

10、哪些文件屬于某一VB工程中的文件(ABCD)

A、.vbp B、.frm C、.ocx D、.bas

三、判斷題（每題1分，共10分）

1、Visual Basic是美國微軟公司于1991年推出的基于Basic的可視化程序設計語言。（1）

2、一個算法可以被認為是用來解決一個計算問題的工具。（1）

3、一個算法可以用多種程序設計語言來實現。（1）

4、計算機是人制造的，所以，它和人腦解決問題沒有什么區別。（2）

5、字符串型數據是指用‘ ’括起來的一串字符。（2）

6、我們常說的程序設計語言就是程序設計。（2）

7、控件是應用程序的基本元素，與窗體共同構成應用程序的界面。（1）

8、面向對象的程序設計以對象為中心，以事件為過程的執行起點。（1）

9、MsgtBox函數反回值的類型為數值。（1）

10、Ctrl+T能打開屬性窗口。（2）

四、簡答題（每題10分，共30分）

1、說說人類和計算機解決問題的區別？

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

2、用流程圖描述出“閏年問題”的算法。

算法描述：

輸入年份Y

IF Y能被4整除 THEN

IF Y不能被100整除 THEN

輸出“是閏年”

ELSE

IF Y能被400整除 THEN

輸出“是閏年”

ELSE

輸出“不是閏年”

END IF

END IF

ELSE

輸出“不是閏年”

END IF

精心收集

精心編輯

精致閱讀 如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

3、在“神州號”程序中，我們只判斷了飛船成功飛行的條件。當飛船速度繼續加大時，飛船將達到第二宇宙、第三宇宙速度。。。。（見下表）

試編寫程序，輸入不同的飛船速度，判斷它的各種飛行狀況。

飛船速度（V）單位（km/s）

飛行狀況

7.91<=V<11.19 飛船繞地球似做勻速圓周運動

11.19<=V<16.67 飛船離開地球的控制 ,圍繞太陽轉

V>16.67 飛船掙脫太陽引力飛出太陽系

編程：

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

方法一：Prevate Sub Command1_Click()

Dim v As Integer

v = InputBox(”請輸入飛船速度的值“)

If(v >= 7.91)And(v <= 11.19)Then

Label1.Caption = ” 飛船繞地球似做勻速圓周運動“

Else

If(v >= 11.19)And(v <= 16.67)Then

Label1.Caption = ” 飛船離開地球的控制,圍繞太陽轉“

Else

If v >= 16.67 Then

Label1.Caption = ” 飛船掙脫太陽引力飛出太陽系“

Else

If v <= 7.91 Then

Label1.Caption = ” 輸入數據錯誤！“

End If

End If

End If

End If

End Sub

方法二：(課本P36)

Private Sub Form_Load()

Dim v As single

精心收集

精心編輯

精致閱讀

如需請下載！

演講稿 工作總結 調研報告 講話稿 事跡材料 心得體會 策劃方案

v = InputBox(”請輸入飛船速度的值“)

select case v

case is>16.67

Label1.Caption = ”飛船掙脫太陽引力飛出太陽系“

case is >= 11.19

Label1.Caption = ” 飛船離開地球的控制,圍繞太陽轉“

case is <= 7.91

Label1.Caption = ” 飛船離開地球的控制,圍繞太陽轉“

Case else

Label1.Caption = ” 輸入數據錯誤！"

End select

End Sub

精心收集

精心編輯

精致閱讀

如需請下載！

第四篇：算法分析與設計知識點總結

第一章 概述

算法的概念：算法是指解決問題的一種方法或過程，是由若干條指令組成的有窮序列。算法的特征：

可終止性：算法必須在有限時間內終止；

正確性：算法必須正確描述問題的求解過程；

可行性：算法必須是可實施的；

算法可以有0個或0個以上的輸入；

算法必須有1個或1個以上的輸出。

算法與程序的關系：

區別：程序可以不一定滿足可終止性。但算法必須在有限時間內結束；

程序可以沒有輸出,而算法則必須有輸出；

算法是面向問題求解的過程描述，程序則是算法的實現。

聯系：程序是算法用某種程序設計語言的具體實現；

程序可以不滿足算法的有限性性質。

算法描述方式：自然語言，流程圖，偽代碼，高級語言。

算法復雜性分析：

算法復雜性的高低體現運行該算法所需計算機資源（時間，空間）的多少。

算法復雜性度量：

期望反映算法本身性能，與環境無關。

理論上不能用算法在機器上真正的運行開銷作為標準（硬件性能、代碼質量影響）。

一般是針對問題選擇基本運算和基本存儲單位，用算法針對基本運算與基本存儲單位的開銷作為標準。

算法復雜性C依賴于問題規模N、算法輸入I和算法本身A。即C=F(N, I, A)。

第二章遞歸與分治

分治法的基本思想：

求解問題算法的復雜性一般都與問題規模相關，問題規模越小越容易處理。

分治法的基本思想是，將一個難以直接解決的大問題，分解為規模較小的相同子問題，直至這些子問題容易直接求解，并且可以利用這些子問題的解求出原問題的解。各個擊破，分而治之。

分治法產生的子問題一般是原問題的較小模式，這就為使用遞歸技術提供了方便。遞歸是分治法中最常用的技術。

使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。

分治法所能解決的問題一般具有以下幾個特征：

該問題的規模縮小到一定的程度就可以容易地解決；

該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；利用該問題分解出的子問題的解可以合并為該問題的解；

該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。（這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態規劃較好。）

遞歸的概念：

直接或間接地調用自身的算法稱為遞歸算法，用函數自身給出定義的函數稱為遞歸函數。

反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。

邊界條件與遞歸方程是遞歸函數的二個要素，遞歸函數只有具備了這兩個要素，才能在有限次計算后得出結果。

第三章動態規劃

動態規劃的基本思想：

動態規劃算法與分治法類似，其思想把求解的問題分成許多階段或多個子問題，然后按順序求解各子問題。最后一個階段或子問題的解就是初始問題的解。

分治法求解時，子問題數目太多，從而導致解決原問題需要耗費指數級時間。與分治法不同的是，動態規劃中分解得到的子問題往往不是互相獨立的。

但不同子問題的數目常常只有多項式級。用分治法求解時，有些子問題被重復計算了許多次。

動態規劃的適用條件：

動態規劃法解所能解決的問題一般具有以下兩個基本因素：

一、最優子結構性質

當問題的最優解包含著其子問題的最優解時，稱該問題具有最優子結構性質。

二、重疊子問題性質

遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。

其它同分治法。

動態規劃問題的特征：

求解的問題是組合優化問題；

求解過程需要多步判斷，從小到大依次求解；

子問題目標函數最優解之間存在依賴關系；

動態規劃算法設計的基本步驟和要素：

基本步驟：

（1）找出最優解的性質，并刻畫其結構特征。（考察是否適合采用動態規劃法。）

（2）遞歸地定義最優值。(建立遞歸式或動態規劃方程)

（3）以自底向上的方式（或以自頂向下的備忘錄方法）計算出最優值。

（4）根據計算最優值時得到的信息，構造最優解。

要素：

最優子結構

重疊子問題

備忘錄（表格）

應用實例分析：

1、矩陣連乘問題：

（1）分析最優解結構：

計算A[i:j]的最優次序所包含的計算矩陣子鏈 A[i:k]和A[k+1:j]的次序也是最優的。矩陣連乘計算次序問題的最優解包含著其子問題的最優解，滿足最優子結構性質。問題的最優子結構性質是該問題可用動態規劃算法求解的顯著特征。

（2）建立遞歸關系；

（3）計算最優值—遞歸求解（遞歸求解最優值復雜度較高的原因是：子問題重復度高)；計算最優值—迭代查表求解

計算最優值—備忘錄求解

（4）構造最優解

第四章貪心法

貪心算法的基本思想：

當一個問題具有最優子結構性質時，可用動態規劃方法求解，但有時會有更簡單有效的方法。

顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。在一些情況下，即使貪心算法不能得到整體最優解，其最終結果卻是最優解的很好近似。貪心算法中，較大子問題的解恰好包含了較小子問題的解作為子集，這與動態規劃算法設計中的優化原則本質上是一致的。

動態規劃算法在某一步決定優化函數的最大或最小值時，需要考慮到它的所有子問題的優化函數值，然后從中選出最優的結果；貪心算法的每步判斷時，不考慮子問題的計算結果，而是根據當時情況采取“只顧眼前”的貪心策略決定取舍。

貪心算法的設計要素：

可以用貪心算法求解的問題一般具有2個重要的性質：

1、最優子結構性質：

當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用動態規劃算法或貪心算法求解的關鍵特征

2、貪心選擇性質：

貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法與動態規劃算法的主要區別。

動態規劃算法通常以自底向上的方式求解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。

對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。

應用實例：

1、活動安排問題：

第五章回溯法

回溯法的基本思想：

回溯法的使用條件：

回溯法適用于搜索問題和優化問題。

回溯法的設計要素：

針對問題定義解空間：

問題解向量

解向量分量取值集合構造解空間樹

兩類典型的解空間樹：

子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。子集樹通常有2n個葉結點

排列樹：當所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉結點。

判斷問題是否滿足多米諾性質。

搜索解空間樹，確定剪枝函數。

確定存儲搜索路徑的數據結構。

第六章分支限界法

分支限界法的基本思想：

分支界限法類似與回溯法，也是在問題解空間中搜索問題解的一種算法。

分支界限法與回溯法思想對比：

求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。

搜索方式的不同：回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。

在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。

此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。

常見的兩種分支界限法：

隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。

優先隊列式分支限界法：按照優先隊列中規定的優先級選取優先級最高的節點成為當前擴展節點。

最大堆：最大效益優先

最小堆：最小耗費優先

第五篇：算法學習心得

算法設計與分析學習心得

班級：物聯網1201 姓名：劉瀟 學號：1030612129

一、實驗內容：

這學期的算法與設計課，老師布置了這四個問題，分別是貨郎擔問題，動態生成二維數組，對話框下拉列表，排序問題。

二、學習掌握：

基本程序描述：

（1）貨郎擔問題：貨郎擔問題屬于易于描述但難于解決的著名難題之一，至今世界上還有不少人在研究它。貨郎擔問題要從圖g的所有周游路線中求取具有最小成本的周游路線，而由始點出發的周游路線一共有（n一1）！條，即等于除始結點外的n一1個結點的排列數，因此貨郎擔問題是一個排列問題。貨郎擔的程序實現了利用窮舉法解決貨郎擔問題，可以在城市個數和各地費用給定的情況下利用窮舉法逐一計算出每一條路線的費用，并從中選出費用最小的路線。從而求出問題的解

（2）費用矩陣：費用矩陣的主要內容是動態生成二維數組。首先由鍵盤輸入自然數，費用矩陣的元素由隨機數產生，并取整，把生成的矩陣存放在二維數組中，最后把矩陣內容輸出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是對包含具有約束條件的最優化問題的所有可行解的解（數目有限）空間進行搜索。該算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集，并為每個子集內的解計算一個下界或上界。動態生成二維n*n的數組程序利用指針表示數組的行和列，并逐一分配空間，在輸入n的數值后，系統自動分配空間，生成n*n的數組，并產生隨機數填充數組，最后將結果輸入到指定文件中。

三.疑問與總結：

貨郎擔的問題，我認為窮舉法相對比而言是比較初級的方法，費時耗力，適合在練習時選用，但是在實際問題中不建議采用。克魯斯卡爾或者普里姆算法求取最小生成樹的方法來解決貨郎擔的問題是更適合現實解決問題的。我認為程序可以用switch函數來將函數分成幾個部分更人性化，比如分為解決問題的的選項，輸出結果選項，退出程序選項等。再有就是費用矩陣的值可以從文件中讀取，而結果也可以直接放在指定文件中，這樣在實際應用中比較廣泛。

動態生成二維數組的程序我認為如果按照規范性，我的方法是中規中矩的，畢竟再向下延伸，生成三維的數組，需要三層的指針來實現。但是就程序的簡化程度和計算機處理時間來說，我認為這樣雙層指針的算法有些太占用內存，畢竟要給行和列各分配n個空間。我通過與同學的交流，我發現可以用1位數組來實現二維的n*n的數組。首先分配n*n的空間，然后通過循環在一行的數據達到n時自動換行。這樣程序得到了一定的簡化，并且減少了一定的內存使用。我認為這種方法是比較貼合實際的。

四.心得體會

在計算機軟件專業中，算法分析與設計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數據結構這個公式。算法的學習對于培養一個人的邏輯思維能力是有極大幫助的，它可以培養我們養成思考分析問題，解決問題的能力。

如果一個算法有缺陷，或不適合某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜性和時間復雜度來衡量。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。計算機系統中的操作系統、語言編譯系統、數據庫管理系統以及各種各樣的計算機應用系統中的軟件，都必須使用具體的算法來實現。算法設計與分析是計算機科學與技術的一個核心問題。因此，學習算法無疑會增強自己的競爭力，提高自己的修為，為自己增彩。篇二：算法個人心得

算法學習心得: 算法這個詞是在我在大學第一次c語言課上聽到的，當時老師講的是程序=算法+數據結構，算法是一個程序的靈魂。當時我什么也不懂，不知道什么叫數據結構，什么叫算法，它們是干什么的我也不明白。然而經歷了大學四年的學習，現在的我對算法有了一個較為清晰的認識，對于它的作用也有了深刻的體會。

所謂算法簡單來說就是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，也就是說算法告訴計算機怎么做，以此來解決問題。同一個問題存在多種算法來解決它，但是這些算法存在著優劣之分，好的算法速度快，效率高，占用空間小，差的算法不僅復雜難懂，而且效率低，對機器要求還高，當然，有時候算法之間存在一種互補關系，有些算法效率高，節省時間，但浪費空間，另外一些算法可能速度上慢些，但是空間比較節約，這時候我們就應該根據實際要求，和具體情況來采取相應的算法來解決問題。

這學期算法課上我們主要講了七部分內容.第一章主要講的是算法的基本概念，算法時間復雜度分析，算法的漸近時間復雜度等內容。因為算法之間的比較就是通過時間復雜度和空間復雜度來來比較的，第一章的主要目的就是讓我們學會去分析一個算法的復雜度，以后就可以通過對復雜度的分析來評價算法的好壞。

第二章講的是分治法，任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少，分治法的設計思想就是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。在這一章中我們講到了尋找第k個元素，矩陣相乘，尋找最近點對等幾個使用分治法的經典例子，最后還將講到了傅里葉變換的問題。以前我們學到的歸并排序，二分搜索其實也是基于分治法思想的。能采用分治法來解決的問題通常有如下幾個特征： 1)該問題的規模縮小到一定的程度就可以容易地解決 2)該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子

結構性質。

3)利用該問題分解出的子問題的解可以合并為該問題的解； 4)該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公

共的子子問題。

在用分治法解決實際問題時，我們疑問究竟各個子問題的規模應該怎樣才為適當？從大量實踐中發現，在用分治法設計算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的，這就是一種平衡的思想。

第三章主要講動態規劃問題。這一章的內容我覺得是算法設計思想中最難，也最有趣的這部分。什么叫動態規劃，動態規劃的思想是什么？動態規劃采用自頂向下的方式分析問題，自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。簡言之，動態規劃的基本思想就是把全局的問題化為局部的問題，為了全局最優必須局部最優。“多階段決策問題是根據問題本身的特點，將其求解的過程劃分為若干個相互獨立又相互聯系的階段，在每一個階段都需要做出決策，并且在一個階段的決策確定以后再轉移到下一個階段，在每一階段選取其最優決策，從而實現整個過程總體決策最優的目的”（引用）。還記得期末考試中的最后一道關于任意給定一個數，從所給的牌中用最少的牌組成這個數，這個問題其實就可以用動態規劃來解決。本科期間，在算法課上老師在動態規劃這一章不布置的一個作業跟這個題目類似，當時的題目是找錢問題，問題是這樣描述的：有n種不同面值的硬幣，各硬幣面值存于數組t[1:n]，現用這些面值的錢來找錢，編程計算找錢m的最少硬幣數及各個面值。分析如下：假設對于i = 1...n-1，所需最少的硬幣數count(i)已知，那么對于n，所需的硬幣數為min(count(i)+ count(n-i)), i=1...n-1;于是一個直觀的方法是用遞歸計算。

但是，遞歸過程中，每次計算count(i)，都會重復計算 count(1)....count(i-1);這樣時間復雜度就是o(n^2);我們可以從1開始記錄下每個錢數所需的硬幣枚數，避免重復計算，為了能夠輸出硬幣序列，我們還需要記錄下每次新加入的硬幣。下面給出用動態規劃解決此問題的遞推式：

參數說明： 當只用面值為t[1],t[2],?t[n]來找出錢j時，所用的硬幣的最小個數記為c(i,j),則c(i,j)的遞推方程為：

運用這個遞推式，我們可以從下往上記錄各個j所需要的應兵書i，最后當j=m時，所對應的i就是我們要求的。第四章講的是集合算法，這一章的內容是我第一次接觸，以前沒有學過。這一章主要講了平攤分析，union-find，finding the depth，以及2-3樹等內容，平攤分析教會我們如何從整體的角度去更精確的分析算法的時間復雜度，union-find sets是一種簡單的用途廣泛的集合，并查集是若干個不相交集合，能夠實現較快的合并和判斷元素所在集合的操作，一般采取樹形結構來存儲并查集，并利用一個rank數組來存儲集合的深度下界，在查找操作時進行路徑壓縮使后續的查找操作加速，finding the depth 確定深度問題。為了既能求得各點在原先樹中的正確深度、又能使時間復雜度較小，需要使用具有路徑壓縮功能的find-depth指令，同時還需要采取一些輔助手段來保證深度計算的正確性。2-3樹具有以下幾個特點：

1、任一內結點（非葉結點）均有2個或3個兒子。

2、從根到每片樹葉的路徑長度相等。

3、內結點中只存放便于查找的信息，而葉結點中存放原始數據。

第五章主要講了隨機算法。在隨機算法中，我們不要求算法對所有可能的輸入均正確計算，只要求出現錯誤的可能性小到可以忽略的程度。另外我們也不要求對同一輸入算法每次執行時給出相同的結果。我們所關心的是算法在執行時，是否能夠產生真正隨機的結果。有不少問題，目前只有效率很差的確定性求解算法，但用隨機算法去求解，可以很快地獲得相當可信的結果。隨機算法通常分為兩大類:las vegas算法、monte carlo算法。las vegas算法總是給出正確的結果，但在少數應用中，可能出現求不出解的情況。此時需再次調用算法進行計算，直到獲得解為止.mont carlo算法通常不能保證計算出的結果總是正確，一般只能斷定所給解的正確性不小于p（1/2＜p＜1）。通過反復執行算法（即以增大算法的執行時間為代價），能夠使發生錯誤的概率小到可以忽略的程度。第五章還講到素數測試，其中介紹了相關定理，重點講了miller-rabin算法。

第六章介紹了計算模型，這一章主要介紹了有關計算的一些本質問題，random access machines(隨機存取機，簡稱ram)，存儲程序模型rasp（random access stored program），圖靈機（turning machine）以及各個計算模型之間的關系。

第七章介紹了np完全問題，主要包括近似算法（approximation algorithms），非確定性turing機 ndtm，確定性turing機 dtm，以及之間的區別，np完全經典問題等內容。

經過一學期的算法學習，我對算法的了解進一步加深，曾經學習過的內容得到進一步鞏固，同時沒有接觸的內容也讓我有了新的認識。作為一名計算機專業的學生，算法是一門基礎學科，它里面包含的思想無處不在，學好算法分析，對于在自己的方向上獲得啟示，體會更深有著重大作用。所以，我們應該培養對算法的興趣，將算法的運用融入到生活當中，比如找錢問題就是個很好的例子，通過具體的生活實例來讓算法變得更加有魅力，有吸引力,以此來激發對算法的興趣。篇三：算法設計與分析學習總結 算法分析與設計 學習總結

題目：算法分析與設計學習總結

學 院 信息科學與工程學院

專 業 屆 次

學生姓名 學 號

二○一三年一月十五日

算法分析與設計學習總結

本學期通過學習算法分析與設計課程，了解到：算法是一系列解決問題的清晰指令，代表著用系統的方法描述解決問題的策略機制。算法能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個算法有缺陷，或不適合某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜性和時間復雜度來衡量。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。計算機系統中的操作系統、語言編譯系統、數據庫管理系統以及各種各樣的計算機應用系統中的軟件，都必須使用具體的算法來實現。算法設計與分析是計算機科學與技術的一個核心問題。

設計的算法要具有以下的特征才能有效的完成設計要求，算法的特征有：（1）有窮性。算法在執行有限步后必須終止。（2）確定性。算法的每一個步驟必須有確切的定義。（3）輸入。一個算法有0個或多個輸入，作為算法開始執行前的初始值，或初始狀態。（4）輸出。一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的。（5）可行性。在有限時間內完成計算過程。

算法設計的整個過程，可以包含對問題需求的說明、數學模型的擬制、算法的詳細設計、算法的正確性驗證、算法的實現、算法分析、程序測試和文檔資料的編制。算法可大致分為基本算法、數據結構的算法、數論與 代數算法、計算幾何的算法、圖論的算法、動態規劃以及數值分析、加密算法、排序算法、檢索算法和并行算法。經典的算法主要有：

1、窮舉搜索法

窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，bing從中找出那些符合要求的候選解作為問題的解。

窮舉算法特點是算法簡單，但運行時所花費的時間量大。有些問題所列舉書來的情況數目會大得驚人，就是用高速計算機運行，其等待運行結果的時間也將使人無法忍受。我們在用窮舉算法解決問題是，應盡可能將明顯不符合條件的情況排除在外，以盡快取得問題的解。

2、迭代算法

迭代法是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或方程組）的過程，為實現這一過程所使用的方法統稱為迭代法。迭代法是用于求方程或方程組近似根的一種常用的算法設計方法。設方程為f(x)=0,用某種數學方法導出等價的形式x=g(x),然后按以下步驟執行：

（1）選一個方程的近似根，賦給變量x0。(2)將x0的值保存于變量x1，然后計算g(x1),并將結果存于變量x0。（3）當x0與x1的差的絕對值還小于指定的精度要求時，重復步驟（2）的計算。若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。

3、遞推算法

遞推算法是利用問題本身所具有的一種遞推關系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的。

4、遞歸算法

遞歸算法是一種直接或間接的調用自身的算法。

能采用遞歸描述的算法通常有這樣的特征：為求解規模為n的問題，設法將它分解成規模較小的問題，然后從這些小問題的解方便地構造出大問題的解，并且這些規模較小的問題也能采用同樣的分解和綜合方法，分解成規模更小的問題，并從這些更小問題的解構造出規

模較大問題的解。特別的，當規模n=0或1時，能直接得解。

遞歸算法解決問題的特點有：

（1）遞歸就是在過程或函數里調用自身

（2）在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口

（3）遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低

（4）在遞歸調用的過程中系統為每一層的返回點、局部變量等開辟堆棧來存

儲。

舉例如下： fibonacci數列

int fib[50];//采用數組保存中間結果 void fibonacci(int n){ fib[0] = 1;fib[1] = 1;for(int i=2;i<=n;i++)fib[i] = fib[i-1]+fib[i-2];}

5、分治算法

分治算法是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最后子問題可以簡單地直接求解，原問題的解即子問題解的合并。

如果原問題可分割成k個子問題，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。

分治策略的算法設計模式 divide_and_conquer（p）{ if(|p|＜＝n0)return adhoc(p)； divide p into smaller substances p1，p2，?，pk； for(i＝1;i＜＝k;k＋＋)yi＝divide-and-conquer（pi）//遞歸解決pi return merge（y1，y2，?，yk）//合并子問題 }

6、貪心算法

貪心算法也稱貪婪算法。它在對問題求解時，總是做出在當前看來是最好的選擇。它不從整體最優上考慮，所得出的僅是在某種意義上的局部最優解。貪心算法的基本思路如下：（1）建立數學模型來描述問題

（2）把求解的問題分成若干個子問題

（3）對每一子問題求解，得到子問題的局部最優解

（4）把子問題的局部最優解合成原來問題的一個解

貪心算法的一般流程: greedy(a){ s={ };//初始解集合為空集 while(not solution(s))//集合s沒有構成問題的一個解 { x = select(a);//在候選集合a中做貪心選擇 if feasible(s, x)//判斷集合s中加入x后的解是否可行 s = s+{x};a = a-{x};} return s;｝

（1）候選集合a：問題的最終解均取自于候選集合a。（2）解集合s：解集合s不斷擴展，直到構成滿足問題的完整解。

（3）解決函數solution：檢查解集合s是否構成問題的完整解。

（4）選擇函數select：貪心策略，這是貪心算法的關鍵。

（5）可行函數feasible：解集合擴展后是否滿足約束條件。

7、動態規劃算法

動態規劃算法是一種在數學和計算機科學中用于求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。

動態規劃算法的步驟

(1)找出最優解的性質，并刻畫其結構特征；(2)遞歸地定義最優值（寫出動態規劃方程）；(3)以自底向上的方式計算出最優值；(4)根據算法最優值時得到的信息，構造一個最優值。

動態規劃算法的有效性依賴于問題本身所具有的兩個重要的性質：最優子結構性質和子問題重疊性質。(1)最優子結構：當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。

(2)重疊子問題：在用遞歸算法自頂向下解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。

8、回溯算法 回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。當探索到某一步時，發現原先的選擇并不優或達不到目標，就回退一步重新選擇，這種走不通就退回再走的技術成為回溯法，滿足回溯條件的某個狀態的點稱為“回溯點”。迷宮問題算法所采用的就是回溯算法。

回溯算法解決問題的過程是先選擇某一可能的線索進行試探，每一步試探都有多種方式，將每一方式都一一試探，如有問題就返回糾正，反復進行這種試探在反復糾正，直到得出全部符合條件的答案或是問題無解為止。由于回溯方法的本質是深度優先的方法在解的空間樹中搜索，就要從堆棧中找到回溯的前一個位置繼續試探。

裝載問題回溯算法數據結構 #define num 100 int n;//集裝箱的數量 int c;//輪船的載重量 int w[num];//集裝箱的重量數組 int x[num];//當前搜索的解向量 int r;//剩余集裝箱的重量 int cw;//當前輪船的載重量 int bestw;//當前最優載重量

int bestx[num];//當前最優解 算法實現 //形參表示搜索第t層結點 void backtrack(int t){ //到達葉子結點 if(t>n){ //更新最優解 if(cw>bestw){ for(int i=1;i<=n;i++)bestx[i] = x[i];bestw = cw;} return;} //更新剩余集裝箱的重量 r-= w[t];//搜索左子樹

if(cw+w[t]<=c){ x[t] = 1;cw += w[t];backtrack(t+1);cw-= w[t];} //搜索右子樹

if(cw+r>bestw){ x[t]=0;backtrack(t+1);} r += w[t];//恢復狀態 }

9、分支限界算法 分支限界算法是一種在表示問題解空間的樹上進行系統搜索的方法。該方法使用了廣度篇四：算法設計與實現個人課程總結 算法課程總結

指導教師

所在院（系）

班 級

學生姓名

學 號

一、算法概述 1.什么是算法？

算法是解一確定類問題的任意一種特殊的方法。在計算機科學中，算法是使用計算機解一類問題的精確、有效方法的代名詞。算法是一組有窮的規則，它規定了解決某一特定類型問題的一系列運算。

2.算法的五個重要特性：確定性、能行性、輸入、輸出、有窮性/有限性。1）確定性：算法每種運算必須有確切定義，不能有二義性。2）能行性：算法中有待實現的運算都是基本的運算，原理上每種運算都能由人用紙和筆在有限的時間內完成。3）輸入：每個算法有0個或多個輸入。這些輸入是在算法開始之前給出的量，取自于特定的對象集合——定義域

4）輸出：一個算法產生一個或多個輸出，這些輸出是同輸入有某種特定關系的量。5）有窮性/有限性：一個算法總是在執行了有窮步的運算之后終止。3.計算過程：只滿足確定性、能行性、輸入、輸出四個特性但不一定能終止的一組規則。4.準確理解算法和計算過程的區別：不能終止的計算過程：操作系統；算法是“可以終止的計算過程”；算法的時效性：只能把在相當有窮步內終止的算法投入到計算機上運行。5.算法的語言主要有：自然語言，流程圖，盒圖，pad圖，偽代碼，計算機程序設計語言。

6.算法分類： 1)多項式時間算法：可用多項式（函數）對其計算時間限界的算法。常見的多項式限界函數有：ο(1)< ο(logn)< ο(n)< ο(nlogn)< ο(n2)< ο(n3)2）指數時間算法：計算時間用指數函數限界的算法。常見的指數時間限界函數：ο(2n)< ο(n！)< ο(nn)7.算法基本工具：循環與遞歸，算法與數據結構，優化算法的數學模型。8.主要算法：迭代算法，蠻力法，分治法，動態規劃法，貪婪算法，圖搜索基礎。

二、算法的核心是思想

我們學習這門課不是僅僅掌握那幾個經典算法例子，更重要的是為了學習蘊含在其中的思想方法。為什么呢？舉個例子。有同學曾問我這樣一個問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發期為1個星期。現在用10只老鼠在一個星期內判斷那只瓶子有毒，每只老鼠可以喝多個瓶子的水，每個瓶子可以只喝一點。問如何解決？其實一開始我也一頭霧水，但是他提醒我跟計算機領域相關，我就立馬有了思路，運用二進制。因為計算機的最基本思想就是二進制。所以說，我們不僅要學習算法，更得學習思想方法。

①算法最基本的設計方法包括分治法，動態規劃法，貪婪算法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個元素中最大元和最小元的量級，降低n位二進制x和y相乘的量級，做strassen矩陣乘法等等。它的思想就是規模很大的問題分解為規模較小的獨立的子問題，關鍵是子問題要與原問題同類，可以采取平衡法來提高性能。

動態規劃法是把大問題分解為子問題，但是子問題是重復的，后面的問題可

以利用前面解決過的問題的結果。如構造最優二叉查找樹，解決矩陣連乘時最小計算次數問題，尋找最長公共子序列等等。

貪婪算法就是局部最優法，先使局部最優，再依次構造出更大的局部直至整體。如kruscal最小生成樹算法，求哈夫曼編碼問題。

周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點，典型的應用就是圖中的深度優先搜索(dfs)和廣度優先搜索(bfs)。

回溯法就是就是在滿足一定的條件后就往前走，當走到某步時，發現不滿足條件就退回一步重新選擇新的路線。典型的應用就是8皇后問題，平面點集的凸包問題和0-1背包問題。

分支定界法：它是解決整數規劃問題一種最常用的方法。典型應用就是解決整數規劃問題。

②評價算法性能的方法如平攤分析中的聚集法，會計法和勢能法。聚集法就是把指令分為幾類，計算每一類的消耗，再全部疊加起來。會計法就是計算某個指令時提前將另一個指令的消耗也算進去，以后計算另一個指令時就不必再算了。勢能法計算每一步的勢的變化以及執行這步指令的消耗，再將每一步消耗全部累計。

這幾種方法都是平攤分析法，平攤分析的實質就是總體考慮指令的消耗時間，盡管某些指令的消耗時間很大也可以忽略不計。上述三種方法難易程度差不多，每種方法都有屬于它的難點。如聚集法中如何將指令有效分類，會計法中用什么指令提前計算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學會去應用，在具體的問題中去判斷分析。

三、重點學習 1.貪婪算法

貪婪+其他算法：由于貪婪往往能大幅化簡狀態，利用問題的某些“單調性”，加上貪婪的思想，往往能是問題大幅簡化，從而結合其他算法解決問題經典例題：田忌賽馬，利用貪婪來確定狀態。2.分治法

分而治之的思想在信息學競賽中是非常重要的，下面主要介紹一下分治的經典應用 1)二分查找

思想很簡單，功能很強大，邊界要注意，負數要特判（noi2010 piano）在非負數范圍內的二分一般寫法

如果是l := mid1 或 +1則 mid :=(l + r + 1)div 2 2)快速冪

a^b =(a^(b div 2))^2 + ord(odd(b))*a取模也適用 3）快速排序，歸并排序

任何一本算法書上都會講的，這里就略過了，值得一提的是快排記得加上隨機化 k := a[random(rg(x)*ans = 0 重構權，將f(i)-g(i)*ans作為新權值，用相應算法求出一個“最小值”，判斷是否>=0，接著二分即可 5)樹的分治

一般用來解決樹上的路徑或統計類問題，每次只考慮跟樹根有關的信息，然后遞歸分治處理

樹的分治通常有基于點或基于邊的分治，基于點的難合，基于邊的復雜度太高，這里只介紹基于點的分治

步驟：處理跟當前樹根有關的信息，重新計算子樹大小，在子樹中選擇重心為根，遞歸到相應子樹處理。

因為每次選了重心，所以遞歸總共logn層，每層o(n)的復雜度，總復雜度就是o(nlogn)6)二分搜索

直接搜的復雜度是指數級的的話，一般是40左右的數據量，hash一半，搜一半，搜后面的時候利用之前的hash信息合并出原問題的解。

而直接搜的復雜度達到階乘級的話n一般就不超過20了，做法一般差不多 經典例題：poi02szy，noi2001方程的解數。3.搜索

作為信息學競賽中的所謂“萬能算法”，搜索可以說是計算機學科所具有的最大特點了，自然地，搜索算法的應用自然也是非常之廣泛，除了專門的搜索題，搜索一般可以用來部分預處理，打表找規律，當然還有騙分。

搜索的一般步驟：確定狀態——選擇搜索方式（dfs、bfs）——確定產生式規則——開始搜索。搜索的常見優化方式： 1)改變狀態表示

這個需要根據題目而定，確定一個漂亮的狀態表示，可能就有希望轉向記憶化了，即使不行，搞出一個漂亮的狀態表示是解決一道麻煩題的最重要的一步，再者，調試起來也會容易許多。

2）優化搜索順序

這個優化在多數搜索中能起到摧枯拉朽的提速效果，通常我們選擇枝葉較少的兒子先擴展，例如大名鼎鼎的dancing links，除了利用雙向十字鏈表去除冗余狀態，每次選擇可擴展數最少的兒子擴展同樣給它的神速創造了條件。3）可行性剪枝以及最優性剪枝

這是非常常用的剪枝思路之一，因題目而異，在迭代加深搜索中尤為重要 一般思路：考慮每次解最多變優多少，從當前的層數來看還有多少改進空間，如果已經不可能成為解或更新答案則可以剪枝了

——a*及ida*算法：本質就是給搜索加上一個滿足相容性的估價函數，然后用估價函數剪枝，理論上很牛b，實際上不常用，因為考場上很難想出滿足那么多條件的估價函數，但記得一些常見模型的估價函數還是有價值的。例如15 數碼的估價函數就可以選擇除了0之外每個元素到自己該到的位置的曼哈頓距離之和，因為每次最多使一個數距離減少1，所以這個估價函數是相容的，再例如求k短路的a*算法就是用個堆維護 min{ f(s)+ g(s)}估價函數就是從匯點反搜的“反向最短路”的長度。

四、總結

在計算機軟件專業中，算法分析與設計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數據結構這個公式。算法的學習對于培養一個人的邏輯思維能力是有極大幫助的，它可以培養我們養成思考分析問題，解決問題的能力。作為it行業學生，學習算法無疑會增強自己的競爭力，修煉自己的“內功”。

經過這門課的學習，我深刻的領悟到數學是一切算法分析與設計的基礎。這門課的很多時間多花在了數學公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數學息息相關。其中有幾個定理令我印象深刻。

①主定理

本門課中它主要應用在分治法性能分析上。例如：t(n)=a*t(n/b)+f(n)，它可以看作一個大問題分解為a個子問題，其中子問題的規模為b。而f(n)可看作這些子問題的組合時的消耗。這些可以利用主定理的相關結論進行分析處理。當f(n)量級高于時，我們可以設法降低子問題組合時的消耗來提高性能。反之我們可以降低的消耗，即可以擴大問題的規模或者減小子問題的個數。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進行有效的改進。

②隨機算法中的許多定理的運用

在這門課中，我學到了以前從未遇見過的隨機算法，它給予我很大的啟示。隨機算法不隨機，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計。這些都不是空穴來風，它是建立在嚴格的定理的證明上。如素數判定定理是個很明顯的例子。它運用了包括費馬小定理在內的各種定理。將這些定理進行有效的組合利用，才得出行之有效的素數判定的定理。尤其是對尋找證據數算法的改進的依據，也是建立在3個定理上。還有檢查字符串是否匹配也是運用了許多定理：指紋的運用，理論出錯率的計算，算法性能的評價也都是建立在數學定理的運用上。篇五：遺傳算法學習心得

基本概念

遺傳算法(genetic algorithms, ga)是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。

它模擬自然選擇和自然遺傳過程中發生的繁殖、交叉和基因突變現象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。ga的組成:（1）編碼（產生初始種群）

（2）適應度函數

（3）遺傳算子（選擇、交叉、變異）

（4）運行參數

編碼

基因在一定能夠意義上包含了它所代表的問題的解。基因的編碼方式有很多，這也取決于要解決的問題本身。常見的編碼方式有：

（1）二進制編碼，基因用0或1表示（常用于解決01背包問題）如：基因a：00100011010(代表一個個體的染色體)（2）互換編碼（用于解決排序問題，如旅行商問題和調度問題）

如旅行商問題中，一串基因編碼用來表示遍歷的城市順序，如：234517986，表示九個城市中，先經過城市2，再經過城市3，依此類推。

（3）樹形編碼（用于遺傳規劃中的演化編程或者表示）

如,問題：給定了很多組輸入和輸出。請你為這些輸入輸出選擇一個函數，使得這個函數把每個輸入盡可能近地映射為輸出。

編碼方法：基因就是樹形結構中的一些函數。

（4）值編碼（二進制編碼不好用時，解決復雜的數值問題）在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關任何值：整數，實數，字符或者其他一些更復雜的東西。

適應度函數

遺傳算法對一個個體（解）的好壞用適應度函數值來評價，適應度函數值越大，解的質量越好。適應度函數是遺傳算法進化過程的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。

如tsp問題，遍歷各城市路徑之和越小越好，這樣可以用可能的最大路徑長度減去實際經過的路徑長度，作為該問題的適應度函數。

遺傳算子——選擇

遺傳算法使用選擇運算來實現對群體中的個體進行優勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。sga（基本遺傳算法）中采用輪盤賭選擇方法。

輪盤賭選擇又稱比例選擇算子，基本思想：各個個體被選中的概率與其適應度函數值大小成正比。設群體大小為n，個體i 的適應度為 fi，則個體i 被選中遺傳到下一代群體的概率為：

遺傳算子——交叉

所謂交叉運算，是指對兩個相互配對的染色體依據交叉概率按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算在ga中起關鍵作用，是產生新個體的主要方法。1.單交叉點法（用于二進制編碼）

選擇一個交叉點,子代在交叉點前面的基因從一個父代基因那里得到,后面的部分從另外一個父代基因那里得到。

如：交叉前：

00000|***00 11100|***01 交叉后：

00000|***01 11100|***00 2.雙交叉點法（用于二進制編碼）

選擇兩個交叉點,子代基因在兩個交叉點間部分來自一個父代基因,其余部分來自于另外一個父代基因.如：交叉前： 01 |0010| 11 11 |0111| 01 交叉后： 11 |0010| 01 01 |0111| 11 3.基于“ 與/或 ”交叉法（用于二進制編碼）對父代按位與”邏輯運算產生一子代a;按位”或”邏輯運算產生另一子代b。該交叉策略在解背包問題中效果較好.如：交叉前： 01001011 11011101 交叉后： 01001001 11011111 4.單交叉點法（用于互換編碼）

選擇一個交叉點，子代的從初始位置出發的部分從一個基因復制，然后在另一個基因中掃描，如果某個位點在子代中沒有，就把它添加進去。

如：交叉前： 87213 | 09546 98356 | 71420 交叉后：

87213 | 95640 98356 | 72104 5.部分匹配交叉（pmx）法（用于互換編碼）

先隨機產生兩個交叉點，定義這兩點間的區域為匹配區域，并用交換兩個父代的匹配區域。

父代a：872 | 130 | 9546 父代b：983 | 567 | 1420 變為： temp a: 872 | 567 | 9546 temp b: 983 | 130 | 1420 對于 temp a、temp ｂ中匹配區域以外出現的數碼重復，要依據匹配區域內的位置逐一進行替換。匹配關系：1<——>５ ３<——>６ ７<——>０ 子代ａ：802 | 567 | 9143 子代ｂ：986 | 130 | 5427 6.順序交叉法(ox)（用于互換編碼）

從父代ａ隨機選一個編碼子串，放到子代ａ的對應位置；子代ａ空余的位置從父代ｂ中按ｂ的順序選取（與己有編碼不重復）。同理可得子代ｂ。父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：

子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 7.循環交叉（cx）法（用于互換編碼）cx同ox交叉都是從一個親代中取一些城市，而其它城市來自另外一個親代，但是二者不同之處在于：ox中來自第一個親代的編碼子串是隨機產生的，而cx卻不是，它是根據兩個雙親相應位置的編碼而確定的。

父代ａ：1 2 3 4 5 6 7 8 9 | | | | | 父代ａ：5 4 6 9 2 3 7 8 1 可得循環基因：1->5->2->4->9->1 用循環的基因構成子代ａ，順序與父代ａ一樣 1 2 4 5 9 用父代ｂ剩余的基因填滿子代ａ： 1 2 6 4 5 3 7 8 9 子代ｂ的編碼同理。（循環基因 5->1->9->4->2->5）

遺傳算子——變異 變異是指依據變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。ga中的變異運算是產生新個體的輔助方法，它決定了ga的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。

注：變異概率pm不能太小，這樣降低全局搜索能力；也不能太大，pm > 0.5，這時ga退化為隨機搜索。