【算法】【殊途同归】搜索算法之（深度优先||广度优先）（约束条件||限界函数）

对于所谓的分支限界法和回溯法&＃xff0c;我们完全可以更加灵活&＃xff0c;请看表格。

前两种是我们常见的&＃xff0c;但是&＃xff0c;事实上&＃xff0c;这几种方式&＃xff0c; 怎么玩都行&＃xff0c;看实际需求了。

一般来说&＃xff0c;剪枝策略使用 约束条件 &＃43; 限界函数&＃xff0c;然后再配合深度优先或者广度优先&＃xff0c;是最好不过的了&＃xff0c;也就是后两种。

这样一来&＃xff0c;能够尽可能地剪枝&＃xff0c;以提高搜索效率。

而最后两种枚举法&＃xff0c;则没有剪枝策略&＃xff0c;是一种全局判定方式&＃xff0c;是最低效的。

总之&＃xff0c;这三种常见的搜索算法&＃xff0c;无非就是

• 枚举策略
  • 深度优先
  • 广度优先
• 剪枝策略
  • 约束条件
  • 限界函数

其中&＃xff0c;枚举策略有且仅有一种&＃xff0c;剪枝策略则随意&＃xff0c;然后就有了经典的枚举法&＃xff08;蛮力法&＃xff09;、回溯法和分支限界法。

搜索算法的学习策略

已经显而易见了&＃xff0c;这4种方式&＃xff0c;单独学明白&＃xff0c;懂逻辑&＃xff0c;会实现&＃xff0c;然后再组合起来使用就OK了。

预测思想&＃xff1a;限界函数

限界函数是通过对子树未来的上界/下界的预测&＃xff0c;来评定是否需要继续生成&＃xff0c;方法就是按照平均值排序后&＃xff0c;乘以剩余容量。

具体实例可以参考

1. 0/1 knapsack problem using branch and bound

2. 分支限界法-01背包问题

限界函数和约束条件的目标

1. 约束条件&＃xff0c;是为了去掉不可行解&＃xff0c;从而进行剪枝
2. 限界函数&＃xff0c;是为了去掉非最优解&＃xff0c;从而剪枝&＃xff0c;但是它依然是可行解

明确了这两个目标&＃xff0c;就能够更加针对性选择了&＃xff0c;如果题目求多个可行解&＃xff0c;那么就不可能使用限界函数。