Brute force algorithm for the Traveling Salesman Problem in Java
I'm working on a project for a math class at school, and I chose to do mine on the Traveling Salesman Problem, something I've always wanted to investigate more. However, I'm having problems with my brute force solving algorithm.
*Please go to the update at the bottom to view the most recent version of the code
SKIP THIS PARAGRAPH IF YOU KNOW WHAT THE TRAVELING SALESMAN PROBLEM IS: To summarize as much as possible, the TSP goes like this: You are a salesman who wants to visit each city in a region (a city is essentially a point on a map). There are 'n' cities in the bounded x and y region, and each city is connected to each city (by assume a straight road). You need to find the shortest possible route among the cities that allows you to visit each city.One of the algorithms I want to use (and I will need to test other algorithms) is Brute Force, which checks every possible route and returns the shortest route. The reason this is not always used is because it requires us to check (n-1)! possible routes, and that number gets huge as 'n' increases- in fact, with just 50 cities, that would be 608281864034267560872252163321295376887552831379210240000000000 routes to check.
ASSUME FOR ALL EXAMPLES TALKED ABOUT IN THIS POST THAT WE ARE GOING TO BE USING AN ARBITRARY REGION WITH 4 CITIES (even though the algorithm can handle n cities. also we don't care about distances- we want to hit every possible route in brute force).
Here is a simple picture demoing what I'm talking about (4 cities is what I'm starting with to check if the process is working properly)
Here is the Brute Force algorithm (assume all other called methods work correctly, because they do):
(check below for a bit more explanation)
[code]
public void BruteForceFindBestRoute(Route r) //Must start r having 1 unflagged city to begin with
{
if(!r.allFlagged() && r.route.size() != m.cities.size())
{
/*STEP 1 Begin with last unflagged city*/
City pivot = r.lastCityAdded();
/*STEP 2: Flag city*/
pivot.visited = true;
/*STEP 3: Find cities "NOT IN ROUTE"*/
ArrayList<City> citiesNotInRoute = new ArrayList<City>();
for(int i = 0; i<m.cities.size(); i++)
{
if(!r.isCityInRoute(m.cities.get(i).name))
{
citiesNotInRoute.add(m.cities.get(i));
}
}
/*STEP 4: Recursively call BruteForceFindBestRoute() using these cities added to the end of our original route*/
for(int i = 0; i<citiesNotInRoute.size(); i++)
{
Route newRoute = r;
newRoute.addToRoute(citiesNotInRoute.get(i));
BruteForceFindBestRoute(newRoute);
}
}
/*STEP 5: If the route is full but the last city isn't flagged, then flag it call BruteForceFindBestRoute() again, with the last city flagged*/
else if(!r.allFlagged() && r.route.size() == m.cities.size())
{
if(r.allFlaggedButLast())
{
Route x = r;
x.flagLastCity();
BruteForceFindBestRoute(x);
}
}
/*STEP 6: If all cities are flagged, the route is full. Check to see if it's the best route.*/
else if(r.allFlagged())
{
if(IsBestRoute(r))
bestRoute = r;
}
else
System.err.println("Error: somehow all cities got flagged, but the route isn't full");
}
Here is my logic: (Note: a city object has a "flag" boolean variable called "visited")
(if all routes are not flagged, and if the route doesn't contain each possible city)
- begin with route with 1 unflagged city.
- flag the "last unflagged" city (this city is "pivot")
- Find each city that is "NOT IN ROUTE R", and add it to a new route.
- recursively call the BruteForce method on each of these routes.
(if all routes are not flagged, but the route contains each city)
- flag the last city
(else... this means the route has each city flagged and contains each possible city)
- see if this is the shortest route- if it is, store it in global variable
This image will help me explain the problem... So the program correctly goes down the left side. However, after it gets to the bottom, one would expect the recursion to jump back up to step4, which it does. However, instead of R having city A flagged and city B unflagged and then recursively calling itself on the "new route" containing Aflag and B, R now has all 4 cities included, and all 4 are flagged. It fails because it adds city D again to "newRoute", recursively calls itself again, and in another method we get an array out of bounds error because there aren't 5 cities in my region, but there incorrectly are 5 cities in route r (A,B,C,D,D).
Helpful picture of recursive tree structure
The problem has something to do with calling recursion in the loop, or route 'r' being referenced within a recursive call.
If you have any idea what I need to do, I would SERIOUSLY appreciate some help.
Thanks to anyone who will help me out. I will send the whole project to anyone who is willing to help as well.
UPDATE
Alright, so I have attempted to shorten and simplify my original method, and this is what I have:
public void BruteForceFindBestRoute(Route r, ArrayList<City> citiesNotInRoute)
{
if(!citiesNotInRoute.isEmpty())
{
for(int i = 0; i<citiesNotInRoute.size(); i++)
{
City justRemoved = (City) citiesNotInRoute.remove(0).clone();
Route newRoute = (Route) r.clone();
newRoute.addToRoute(justRemoved);
BruteForceFindBestRoute(newRoute, citiesNotInRoute);
citiesNotInRoute.add(justRemoved);
}
}
else //if(citiesNotInRoute.isEmpty())
{
if(IsBestRoute(r))
bestRoute = r;
}
}
The problem is that the variable i inside the for loop seems to lose it's meaning when we break out of the recursion, and the loop is not continued. Ideas?
Answer
You should remove cities from the route after the recursive call returns. You do this:
Route newRoute = r;
newRoute.addToRoute(citiesNotInRoute.get(i));
BruteForceFindBestRoute(newRoute);
but never a newRoute.removeFromRoute or similar.
Note that you are writing Java, and in Java, an assignment of an object is done by reference. Which means that r and newRoute are the same object. newRoute is not an independent copy of r as you might expect. So any modification to newRoute will change r as well. You might want to explicitely copy your route there. The Java term for this is clone. Make sure your clone is deep enough, i.e. you clone all relevant data structures, instead of sharing them between the original and its clone.
Note: There are many places where you might make your code more efficient, but as brute force is far from efficient in any case, and you're only talking about few cities, perhaps you don't have to care. If you want to investigate alternatives, though, consider maintaining a single linked list of all unvisited cities. Each call would loop over that list, remove an element, recurse and put the element back. No need to build this list from scratch in each invocation. The idea of dancing links could be neatly applied to this task, as an alternative to premade linked list implementations.
EDIT:
The following variation of your code works for me:
import java.util.*;
class SO11703827 {
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);
ArrayList<Integer> newRoute =
(ArrayList<Integer>) r.clone();
newRoute.add(justRemoved);
bruteForceFindBestRoute(newRoute, citiesNotInRoute);
citiesNotInRoute.add(justRemoved);
}
}
else //if(citiesNotInRoute.isEmpty())
{
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 < 6; ++i)
lst.add(i);
ArrayList<Integer> route = new ArrayList<Integer>();
bruteForceFindBestRoute(route, lst);
}
}