Difference Between Backtracking and Branch and Bound

Code Example

• Python

Python

def is_safe(board, row, col):
    for i in range(col):
        if board[row][i] == 1:
            return False
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    return True

def solve_n_queens(board, col):
    if col >= len(board):
        return True
    for i in range(len(board)):
        if is_safe(board, i, col):
            board[i][col] = 1
            if solve_n_queens(board, col + 1):
                return True
            board[i][col] = 0  # backtrack
    return False

def place_queens(n):
    board = [[0]*n for _ in range(n)]
    if not solve_n_queens(board, 0):
        return "No solution"
    return board

# Example usage
n = 4
solution = place_queens(n)
print("Solution for", n, "queens:")
for row in solution:
    print(row)

You can also try this code with Online Python Compiler

Run Code

Output

Solution for 4 queens:
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]

This example illustrates backtracking by trying to place queens on the board & backtracking whenever placing a queen results in a conflict.

Branch and Bound

Branch and bound is a systematic method for solving optimization problems, which are often about finding the best solution among many possible options. Unlike backtracking, which focuses on feasibility (finding any solution that satisfies the problem's constraints), branch and bound aims to find the optimal solution by efficiently exploring the entire solution space.

This technique involves dividing the problem into smaller parts (branching) and then evaluating these parts to decide whether to explore further or discard them (bounding). The "bound" part uses logical tests or bounds to eliminate suboptimal paths in the search process, hence speeding up the solution finding.

For instance, consider the problem of finding the shortest traveling path through several cities. Here, the algorithm would explore routes (branching) and use bounds (like the minimum distance already traveled) to discard longer routes early in the process.

Code Example

• Python

Python

import heapq
def branch_and_bound(items, capacity):
    # Initial best (highest value within weight limit)
    best_value = 0
    # Priority queue for exploring nodes: (negative value, total weight, index, items taken)
    pq = [(-0, 0, 0, [])]  # Max-heap by value

    while pq:
        value, weight, index, taken = heapq.heappop(pq)
        value = -value  # Convert back to positive value

        # Bound: if no items left to consider, update best value
        if index == len(items):
            if value > best_value:
                best_value = value
            continue
        # Check next item inclusion
        item = items[index]
        if weight + item['weight'] <= capacity:
            # Explore path with this item included
            heapq.heappush(pq, (-(value + item['value']), weight + item['weight'], index + 1, taken + [item['name']]))
        # Explore path without this item
        heapq.heappush(pq, (-(value), weight, index + 1, taken))

    return best_value
# Example items and capacity
items = [{'name': 'Laptop', 'weight': 2, 'value': 400}, {'name': 'Headphones', 'weight': 1, 'value': 150}]
capacity = 2
print("Maximum value within capacity:", branch_and_bound(items, capacity))

You can also try this code with Online Python Compiler

Run Code

Output

Maximum value within capacity: 400

This code example implements a simple branch and bound algorithm to solve the knapsack problem, where we try to maximize the value of items carried without exceeding the weight capacity.

Difference Between Backtracking & Branch and Bound on the Basis of Parameters

Frequently Asked Questions

What types of problems are best solved by backtracking?

Backtracking is ideal for solving constraint satisfaction problems like puzzles and combinatorial problems where all potential solutions must be examined.

How does branch and bound reduce computational time?

Branch and bound reduces computational time by eliminating paths that cannot possibly lead to an optimal solution based on predefined bounds, which means fewer paths are explored.

Can backtracking and branch and bound be used together?

Yes, they can be combined. For example, branch and bound can be used to find an optimal solution within a set explored through backtracking, optimizing both the search and the solution quality.

Is backtracking DFS or BFS?

Backtracking is typically implemented using a Depth-First Search (DFS) approach. It involves exploring possible solutions by diving deep into each branch of the solution space and backtracking when a solution path is not feasible. This is in contrast to Breadth-First Search (BFS), which explores all possible solutions at the present depth level before moving on to deeper levels.

Conclusion

In this article, we have learned about backtracking and branch and bound, two fundamental techniques for solving problems in computer science. We discussed their purposes, approaches, and the types of problems they are best suited for. Backtracking is excellent for finding any or all solutions that meet specific constraints, while branch and bound is used to find the optimal solution in optimization scenarios. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.