先把所有結果產生出來,最後再挑選最佳解或是透過條件篩選合格解
可以在過程中透過條件判斷是否要繼續,減少不必要的計算
挑選當下最好的先走( Branch ),往下走的過程中發現不可能更好回頭 ( Bound )
Enumeration | Backtracking | Branch&Bound | |
---|---|---|---|
適合情境 | 最佳解&合格解 | 合格解 | 最佳解 |
篩選條件 | 參數 或 全部比較 | 參數 | 紀錄最佳值 |
篩選機制 | 結果產生後 | 進入分枝前 | 進入分枝前 |
分枝選擇 | 陣列順序 | 陣列順序 | Node 之間權重 |
進入分枝 | 直接進入 | 直接進入 | 先排序分枝權重,再進入分枝 |
探索模式 | BFS、DFS | BFS、DFS | DFS |
效率 | 極差 | 佳 | 佳 |