1. 分治、動(dòng)態(tài)規(guī)劃的局限性

• 沒有合適的分割方式時(shí)，就不能使用分治法；
• 沒有合適的子問題或占用內(nèi)存空間太大時(shí)，就不能用動(dòng)態(tài)規(guī)劃；

此時(shí)還需要回到最基本的窮舉搜索算法。

窮舉搜索（exhaustive search）會(huì)把生成答案的過程分為幾個(gè)選擇的過程，之后利用遞歸調(diào)用完成各個(gè)選擇項(xiàng)，由此實(shí)現(xiàn)其目的。此時(shí)，所有子問題的答案和已完成答案的集合就是搜索空間（search space）。例如旅行商（TSP）問題，已訪問過的各個(gè)城市的目錄和當(dāng)前位置就構(gòu)成了搜索空間的 1 個(gè)元素。

但對(duì)窮舉搜索而言，即使問題的規(guī)模只是略有增加，也將無法適用窮舉搜索法。

將窮舉搜索法這種在有限的搜索空間內(nèi)搜索出答案的算法命名為組合搜索。

• 窮舉搜索；
• 有限搜索空間：
  
  • 剪枝（pruning）
  • 盡早地求出適當(dāng)解（proper solution），會(huì)改變搜索的順序，或在搜索前使用貪心算法優(yōu)先求出適當(dāng)答案；

轉(zhuǎn)載于:https://www.cnblogs.com/mtcnn/p/9423826.html

總結(jié)

以上是生活随笔為你收集整理的组合搜索（combinatorial search）在算法求解中的应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。