Scribd
Upload
22 views2 pages

Simple Branch and Bound Algorithms

The document outlines the Branch and Bound algorithms for solving three classic problems: the 15 Puzzle, the 0/1 Knapsack, and the Travelling Salesman Problem. Each problem is broken down into systematic steps involving the use of priority queues and heuristic estimations to find optimal solutions. The processes include defining goals, creating decision trees, and managing costs to explore potential solutions efficiently.

Uploaded by

naveen261005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views2 pages

Simple Branch and Bound Algorithms

The document outlines the Branch and Bound algorithms for solving three classic problems: the 15 Puzzle, the 0/1 Knapsack, and the Travelling Salesman Problem. Each problem is broken down into systematic steps involving the use of priority queues and heuristic estimations to find optimal solutions. The processes include defining goals, creating decision trees, and managing costs to explore potential solutions efficiently.

Uploaded by

naveen261005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Branch and Bound Algorithms - Simple and Understandable

1. 15 Puzzle Problem (Branch and Bound)


Step 1: Start with the puzzle's current tile positions and identify the empty space.

Step 2: Define the target goal arrangement (usually tiles 1-15 in order, with the blank last).

Step 3: Use a heuristic (e.g., Manhattan distance) to estimate how far each tile is from its goal.

Step 4: Add this initial puzzle to a priority queue based on estimated moves needed (cost).

Step 5: While the queue has puzzles to check:

- Take the puzzle with the lowest estimated cost.

- If it matches the goal, you're done!

- If not, move the blank tile in each valid direction to create new puzzles.

- For each new puzzle, calculate its cost and add it back into the queue.

Step 6: Repeat until the goal puzzle is found.

2. 0/1 Knapsack Problem (Branch and Bound)


Step 1: Sort all items by their value divided by weight (value/weight ratio).

Step 2: Create a decision tree to try all item combinations (take or skip).

Step 3: Use a priority queue to track which combinations might give the best value.

Step 4: Begin with a root node that includes no items and zero weight/value.

Step 5: While the queue is not empty:

- Take the node with the best possible value estimate.

- If it goes over the weight limit, skip it.

- If all items are tried, update the best value if it's better.

- Otherwise, create two new nodes:

- One where the next item is included (if it fits).

- One where it is skipped.

- For each new node, estimate the best value it could reach (using fractional knapsack).

- Add promising nodes to the queue.

Step 6: At the end, return the highest value found.


3. Travelling Salesman Problem (Branch and Bound)
Step 1: Create a matrix showing distances between every pair of cities.

Step 2: Reduce the matrix by subtracting the smallest value in each row and column.

Step 3: Start from the first city and create a node with a reduced matrix and zero path cost.

Step 4: Put this node into a priority queue based on the lowest estimated total cost.

Step 5: While the queue has nodes to process:

- Take out the node with the lowest cost estimate.

- If all cities are visited and returned to start, update the best path.

- If not, create new nodes for each unvisited city:

- Mark the new city as visited.

- Update the path and cost matrix.

- Reduce the new matrix and calculate the total cost.

- Add each new node into the queue.

Step 6: Continue until all paths are considered. Return the shortest one.

You might also like