(1)回溯求解0/1背包问题,虽剪枝减少了搜索空间,但整个搜索按深度优先机械进行,是盲目搜索(不可预测本结点以下的结点进行的如何)。
(2)回溯求解TSP也是盲目的(虽有目标函数,也只有找到一个可行解后才有意义)
(3)分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界[down, up];然后按照广度优先策略遍历问题的解空间树,在某一分支上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值(对最小化问题,估算结点的down,对最大化问题,估算结点的up)。如果某孩子结点的目标函数值超出目标函数的界,则将其丢弃(从此结点生成的解不会比目前已得的更好),否则入待处理表。