iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 16
3

在結束介紹資料結構的部分後,我們將會進入學習一些和演算法相關的知識,今天就先來認識一下"五個"常見的演算法吧!

Brute force 暴力演算法

暴力法又稱為窮舉法,也就是將某個問題所有可能的答案/結果一一列舉出來,並根據問題條件去作篩選判斷,進而找出真正的解答。很像在解不知道密碼的密碼鎖,一個數字一個數字慢慢解...這樣
例子:
旅行推銷員問題
https://zh.wikipedia.org/wiki/%E6%97%85%E8%A1%8C%E6%8E%A8%E9%94%80%E5%91%98%E9%97%AE%E9%A2%98

Greedy 貪婪演算法

在進行解決問題的過程中,把問題分成數個子問題,每個子問題都選擇當前最佳最有利的選擇/解答,直到解決問題為止,便是貪婪演算法。
例子:
克魯斯克爾演算法
https://zh.wikipedia.org/wiki/克鲁斯克尔演算法

Divide and Conquer 分治法

將一個問題分成好幾個小問題,再將小問題的結果/答案合併。
例子:

  1. 快速排序法及合併排序法
  2. 河內塔

Dynamic Programming 動態規劃法

將一個問題分成好幾個小問題,並將小問題解出並記錄答案,最後根據小問題的答案取得整個問題的答案。
和分治法不同的地方是動態規劃法的小問題解答會被重複使用多次,並且這些答案都會有些關聯性,因此會把這些答案記錄下來,避免重複計算。
例子:

  1. 費氏數列,將第1項與第2項相加等於第3項,第2項與第3項相加等於第4項,依此類推
  2. 0/1背包問題
    https://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98

Backtracking 回溯法

採用試探的方式,一個步驟一個步驟的解決問題,當發現某步驟無法解決問題時,將會退回前幾個步驟,嘗試別的解決方法。
例子:

  1. N皇后問題
  2. 騎士走棋盤
    http://notepad.yehyeh.net/Content/Algorithm/Famous/KnightTour/KnightTour.php

五個演算法介紹到這邊結束,之後的連續五天將會每天介紹一種排序演算法!


上一篇
Day15-資料結構總結與一些免費學習資源
下一篇
Day17-排序法系列(一)-氣泡排序法
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言