iT邦幫忙

2024 iThome 鐵人賽

DAY 1
0

回溯法Backtracking)是一種暴力搜尋法,主要通過逐一嘗試所有可能的解來解決問題,並增加中止條件判斷來提前排除不可行的解,也可說是一種優化版的枚舉法。

在這個過程中,回溯法會將每種可能性列出,再透過遞迴來試探所有可能的解,遇到符合中止條件的選擇時,會停止繼續深入搜索,然後回退到上一個選擇點,嘗試其他選擇。

回溯法適合解決各類組合問題、切割問題、子集問題、排列問題(無需排序的組合問題)以及棋盤問題等。由於回溯法在解空間中逐層深入並探索所有可能性,因此它也可以視為深度優先搜尋法 (DFS) 的一種應用。

範例說明

  • 問題:請列出所有由A、B、C組成的排列組合。
  • 中止條件:當出現重複元素則停止深入列舉。
  • 解法:我們使用回溯法來逐步生成排列。每次從未使用過的字母中選擇一個加入當前排列,直到排列的長度達到3。在生成排列的過程中,如果觸發中止條件,也就是當前的選擇會導致字母重複出現,就會停止深入列舉並回溯到上一步,嘗試其他可能的字母。重複這個過程直到列出所有可能。如下圖所示:

https://ithelp.ithome.com.tw/upload/images/20240915/20168780buOWsPFDeD.png


優點:

  • 邏輯直觀易理解:回溯法試探所有可能的選擇,邏輯直觀,容易理解和實現。
  • 適用範圍廣泛:可以解決多種問題,包括組合問題、排列問題、切割問題等。尤其適合解決那些需要考慮所有可能解的問題。
  • 排除所有不可能解:回溯法能夠在其出現不可行解法時及時中止,以防深入造成時間浪費。

缺點:

  • 時間複雜度高:在最壞情況下,回溯法需要遍歷所有可能的選擇,時間複雜度會很高,造成效率較低,不如預期。
  • 僅適合解決小規模問題:雖然回溯法適用於許多類型的問題,但在處理非常大問題時,可能需要更高效的算法。

參考資料:


下一篇
Day2 Backtracking回朔 - 題目1:39. Combination Sum
系列文
Java刷題A:Leetcode Top 100 Liked26
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言