解決問題的方式有多種，之前介紹過在解空間中用搜索技術來尋找合適的答案。解決問題本質上也是從解空間中的眾多解中找到那個最適合的，雅虎、百度、谷歌都是利用搜索技術來找答案的典型創業成功的案例。除了搜索還有沒有其他的方式找到答案呢？還有一種方式，那就約束傳播技術。
約束傳播有點像動態規劃，它會有一個約束庫，每走一步都會檢索庫中的約束條件，查看是否滿足。最典型的地圖染色問題：用四種顏色填充地圖，要求相鄰的省份顏色不同。比如美國地圖，有50多個州，每個州有四種選擇那就是至少4^50（2^100）種選擇，如果用搜索算法來解的化將是災難性的。這時候如果用約束傳播的機制，就是從某一個州開始任選一種顏色填充，然後檢查約束是否滿足，不滿足約束的回溯上一步將會大大提高計算效率，它核心思想是不要求全局的信息，通過局部計算就可以達到全局的最優，核心就是檢查約束是否滿足。很多最優化的算法都這個思想，通過給最小化函數增加正則項來降低解空間的不確定，而約束正是在解空間生效的條件，本質上也是一種剪枝的效果。
分享到:
閱讀更多 老郭講算法 的文章
