演算法設計基礎

㈠ 演算法設計的5種基本方法

步驟/方式1
一、【分治法】
分治策略是：對於一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。
步驟/方式2
二、【動態規劃法】
最優化原理是動態規劃的基礎，任何一個問題，如果失去了這個最優化原理的支持，就不可能用動態規劃方法計算。
使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的階段，每個階段的狀態以及從前一個階段轉化到後一個階段之間的遞推關系。
步驟/方式3
三、【貪心演算法】所謂貪心演算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。貪心演算法的基本思路如下：
1. 建立數學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優解。
4.把子問題的解局部最優解合成原來解問題的一個解。
步驟/方式4
四、【回溯法】
回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
用回溯法解題的一般步驟：
（1）針對所給問題，定義問題的解空間；
（2）確定易於搜索的解空間結構；
（3）以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。
步驟/方式5
五、【分支限界法】
基本思想 ：分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。
常見的兩種分支限界法：
（1）隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。
（2）優先隊列式分支限界法：按照優先隊列中規定的優先順序選取優先順序最高的節點成為當前擴展節點。

㈡ 學習演算法分析與設計需要那些基礎(是否需要學習離散數學和線性代數)

演算法分析與設計，目前國內本科生和碩士生的教材好像都是從國外翻譯過來的。聽起來挺復雜的樣子，如果簡單地掌握和運用還是不難的，大部分內容在數據結構中都涉及過，實際編程中也運用比較多，難的在於演算法的理論研究，如21世紀的七大難題之一的NP問題就是演算法問題（涉及邏輯可滿足性問題）。

簡單地講需要的基礎有以下幾類：
1、基礎類（相對一般本科生而言）：（1）把數據結構學好了演算法就不難的，而數據結構其實就是圖論的運用，如果是非數學專業的學生可以看離散數學中的圖論部分。（2）演算法分析設計時間和空間復雜度的計算，常用的還是毛澤東的戰略思想——以空間換取時間。所以要學會簡單的數量級運算，涉及部分代數式和數論的知識。只要簡單掌握運算就可以了，不必深究。
2、提高型（研究生水平）：圖論、組合數學、數理邏輯學要專門學習，可以採用數學系本科生的圖論、組合數學、數理邏輯學等專業課的教材。其中組合數學中的組合設計在一定程度上和演算法設計有異曲同工之處。
3、研究型（專業研究）：這主要看自己的研究方向了，如果研究能力強的話可以在很短時間內可以把需要遇到的數學知識搞懂，沒有現成的固定模式。其中如研究NP問題，需要非常精深的邏輯學知識和數論基礎。但不管哪個研究方向，數學的縝密思維和推理能力都是必備的，這不是一朝一夕可以練就的，需要長時間的鍛煉。

以上僅個人一點點體會，僅供參考。