【算法】【殊途同归】搜索算法之（深度优先 || 广度优先） （约束条件 || 限界函数）
對(duì)于所謂的分支限界法和回溯法，我們完全可以更加靈活，請(qǐng)看表格。
| √ | √ | 回溯法 | 局部判定 | ||
| √ | √ | √ | 分支限界法 | 局部判定 | |
| √ | √ | √ | 加限界的回溯法 | 局部判定 | |
| √ | 枚舉法 | 全局判定 | |||
| √ | 枚舉法 | 全局判定 |
前兩種是我們常見(jiàn)的，但是，事實(shí)上，這幾種方式， 怎么玩都行，看實(shí)際需求了。
一般來(lái)說(shuō)，剪枝策略使用 約束條件 + 限界函數(shù)，然后再配合深度優(yōu)先或者廣度優(yōu)先，是最好不過(guò)的了，也就是后兩種。
這樣一來(lái)，能夠盡可能地剪枝，以提高搜索效率。
而最后兩種枚舉法，則沒(méi)有剪枝策略，是一種全局判定方式，是最低效的。
總之，這三種常見(jiàn)的搜索算法，無(wú)非就是
- 枚舉策略
- 深度優(yōu)先
- 廣度優(yōu)先
- 剪枝策略
- 約束條件
- 限界函數(shù)
| 深度優(yōu)先 | 約束條件 |
| 廣度優(yōu)先 | 限界函數(shù) |
其中，枚舉策略有且僅有一種，剪枝策略則隨意，然后就有了經(jīng)典的枚舉法（蠻力法）、回溯法和分支限界法。
搜索算法的學(xué)習(xí)策略
已經(jīng)顯而易見(jiàn)了，這4種方式，單獨(dú)學(xué)明白，懂邏輯，會(huì)實(shí)現(xiàn)，然后再組合起來(lái)使用就OK了。
預(yù)測(cè)思想：限界函數(shù)
限界函數(shù)是通過(guò)對(duì)子樹(shù)未來(lái)的上界/下界的預(yù)測(cè)，來(lái)評(píng)定是否需要繼續(xù)生成，方法就是按照平均值排序后，乘以剩余容量。
具體實(shí)例可以參考
0/1 knapsack problem using branch and bound
分支限界法-01背包問(wèn)題
限界函數(shù)和約束條件的目標(biāo)
明確了這兩個(gè)目標(biāo)，就能夠更加針對(duì)性選擇了，如果題目求多個(gè)可行解，那么就不可能使用限界函數(shù)。
總結(jié)
以上是生活随笔為你收集整理的【算法】【殊途同归】搜索算法之（深度优先 || 广度优先） （约束条件 || 限界函数）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
