What is the difference between FIFO Branch and Bound, LIFO Branch and Bound and LC Branch and Bound?

algorithm branch-and-bound
Satender picture Satender · Apr 5, 2017 · Viewed 24k times · Source

What is the difference between FIFO, LIFO and LC Branch and Bound?

Answer

rival picture rival · Oct 27, 2017

Branch & Bound discovers branches within the complete search space by using estimated bounds to limit the number of possible solutions. The different types (FIFO, LIFO, LC) define different 'strategies' to explore the search space and generate branches.

FIFO (first in, first out): always the oldest node in the queue is used to extend the branch. This leads to a breadth-first search, where all nodes at depth d are visted first, before any nodes at depth d+1 are visited.

LIFO (last in, first out): always the youngest node in the queue is used to extend the branch. This leads to a depth-first search, where the branch is extended through every 1st child discovered at a certain depth, until a leaf node is reached.

LC (lowest cost): the branch is extended by the node which adds the lowest additional costs, according to a given cost function. The strategy of traversing the search space is therefore defined by the cost function.

Related questions

TSP - Branch and bound

I'm trying to solve the TSP with Branch and bound algorithm. I must build a matrix with costs but I have this problem: I have city with coordinates x and y. The cost of traveling is ceil(ceil(sqrt((x1…

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More