分支机构

Question

有人可以为我解释分支和绑定搜索技术吗？我需要使用分支定界搜索算法找到从任何起始节点到任何随机图的结束节点的最小成本的路径.

Answer 1

B&B的基本理念是:

1. 在解决优化问题时("找到满足标准Y的X以便最小化成本f(X)"),您可以逐个构建解决方案 - 在任何时间点,您都有一个部分解决方案,其中包含成本.
2. 如果问题的性质使得部分解决方案的成本只能保持不变或者随着您继续向其添加部分而增加,那么您就知道如果已经存在的话,那么继续将部分添加到部分解决方案中是没有意义的完全解决方案,成本更低.在这种情况下,您可以放弃(或"修剪"或"深入")进一步处理此部分解决方案.

许多问题具有后一种性质,使得B&B成为一种广泛适用的算法技术.

搜索解决方案的过程可以由搜索树表示,其中根节点表示尚未做出决定的起始点,并且从节点引出的每个边表示关于要包括在部分解中的某事的决定.每个节点都是部分解决方案,包括从根到该节点的决策(边缘).

示例:如果我们想要解决数独谜题,则根节点将代表具有填充的最初提供的数字的板; 此根可能有9条边,每条边代表决定将数字1-9分配给左上角的单元格.这9个部分求解节点中的每一个可以具有8个分支,表示对位置(1,2)处的单元的有效分配,等等.通常,每个边表示程序中的递归步骤.

对于B&B,在最好的情况下,很早就找到了一个很好的解决方案,这意味着可以在根部附近修剪搜索树中没有希望的区域; 但在最坏的情况下,将生成整个有效解决方案树.因此,B&B通常仅用于解决没有更快算法的问题(例如NP难问题).