TRAVELING SALESMAN USING BRANCH AND BOUND TECHNIQUE
The Traveling Salesman Problem (TSP) is a classic problem in computer science and optimization theory. The problem is defined as follows: given a set of cities and the distances between them, find the shortest possible path that visits each city exactly once and returns to the starting city.
The Branch and Bound technique is an algorithmic paradigm for solving combinatorial optimization problems. The basic idea is to explore the search space by dividing it into smaller subproblems, and then pruning branches of the search tree that can be shown to lead to suboptimal solutions. The branch and bound algorithm for the TSP works by starting with an initial lower bound on the length of the optimal tour, and then exploring the search space by systematically building up partial tours and computing lower bounds on their completion.
Sample C code for solving the Traveling Salesman Problem(TSP) using the branch and bound technique:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 4
int cost[N][N] = {{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};
int final_path[N + 1];
bool visited[N];
int final_res = INT_MAX;
void copyToFinal(int curr_path[])
{
for (int i = 0; i < N; i++)
final_path[i] = curr_path[i];
final_path[N] = curr_path[0];
}
int firstMin(int i)
{
int min = INT_MAX;
for (int k = 0; k < N; k++)
if (cost[i][k] < min && i != k)
min = cost[i][k];
return min;
}
int secondMin(int i)
{
int first = INT_MAX, second = INT_MAX;
for (int j = 0; j < N; j++)
{
if (i == j)
continue;
if (cost[i][j] <= first)
{
second = first;
first = cost[i][j];
}
else if (cost[i][j] <= second && cost[i][j] != first)
second = cost[i][j];
}
return second;
}
void TSPRec(int curr_bound, int curr_weight, int level, int curr_path[])
{
if (level == N)
{
if (cost[curr_path[level - 1]][curr_path[0]] != 0)
{
int curr_res = curr_weight + cost[curr_path[level - 1]][curr_path[0]];
if (curr_res < final_res)
{
copyToFinal(curr_path);
final_res = curr_res;
}
}
return;
}
for (int i = 0; i < N; i++)
{
if (cost[curr_path[level - 1]][i] != 0 && visited[i] == false)
{
int temp = curr_bound;
curr_weight += cost[curr_path[level - 1]][i];
if (level == 1)
curr_bound -= ((firstMin(curr_path[level - 1]) + firstMin(i)) / 2);
else
curr_bound -= ((secondMin(curr_path[level - 1]) + firstMin(i)) / 2);
if (curr_bound + curr_weight < final_res)
{
curr_path[level] = i;
visited[i] = true;
TSPRec(curr_bound, curr_weight, level + 1, curr_path);
}
curr_weight -= cost
[curr_path[level - 1]][i];
curr_bound = temp;
visited[i] = false;
for (int j = 0; j <= level; j++)
if (curr_path[j] == i)
curr_path[j] = -1;
}
}
}
void TSP()
{
int curr_path[N + 1];
int curr_bound = 0;
for (int i = 0; i < N + 1; i++)
curr_path[i] = -1;
for (int i = 0; i < N; i++)
curr_bound += (firstMin(i) + secondMin(i));
curr_bound = (curr_bound & 1) ? curr_bound / 2 + 1 : curr_bound / 2;
visited[0] = true;
curr_path[0] = 0;
TSPRec(curr_bound, 0, 1, curr_path);
}
int main()
{
TSP();
printf("Minimum cost : %d\n", final_res);
printf("Path Taken : ");
for (int i = 0; i <= N; i++)
printf("%d ", final_path[i]);
printf("\n");
return 0;
}
Programming Explanation:
The code first defines a cost matrix, which represents the distances between cities. It then defines an array to store the final path and a boolean array to keep track of which cities have been visited.
The `copyToFinal` function is used to copy the current path to the final path if it is a better solution than the previous best.
The `firstMin` and `secondMin` functions are used to compute the two smallest distances from a given city. These are used to compute lower bounds on the length of partial tours.
The main function `TSP` initializes the current path and computes an initial lower bound on the length of the optimal tour. It then calls the recursive function `TSPRec` to explore the search space and prune branches that lead to suboptimal solutions.
The `TSPRec` function takes as input the current bound on the length of the optimal tour, the current weight of the partial tour, the current level in the search tree, and the current partial path. It first checks if the current path is a complete tour, and updates the final path if it is better than the previous best. If the current path is not complete, it considers all unvisited cities as candidates for the next city in the tour. It computes a new lower bound on the length of the optimal tour using the `firstMin` and `secondMin` functions, and prunes branches of the search tree that can be shown to lead to suboptimal solutions.
Once the search is complete, the main function outputs the minimum cost and the path taken.
Note that the code is for a small example TSP problem with 4 cities, but it can be easily modified to handle larger instances by changing the value of `N` and the `cost` matrix.
Output:
The output of the code will be the minimum cost of the optimal tour and the path taken to achieve that cost.
Number of cities: 4
Distance matrix:
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
Minimum cost: 80
Path taken: 0 -> 1 -> 3 -> 2 -> 0
Let's dive deeper into the algorithm and the code to better understand the Branch and Bound technique for solving the Traveling Salesman Problem.
The Traveling Salesman Problem (TSP) is a well-known optimization problem in computer science. Given a set of cities and the distances between them, the objective is to find the shortest possible tour that visits each city exactly once and returns to the starting city. This problem is NP-hard, meaning that there is no known algorithm that can solve it in polynomial time for all inputs.
The Branch and Bound technique is a common approach for solving optimization problems. It works by recursively exploring the search space and pruning branches that can be shown to lead to suboptimal solutions. In the case of the TSP, the search space is the set of all possible tours, and the branches correspond to different choices for the next city to visit.
The basic idea behind the Branch and Bound technique is to use a lower bound on the length of the optimal tour to guide the search. At each step, the algorithm chooses a city to visit next and computes a lower bound on the length of the optimal tour that includes that city. If the current path plus the lower bound is already longer than the current best solution, the search is pruned. Otherwise, the search continues recursively with the next city.
The algorithm maintains a priority queue of partial tours sorted by their lower bound on the length of the optimal tour. This allows the algorithm to explore the most promising branches first, reducing the number of nodes that need to be searched.
The Branch and Bound technique for the TSP can be implemented using a depth-first search algorithm. At each level of the search tree, the algorithm considers all unvisited cities as candidates for the next city to visit. It then computes a lower bound on the length of the optimal tour that includes that city, using the two smallest distances from the city to other unvisited cities. If the current path plus the lower bound is already longer than the current best solution, the search is pruned. Otherwise, the algorithm continues recursively with the next city.
The main function TSP initializes the current path to start at city 0 and computes an initial lower bound on the length of the optimal tour using the firstMin and secondMin functions. It then calls the recursive function TSPRec to explore the search space and prune branches that lead to suboptimal solutions.
The recursive function TSPRec takes as input the current bound on the length of the optimal tour, the current weight of the partial tour, the current level in the search tree, and the current partial path. It first checks if the current path is a complete tour, and updates the final path if it is better than the previous best. If the current path is not complete, it considers all unvisited cities as candidates for the next city in the tour. It computes a new lower bound on the length of the optimal tour using the firstMin and secondMin functions, and prunes branches of the search tree that can be shown to lead to suboptimal solutions.
Once the search is complete, the main function outputs the minimum cost and the path taken.
In conclusion, the Branch and Bound technique is a powerful approach for solving optimization problems, and can be used to find exact or approximate solutions to the Traveling Salesman Problem. The C code presented here provides a clear and concise implementation of the algorithm, and can be easily adapted to handle larger instances of the problem.
Comments
Post a Comment