FIFO、LIFO和LC Branch and Bound有什么区别？
问问题
26445 次
2 回答
5
Branch & Bound 通过使用估计的边界来限制可能解决方案的数量，在整个搜索空间内发现分支。不同的类型（FIFO、LIFO、LC）定义了不同的“策略”来探索搜索空间并生成分支。
FIFO（先进先出）：总是使用队列中最老的节点来扩展分支。这导致了广度优先搜索，首先访问深度 d 的所有节点，然后访问深度 d+1 的任何节点。
LIFO（后进先出）：总是使用队列中最年轻的节点来扩展分支。这导致深度优先搜索，其中分支通过在特定深度发现的每个第一个子节点进行扩展，直到到达叶节点。
LC（最低成本）：根据给定的成本函数，由添加最低附加成本的节点扩展分支。因此，遍历搜索空间的策略由成本函数定义。
于 2017-10-27T10:35:08.947 回答
2
唯一的区别在于活动节点的实现。在 LC 分支定界中，我们开始探索的第一个节点是那个时刻向我们保证最佳解决方案的节点。例如，在 0/1 背包问题中，使用 LC 分支定界，我们将开始探索的第一个子节点将是提供最大成本的子节点。
在 FIFO 分支定界中，顾名思义，子节点以先进先出的方式进行探索。我们从第一个子节点开始探索节点。在 LIFO 分支定界中，我们从最后一个开始探索节点。最后一个子节点是首先要探索的子节点。
于 2017-05-17T06:13:42.633 回答