FIFO Branch and Bound solution 

FIFO Branch and Bound solution is one of the methods of branch and bound. 

Branch and Bound is the state space search method where all the children E-node that is generated before the live node, becomes an E- node. 

FIFO branch and bound search is the one that follows the BFS like method. It does so as the list follows first in and first out. 

Some key terms to keep in mind while proceeding further:

What is a live node?

A live node is the one that has been generated but its children are not yet generated. 

What is an E node?

An E node is the one that is being explored at the moment. 

What is a dead node?

A dead node is one that is not being generated or explored any further. The children of the dead node have already been expanded to their full capacity. 

Branch and Bound solution have three types of strategies:

1. FIFO branch and bound.
2. LIFO branch and bound. 
3. Least Cost branch and bound. 

In this article, we have briefly discussed the FIFO branch and bound. 

To proceed further with the FIFO branch and bound we use a queue. 

To begin with, we keep the queue empty. Then we assume a node 1. 

In FIFO search the E node is assumed as node 1. After that, we need to generate children of Node 1. The children are the live nodes, and we place them in the queue accordingly. Then we delete node 2 from the queue and generate children of node 2. 

Next, we delete another element from the queue and assume that as the E node. We then generate all its children. 

In the same process, we delete the next element and generate their children. We keep repeating the process till the queue is covered and we find a node that satisfies the conditions of the problem. When we have found the answer node, the process terminates. 

Let us understand it through an example:

We start by taking an empty queue:

In the given diagram we have assumed that node 12 is the answer node. 

As mentioned we start by assuming node 1 as the E node and generate all its children. 

Then we delete node 1 from the queue, take node 2 as the E node, and generate all its children:

We delete the next element and generate children for the next node, assuming it to be the E node.

We repeat the same process. The generated children of 4, that is node 9 are killed by the boundary function.

Similarly, we proceed further, but the children of nodes 5, meaning the nodes 10, and 11 are also generated and killed by boundary function. The last standing node in the queue is 6, the children of node 6 are 12, and it satisfies all the conditions for the problem, therefore it is the answer node. 

Reference

FIFO Branch and Bound solution