算法策略是指在問題空間中隨機搜尋所有可能的解決問題的方法，直至選擇一種有效的方法解決問題，在行政規劃，數學驗證及物理檢測等領域有著非常重要的作用。
基本介紹
- 中文名：算法策略
- 性質：搜尋所有可能的解決問題的方法
- 實質是：分治思想和解決冗餘
- 種類：分治算法 貪心算法
算法種類,分治算法,貪心算法,動態規划算法,回溯算法,算法策略間的關係,共同點,
算法種類
分治算法
分治算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。
貪心算法
在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。
動態規划算法
動態規劃的實質是分治思想和解決冗餘，因此，動態規劃是一種將問題實例分解為更小的、相似的子問題，並存儲子問題的解而避免計算重複的子問題，以解決最最佳化問題的算法策略。
動態規劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，並通過求解子問題產生一個全局最優解。其中貪心法的當前選擇可能要依賴已經作出的所有選擇，但不依賴於有待於做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的 (即不包含公共的子子問題)，因此一旦遞歸地求出各子問題的解後，便可自下而上地將子問題的解合併成問題的解。但不足的是，如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重複地解公共的子問題。
解決上述問題的辦法是利用動態規劃。該方法主要套用於最最佳化問題，這類問題會有多種可能的解，每個解都有一個值，而動態規劃找出其中最優(最大或最小)值的解。若存在若干個取最優值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優解，但與分治法和貪心法不同的是，動態規劃允許這些子問題不獨立，(亦即各子問題可包含公共的子子問題)也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，並將結果保存起來，避免每次碰到時都要重複計算。
因此，動態規劃法所針對的問題有一個顯著的特徵，即它所對應的子問題樹中的子問題呈現大量的重複。動態規劃法的關鍵就在於，對於重複出現的子問題，只在第一次遇到時加以求解，並把答案保存起來，讓以後再遇到時直接引用，不必重新求解。
回溯算法
回溯法是一個既帶有系統性又帶有跳躍性的的搜尋算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜尋解空間樹。算法搜尋至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜尋，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜尋。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜尋遍才結束。而回溯法在用來求問題的任一解時，只要搜尋到問題的一個解就可以結束。這種以深度優先的方式系統地搜尋問題的解的算法稱為回溯法，它適用於解一些組合數較大的問題。
其基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜尋整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜尋向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜尋，直至找到所要求的解或解空間中已沒有活結點時為止。
算法策略間的關係
1、對問題進行分解的算法策略——分治法與動態規劃法
共同點
（1）分治法與動態規劃法實際上都是遞歸思想的運用
（2）二者的根本策略都是對問題進行分解，找到大規模與小規模的關係，然後通過解小規模的解，得出大規模的解
不同點： 適用於分治法的問題分解成子問題後，各子問題間無公共子子問題，而動態規劃法相反。
動態規劃法 = 分治算法思想 + 解決子問題間的冗餘情況
2、多階段逐步解決問題的策略——貪心算法和動態規劃法
貪心算法：每一步都根據策略得到一個結果，並傳遞到下一步，自頂向下，一步一步地做出貪心決策。
動態規划算法：每一步決策得到的不是一個唯一結果，而是一組中間結果（且這些結果在以後各步可能得到多次引用），只是每一步都使問題的規模逐步縮小，最終得到問題的一個結果。
