Branch and Bound

Traveling salesman problem

Pinterest LinkedIn Tumblr

Traveling salesman problem helps to find the shortest possible route that visits each city exactly once and returns to the origin city. The traveling salesman problem solves the given set of cities and distance between each pair of cities. Find the shortest route that visit each city exactly once and return to the origin of the city.

Write a program to give all the brute force approach to find the sorted path between the cities?

source Code

package com.dsacode.Algorithm.bruteforce;
 
import java.util.ArrayList;
 
public class TravellingSalesman {
 
     @SuppressWarnings("unused")
    private static ArrayList < Integer > bestRoute;
 
        public static void bruteForceFindBestRoute(ArrayList < Integer > r, ArrayList < Integer > citiesNotInRoute) {
            if(!citiesNotInRoute.isEmpty()) {
                for(int i = 0; i < citiesNotInRoute.size(); i++) {
                    Integer justRemoved =  (Integer) citiesNotInRoute.remove(0);
                     
                    @SuppressWarnings("unchecked")
                    ArrayList < Integer > newRoute = (ArrayList < Integer >) r.clone();
                    newRoute.add(justRemoved);
 
                    bruteForceFindBestRoute(newRoute, citiesNotInRoute);
                    citiesNotInRoute.add(justRemoved);
                }
            }else{
                if(isBestRoute(r))
                    bestRoute = r;
            }
 
        }
 
        private static boolean isBestRoute(ArrayList < Integer > r) {
            System.out.println(r.toString());
            return false;
        }
 
        public static void main(String[] args) {
            ArrayList < Integer > lst = new ArrayList < Integer >();
            for (int i = 0; i < 3; ++i)
                lst.add(i);
            System.out.println("Number of items from the list: " + lst.toString());
            ArrayList < Integer > route = new ArrayList < Integer >();
            System.out.println("All the routes using Branch and bound : ");
            bruteForceFindBestRoute(route, lst);
        }
}

Output

Number of items from the list: [0, 1, 2]
All the routes using Branch and bound :
[0, 1, 2]
[0, 2, 1]
[1, 2, 0]
[1, 0, 2]
[2, 0, 1]
[2, 1, 0]

Algorithm Explanation

Get the number of cities and store in the list.
Call recursively and print all the possible options from the pair of cities.
Return and print the values

Reference

  1. http://mathworld.wolfram.com/TravelingSalesmanProblem.html
  2. https://en.wikipedia.org/wiki/Travelling_salesman_problem
  3. http://www.csd.uoc.gr/~hy583/papers/ch11.pdf
  4. http://www.math.uwaterloo.ca/tsp/problem/index.html

Write A Comment