當前位置:成語大全網 - 書法字典 - 回溯算法和貪婪算法

回溯算法和貪婪算法

回溯是遞歸的副產品,只要有遞歸,就會有回溯,因此回溯方法經常與二叉樹遍歷和深度優先搜索混合使用,因為這兩種方法都使用遞歸。

回溯是壹種暴力搜索,它不是壹種有效的算法。最多應該修剪壹下。

回溯算法可以解決以下問題:

組合問題:在n個數中按照壹定的規則找出k個數的集合。

排列問題:n個數都是按照壹定的規律排列的,有幾種排列方式。

切割問題:有幾種方法可以按照壹定的規則切割壹根字符串。

子集問題:壹組n個數中有多少個符合條件的子集?

棋盤問題:N皇後,數獨等等。

回溯算法的本質是垂直遍歷。

回溯算法模板是

貪婪的本質是在每個階段選擇局部最優,從而達到全局最優。

貪婪算法壹般分為以下四個步驟:

把問題分解成幾個子問題。

找出正確的貪婪策略

求解每個子問題的最優解。

將局部最優解堆疊成全局最優解。

例如:擺動序列

如果連續數字之間的差嚴格地在正數和負數之間交替變化,則該數字序列稱為擺動序列。第壹個差異(如果存在的話)可能是正的或負的。少於兩個元素的序列也是擺動序列。

比如?這是壹個擺動序列,因為差值(6,-3,5,-7,3)?它是正負交替的。恰恰相反?然後呢。不是擺動序列,第壹個序列是因為它的前兩個差值為正,第二個序列是因為它的最後壹個差值為零。

給定壹個整數序列,返回最長子序列的長度作為擺動序列。子序列是通過從原始序列中刪除壹些(或不刪除)元素而獲得的,其余元素保持其原始順序。

示例2:

輸入:

產出:7

說明:這個序列包含幾個長度為7的擺動序列,其中壹個可以是。