iT邦幫忙

2021 iThome 鐵人賽

0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 35

【Day35】[演算法]-常見的演算法策略Algorithmic Patterns

分治法(Divide and conquer)

又稱分而治之法,是最常被使用的策略方式,原理是將一個難以直接解決的大問題,依據相同的概念分割成多個子問題,再各個擊破,分而治之,不斷地將子問題縮小,最後再將各子問題的解答合併起來。

之前介紹多種的演算法,就是運用這樣的策略。
合併排序
快速排序
基數排序
二分搜尋


動態規劃法(Dynamic Programming)

動態規劃法類似上述的分治法,依樣是將大問題分割成多個子問題來解決,只是有些子問題可能是重複的,所以會發生重複計算的問題,動態規劃與分治法最大不同在於會將重複計算的子問題將其記憶化儲存,來解決重複計算的問題,用空間換取時間的概念來加速執行效能。

之前介紹改良版費波那契數列就是運用這樣的策略。


貪婪法 (Greed Algorithm)

又稱貪心法,原理是在每一次解決步驟時都以貪心為原則,採取當下最有利的選擇,當步驟都結束後進而希望是最有利的解答。

假設今天你今天用一張100元鈔票買了18元飲料,你希望全部找的零錢硬幣數量要是最少,該如何找錢?

一開始先選擇50元 x1
接著10元 x3
再來5元 x0
最後1元 x2

總共6枚硬幣,最佳解答。


回溯法(Backtracking)

原理是先列出此階段的所有分支可能性,接著排除掉不可能為解答的分支,再來往其中一個分支執行,若此階段已經確定所有分支都不為解答時,則退回上一階段,往其他分支執行,來避免多餘無效的步驟。

深度優先搜尋,就是運用這樣的策略。


分支界定法(Branch and bound)

有點類似地毯式搜索,列出此階段的所有分支可能性,開始執行此階段所有分支,若此階段都不為解答時,其中一個分支成為新階段,重複上述步驟執行。

廣度優先搜尋,就是運用這樣的策略。


上一篇
【Day34】[演算法]-費波那契數列Fibonacci Sequence
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言