常用的演算法設計策略有哪些

常見的演算法設計策略：

1、分治

##分治法的設計想法是，將一個難以直接解決的大問題，分割成k個規模較小的子問題，這些子問題相互獨立，且與原問題相同，然後各個擊破，分而治之。

分治法常與遞歸結合使用：透過反覆應用分治，可以使子問題與原問題類型一致而規模不斷縮小，最終使子問題縮小到很容易求出其解，由此自然導致遞歸演算法。

2、動態規劃

動態規劃法與分治法類似，其基本想法也是將原始問題分解成若干個子問題。與分治法不同的是，其分解出的子問題往往不是相互獨立的。這種情況下若用分治法會對一些子問題進行多次求解，這顯然是不必要的。動態規劃法在解法過程中把所有已解決的子問題的答案都保存起來，從而避免對子問題重複求解。

動態規劃常用於解決最佳化問題。對一個最佳化問題可否應用動態規劃法，取決於該問題是否具有以下兩個性質：

最優子結構性質：

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

子問題重疊性質：

子問題重疊性質是指由原問題分解出的子問題不是相互獨立的，存在重疊現象。

3、貪心

當一個問題具有最優子結構性質時，可用動態規劃法求解。但有時會有比動態規劃更簡單更直接效率更高的演算法——貪心法。貪心法總是做出在當下看來最好的選擇，也就是說貪心法並不是從整體最優考慮，它所做的選擇只是在某種意義上的局部最優選擇。

4、回溯

回溯法是對問題的解空間樹進行深度優先搜索，但是在對每個節點進行DFS之前，要先判斷該節點是否有可能包含問題的解。如果肯定不包含，則跳過對以該節點為根的子樹的搜索，逐層向其祖先節點回溯。如果有可能包含，則進入該子樹，進行DFS。

5、分支限界

分支限界法的搜尋策略是，在當前節點處，先生成其所有的子節點(分支)，並為每個滿足限制條件的子節點計算一個函數值(限界)，再將滿足限制條件的子節點全部加入解空間樹的活結點優先佇列。然後再從目前的活節點優先佇列中選擇優先權最大的節點(節點的優先權由其限界函數的值來決定) 為新的目前節點。重複這個過程，直到到達一個葉節點為止。所到達的葉節點就是最優解。                                                 

以上是常用的演算法設計策略有哪些的詳細內容。更多資訊請關注PHP中文網其他相關文章！