算法思想

sshe 發布于2019-08-15 17:50 / 3200人閱讀

摘要：基礎算法思想類別遞推枚舉遞歸分治貪婪回溯試探模擬遞推遞推分類順推法從已知條件出發，逐步推算出要解決問題的方法。貪心算法的局限不能保證最后的解是最優的不能求最大最小解問題只能求滿足某些約束條件的可行解范圍。

基礎算法思想類別

遞推

枚舉

遞歸

分治

貪婪

回溯（試探）

模擬

遞推 遞推分類

順推法：從已知條件出發，逐步推算出要解決問題的方法。

逆推法：從已知結果出發，用迭代表達式逐步推算出問題開始的條件，即順推法的逆過程。

遞推算法的經典運用

斐波那契數列（順推法）：由n-2，n-1項得到第n項銀行存款（逆推法）

枚舉

將問題的所有可能答案都列舉出來，根據判斷條件判斷此答案是否合適，一般用循環實現。

枚舉算法的經典運用

百錢買百雞、填寫運算符

遞歸

遞歸算法在函數或子過程的內部，直接或間接調用自己的算法

遞歸算法實際上是把問題轉化為規模縮小了的同類問題的子問題，然后再遞歸調用函數或過程來表示問題的解

注意：必須有一個明確的遞歸結束條件；如果遞歸次數過多，容易造成棧溢出。

遞歸算法的經典運用

漢諾塔問題、階乘問題

分治

　　將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。只要求出子問題的解，就可得到原問題的解。

分治算法的基本步驟

分解，將要解決的問題劃分成若干個規模較小的同類問題

求解，當子問題劃分得足夠小時，用較簡單的方法解決

合并，按原問題的要求，將子問題的解逐層合并構成原問題的解

分治算法的經典運用

大數相乘問題、比賽日程安排

貪心

從問題的某一個初始解出發，逐步逼近給定的目標，以便盡快求出更好的解。

貪心算法的局限

不能保證最后的解是最優的；

不能求最大最小解問題；　　　

只能求滿足某些約束條件的可行解范圍。

貪心算法的基本過程

　1. 從問題的某一初始解出發　　　

while能向給定總目標前進一步　　

求出可行解的一個解元素　　　　

由所有解元素組合成問題的一個可行解

貪心算法的經典運用

裝箱問題、找零方案

試探

　　在試探算法中，放棄當前候選解，并繼續尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。

　　（為求得問題的正確解，會先委婉地試探某一種可能情況。在進行試探過程中，一旦發現原來選擇的假設情況是不正確的，馬上會自覺地退回一步重新選擇，然后繼續向前試探。反復進行，直到得到解或證明無解時才死心）

試探算法的基本步驟

　　　　1.針對所給問題，定義問題的解空間

　　　　2.確定易于搜索的解空間結構

　　　　3.以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索

試探算法的經典運用

八皇后問題、29選7彩票組合

模擬

對真實事物或者過程的虛擬。

模擬算法的經典運用

猜數字游戲、擲骰子問題

云服務器 GPU云服務器最短路徑算法思想最優合并問題的算法思想編程思想 python思想

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69477.html

基本算法思想：遞歸+分治+動態規劃+貪心+回溯+分支限界

摘要：代碼實現見下面評論對應代碼動態規劃基本思想和分治法基本思想有共同的地方，不同的是子問題往往不是獨立的，有事母問題要借助子問題的解來判斷，因此把已經計算好的問題記錄在表格中，后續如果需要查詢一下，可以避免重復計算，這是動態規劃的基本思想。作者：心葉時間：2018-05-01 19:28 本文對應github地址：https://github.com/yelloxing/... 以上實現...

EscapedDog 2019-08-26 11:52 評論0 收藏0
??思維導圖整理大廠面試高頻數組10: 3種方法徹底解決中位數問題, 力扣4??

此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...

XanaHopper 2021-09-10 10:51 評論0 收藏0
算法系列——JavaScript中廣度優先搜索思想實現

摘要：散列表上面的地圖向我們展示了如何用廣度優先搜索的思想找到北京到廣州的最短路線。在廣度優先搜索中，我們需要用到隊列的這種思想來實現查找。建立了下面這個模型武漢廣州西藏上海上海武漢廣州代碼完整實現，利用遞歸和廣度優先搜索的思想實現。什么是廣度優先搜索？如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。假設看這篇文章的都和我一樣是個前端工程師，我們要從廣度優先搜索（BFS）中學到什么...

everfly 2019-08-21 17:36 評論0 收藏0
關于Web開發中“程序=數據結構+算法”的思考

摘要：在這里統一說開發，可能有失頗偏，畢竟我后端一直都是用實現的，沒用過也沒用過，但我想大體都是一樣都，我就此闡述一下我所認為的程序數據結構算法。這套的想法主要目的是把復雜程序盡量做簡化，并以數據和算法的思想去思考程序本身。在這里統一說Web開發，可能有失頗偏，畢竟我后端一直都是用PHP實現的，沒用過.net也沒用過java，但我想大體都是一樣都，我就此闡述一下我所認為的程序=數據結構+算...

fish 2019-06-27 15:58 評論0 收藏0