DSA - 回溯演算法

回溯演算法是一種問題求解方法，它嘗試所有可能的解決方案，並選擇最佳或所需的解決方案。通常，它用於解決具有多個解決方案的問題。術語“回溯”表明，對於給定的問題，如果當前解決方案不合適，則將其消除，然後回溯以嘗試其他解決方案。

什麼時候使用回溯演算法？

回溯演算法可用於以下問題：

問題有多個解決方案或需要找到所有可能的解決方案。
當給定問題可以分解成與原始問題相似的較小子問題時。
如果問題有一些約束或規則必須由解決方案滿足。

回溯演算法如何工作？

回溯演算法探索各種路徑以找到將我們帶到解決方案的序列路徑。沿著這些路徑，它建立一些小的檢查點，如果找不到可行的解決方案，問題可以從這些檢查點回溯。此過程持續到找到最佳解決方案。

在上圖中，綠色是起點，藍色是中間點，紅色是沒有可行解決方案的點，灰色是最終解決方案。

當回溯演算法到達解決方案的結尾時，它會檢查這條路徑是否是解決方案。如果是解決方案路徑，則返回該路徑；否則，它會回溯到前一步以找到解決方案。

演算法

以下是回溯演算法：

1. Start
2. if current_position is goal, return success.
3. else
4. if current_position is an end point, return failed.
5. else-if current_position is not end point, explore and repeat above steps.
6. Stop

回溯演算法的複雜度

通常，回溯演算法的時間複雜度是指數級的 (O(kⁿ))。在某些情況下，觀察到其時間複雜度是階乘的 (O(N!))。

回溯問題的型別

回溯演算法應用於某些特定型別的問題。如下所示：

判定問題 - 用於找到問題的可行解。
最佳化問題 - 用於找到可以應用的最佳解決方案。
列舉問題 - 用於找到問題的所有可行解的集合。

回溯演算法的例子

以下列表顯示了回溯演算法的示例：

列印頁面