We’ll try to understand one of the heuristic search techniques in this article. The heuristic technique is a criterion for determining which among several alternatives will be the most effective in achieving a particular goal. Branch and bound search is also known as Uniform Cost Search.
What is the branch and bound search algorithm?
Branch and bound is a search algorithm used for combinatory, discrete, and general mathematical optimization problems. It is comparable to backtracking in that it similarly implements a state-space stream to represent the solution to the problem.
However, it is probably more suited to trying to address optimization problems and only minimization problems, not maximization problems. Statistically speaking, a branch and the bound algorithm find the best solution from the entire search space of possibilities for an NP-Hard problem.
How does the branch and bound search work?
In the branch and bound search strategy, a cost function (denoted by g(X)) is generated that, by using a sequence of operators, assigns a cumulative cost to the path from the start node to the current node X. A cheapest price path already discovered is extended at every step of the search space generation process until we reach the goal state.
Branch and bound search is also referred to as a uniform cost search since it expands the least-cost partial path. The actual distance traveled from the beginning to the current node X, for instance, may be represented as g(X) in the traveling salesman problem.
Steps for the algorithm
Input: START and GOAL states
Local Variable: OPEN, CLOSED, NODE, SUCCs, FOUND
Output: Yes or No
Method:
Initialise FOUND = false
while(OPEN is not NULL and FOUND = false) do
{
remove the top element from OPEN list and call it NODE
if NODE is the goal node then FOUND = true
else
{
put NODE in CLOSED list:
find SUCCs of NODE. if any,and compute thier 'g' values and store them in OPEN list:
sort all the nodes in the OPEN list based on their cost - function values.
}
}end while loop
if FOUND = true then return Yes otherwise return No.
If g(X) = 1 for all operators, the branch and bound methodology degenerates into a straightforward breadth-first search. Artificial intelligence considers it to be just as detrimental as depth-first and breadth-first. If we add dynamic programming to it, we can make this better by eliminating redundant paths.
We note that the method typically necessitates creating a solution and evaluating its efficacy. Any technique can be used to develop the answer, and heuristics may be used in testing. The following is the basic structure of an algorithm for developing and testing strategies.
start
Generate possible solutions
Test if it is a goal
If not go to start else quit
end
Brand and bound search algorithm in action
To understand the concept more clearly, let’s try to implement the 8 puzzle problem using the branch and bound algorithm. The problem description is given below.
A 3 x 3 board with 8 tiles (each tile has a number ranging from 1 to 8) and a single empty space is provided. The goal is to use the vacant space to arrange the numbers on the tiles so that they match the final arrangement. Four neighboring (left, right, above, and below) tiles can be slid into the available area.
For Example
To avoid searching in sub-trees that do not include an answer node, the search for an answer node can frequently be sped up using an approximation of the cost function. However, instead of using the backtracking method, it does a BFS-style search.
Basically, Branch and Bound involve three different kinds of nodes.
- A live node is a generated node whose children have not yet been produced.
- The children of the E-node, a live node, are now being examined. Or to put it another way, an E-node is a node that is currently expanding.
- A created node that is not to be developed or examined further is referred to as a dead node. A dead node has already extended all of its children.
Cost function: In the search tree, each node X has a corresponding cost. The next E-node can be found using the cost function. The E-node with the lowest cost is the next one. The definition of the cost function is
C(X) = g(X) + h(X) where C(X) is also refered as 'f 'sometimes. g(X) = cost of reaching the current node from the root h(X) = cost of reaching an answer node from X.
Implementing the Branch and Bound Search algorithm in Python
import copy
from heapq import heappush, heappop
# we have defined 3 x 3 board therefore n = 3..
n = 3
# bottom, left, top, right
row = [ 1, 0, -1, 0 ]
col = [ 0, -1, 0, 1 ]
class priorityQueue:
def __init__(self):
self.heap = []
# Inserts a new key 'k'
def push(self, k):
heappush(self.heap, k)
# remove minimum element
def pop(self):
return heappop(self.heap)
# Check if queue is empty
def empty(self):
if not self.heap:
return True
else:
return False
class node:
def __init__(self, parent, mat, empty_tile_pos,
cost, level):
# parent node of current node
self.parent = parent
# matrix
self.mat = mat
# position of empty tile
self.empty_tile_pos = empty_tile_pos
# Total Misplaced tiles
self.cost = cost
# Number of moves so far
self.level = level
def __lt__(self, nxt):
return self.cost < nxt.cost
# Calculate number of non-blank tiles not in their goal position
def calculateCost(mat, final) -> int:
count = 0
for i in range(n):
for j in range(n):
if ((mat[i][j]) and
(mat[i][j] != final[i][j])):
count += 1
return count
def newNode(mat, empty_tile_pos, new_empty_tile_pos,
level, parent, final) -> node:
new_mat = copy.deepcopy(mat)
x1 = empty_tile_pos[0]
y1 = empty_tile_pos[1]
x2 = new_empty_tile_pos[0]
y2 = new_empty_tile_pos[1]
new_mat[x1][y1], new_mat[x2][y2] = new_mat[x2][y2], new_mat[x1][y1]
# Set number of misplaced tiles
cost = calculateCost(new_mat, final)
new_node = node(parent, new_mat, new_empty_tile_pos,
cost, level)
return new_node
#print the N x N matrix
def printMatrix(mat):
for i in range(n):
for j in range(n):
print("%d " % (mat[i][j]), end = " ")
print()
def isSafe(x, y):
return x >= 0 and x < n and y >= 0 and y < n
def printPath(root):
if root == None:
return
printPath(root.parent)
printMatrix(root.mat)
print()
def solve(initial, empty_tile_pos, final):
pq = priorityQueue()
# Create the root node
cost = calculateCost(initial, final)
root = node(None, initial,
empty_tile_pos, cost, 0)
pq.push(root)
while not pq.empty():
minimum = pq.pop()
# If minimum is the answer node
if minimum.cost == 0:
# Print the path from root to destination;
printPath(minimum)
return
# Produce all possible children
for i in range(4):
new_tile_pos = [
minimum.empty_tile_pos[0] + row[i],
minimum.empty_tile_pos[1] + col[i], ]
if isSafe(new_tile_pos[0], new_tile_pos[1]):
# Create a child node
child = newNode(minimum.mat,
minimum.empty_tile_pos,
new_tile_pos,
minimum.level + 1,
minimum, final,)
# Add child to list of live nodes
pq.push(child)
# Driver Code
# 0 represents the blank space
# Initial state
initial = [ [ 2, 8, 3 ],
[ 1, 6, 4 ],
[ 7, 0, 5 ] ]
# Final State
final = [ [ 1, 2, 3 ],
[ 8, 0, 4 ],
[ 7, 6, 5 ] ]
# Blank tile position during start state
empty_tile_pos = [ 2, 1 ]
# Function call
solve(initial, empty_tile_pos, final)
Output
Summary
In this article, we have learned one of the most effective algorithms knowns as a branch and bound search. This search algorithm helps to solve many common problems like the N-Queen problem, 0-1 Knapsack Problem, Traveling salesman problem, etc. The algorithm is bit modified in each case according to the conditions provided in the problem but the basic idea of the searching method remains the same as explained earlier.