Python 算法類

算法是明確的步驟，應(yīng)該通過處理零個或多個輸入給我們一個明確的輸出。這導(dǎo)致了設(shè)計(jì)和編寫算法的許多方法。據(jù)觀察，大多數(shù)算法可以分為以下幾類。

貪婪算法

貪婪算法試圖找到一個局部最優(yōu)解，這可能最終導(dǎo)致全球優(yōu)化的解決方案。但是，通常貪婪算法不提供全局優(yōu)化的解決方案。

所以貪婪算法在那個時候?qū)ふ乙粋€簡單的解決方案，而不考慮它是如何影響未來的步驟的。它與人類如何解決問題的方式類似，不需要通過所提供的輸入的完整細(xì)節(jié)。

大多數(shù)網(wǎng)絡(luò)算法都使用貪婪的方法。這里列出了其中幾個 -

• 旅行推銷員問題
• Prim的最小生成樹算法
• 克魯斯卡爾的最小生成樹算法
• Dijkstra的最小生成樹算法

分而治之

這類算法涉及將給定的問題分成更小的子問題，然后獨(dú)立地解決每個子問題。當(dāng)問題不能進(jìn)一步細(xì)分時，我們開始將解決方案合并到每個子問題上，以解決更大的問題。

分而治之算法的重要例子是 -

• 合并排序
• 快速排序
• 克魯斯卡爾的最小生成樹算法
• 二進(jìn)制搜索

分而治之

動態(tài)編程涉及將較大的問題分成較小的問題，但不同于分而治之，它不涉及獨(dú)立解決每個子問題。相反，較小的子問題的結(jié)果被記住并用于相似或重疊的子問題。大多數(shù)情況下，這些算法用于優(yōu)化。在解決手中的子問題之前，動態(tài)算法將嘗試檢查先前解決的子問題的結(jié)果。

動態(tài)算法的動機(jī)是對問題進(jìn)行全面優(yōu)化，而不是局部優(yōu)化。

動態(tài)編程算法的重要例子是 -

• 斐波那契數(shù)列
• 背包問題
• 河內(nèi)塔