這里寫目錄標題
- 五大常規演算法
- 動態規劃演算法
- 回溯演算法
- 貪心演算法
- 分支定界法
五大常規演算法
兩部分組成:
分（divide）：遞回解決較小的問題
治（conquer）：然后從子問題的解構建原問題的解
三個步驟
- 分解（Divide）：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
- 解決（Conquer）：若子問題規模較小而容易被解決則直接解決，否則遞回地解各個子問題；
- 合并（Combine）：將各個子問題的解合并為原問題的解.
將 16 枚硬幣分為左右兩個部分，各為 8 個硬幣，分別稱重，必然會有一半輕一半重，而我們要的就是輕的那組,重 的舍去，接下來我們繼續對輕的進行五五分
動態規劃演算法
分治法核心思想:從上往下分析問題，大問題可以分解為子問題，子問題中還有更小的子問題
- 動態規劃也是一種分治思想，但與分治演算法不同的是，分治演算法是把原問題分解為若干子問題， 自頂向下，求解各子問題，合并子問題的解從而得到原問題的解，
- 動態規劃也是自頂向下把原問 題分解為若干子問題，不同的是，然后自底向上，先求解最小的子問題，把結果存盤在表格中， 在求解大的子問題時，直接從表格中查詢小的子問題的解，避免重復計算，從而提高演算法效率，
什么時候要用動態規劃？
- 如果要求一個問題的最優解（通常是最大值或者最小值），而且該問題能夠分解成若干個子問題， 并且小問題之間也存在重疊的子問題，則考慮采用動態規劃，
怎么使用動態規劃？
- 判題題意是否為找出一個問題的最優解
- 從上往下分析問題，大問題可以分解為子問題，子問題中還有更小的子問題
- . 從下往上分析問題 ，找出這些問題之間的關聯
- 討論底層的邊界問題
- 解決問題（通常使用陣列進行迭代求出最優解）
回溯演算法
- 在問題的解空間中，按深度優先遍歷策略，從根節點出發搜索解空間樹，
- 演算法搜索至解空間 的任意一個節點時，先判斷該節點是否包含問題的解，
- 如果確定不包含，跳過對以該節點為根的 子樹的搜索，逐層向其祖先節點回溯，否則進入該子樹，繼續深度優先搜索，
- 回溯法解問題的所有解時，必須回溯到根節點，且根節點的所有子樹都被搜索后才結束，回 溯法解問題的一個解時，只要搜索到問題的一個解就可結束，
回溯的基本步驟:
- 定義問題的解空間
- 確定易于搜索的解空間結構
- 以深度優先搜索的策略搜索解空間，并在搜索程序中盡可能避免無效搜索
貪心演算法
特點:
- 貪婪演算法(貪心演算法)是指在對問題進行求解時，在每一步選擇中都采取最好或者最優(即最有利)的選擇，從而希望能夠導致結果是最好或者最優的演算法，
- 貪婪演算法所得到的結果往往不是最優的結果(有時候會是最優解)，但是都是相對近似(接近)最 優解的結果，
- 貪婪演算法并沒有固定的演算法解決框架，演算法的關鍵是貪婪策略的選擇，根據不同的問題選擇 不同的策略，
基本思路:
- 建立數學模型來描述問題
- 把求解的問題分成若干個子問題
- 對每一子問題求解，得到子問題的區域最優解
- 把子問題對應的區域最優結合成原來整個問題的一個近似最優解
分支定界法
特點:
- 分支定界 (branch and bound) 演算法是一種在問題的解空間上搜索問題的解的方法，
- 但與回溯演算法不同，分支定界演算法采用廣度優先或最小耗費優先的方法搜索解空間樹，并且，在分支定界算 法中，每一個活結點只有一次機會成為擴展結點，
利用分支定界演算法對問題的解空間樹進行搜索，它的搜索策略是：
- 產生當前擴展結點的所有孩子結點；
- 在產生的孩子結點中，拋棄那些不可能產生可行解（或最優解）的結點；
- 將其余的孩子結點加入活結點表；
- 從活結點表中選擇下一個活結點作為新的擴展結點，
- 如此回圈，直到找到問題的可行解（最優解）或活結點表為空，
從活結點表中選擇下一個活結點作為新的擴展結點，根據選擇方式的不同，分支定界演算法通 常可以分為兩種形式：
- FIFO(First In First Out) 分支定界演算法：按照先進先出原則選擇下一個活結點作為擴展結 點，即從活結點表中取出結點的順序與加入結點的順序相同，
- 最小耗費或最大收益分支定界演算法：在這種情況下，每個結點都有一個耗費或收益，
- 假如要查找一個具有最小耗費的解，那么要選擇的下一個擴展結點就是活結點表中具有最小 耗費的活結點.
- 假如要查找一個具有最大收益的解，那么要選擇的下一個擴展結點就是活 結點表中具有最大收益的活結點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/280237.html
標籤：其他