最小成本分支限界法如何决定接下来探索哪个节点？

适用条件

• 适用于使用分支限界法的最小成本策略时。
• 为问题定义了成本函数。

理解与推导

1. 使用依赖于问题的成本函数计算每个可用节点的成本。
2. 比较当前前沿中节点的成本。
3. 选择成本最小的节点。
4. 扩展所选节点以生成其子节点。

例子

讲师解释说：“我应该接下来探索成本最小的节点。最小成本，这就是最小成本分支限界法。”在示例中，扩展了节点 $2 (C=12)$，生成了节点 $6 (C=8)$ 和节点 $7 (C=7)$。然后选择节点 7，因为它的成本最小。

容易误解的地方

• 假设算法按节点生成的顺序（FIFO）或逆序（LIFO）探索节点。
• 认为成本是任意的，而不是从特定成本函数得出的。

观看对应讲解

继续追问

• 为什么最小成本分支限界法被认为比 FIFO 或 LIFO 更高效？
• 在树遍历中，FIFO、LIFO 和最小成本策略有什么区别？
• 如何构建三机器生产问题的总成本目标函数？