Brute force algorithm for traveling salesman problem in Java

Question

I am working on a project for a math class at school, and I decided to tackle my problems at Traveling Salesman, which I always wanted to explore more. However, I have problems with my brute force algorithm.

* Go to the update below to view the latest version of the code

---

---

SKIP THIS PARAGRAPH IF YOU KNOW THAT THE PROBLEM OF TRAVELING: Summing up as much as possible, TSP looks like this: you are a seller who wants to visit every city in the region (the city is essentially a point on the map). In a limited area of ​​x and y there are "n" cities, and each city is connected to each city (on a straight road). You need to find the shortest route among the cities, which allows you to visit each city. One of the algorithms that I want to use (and I will need to test other algorithms) is Brute Force, which checks all possible routes and returns the shortest route. The reason this is not always used is because it requires a check (n-1)! possible routes, and this number becomes huge as the "n" increases - in fact, only 50 cities, it will be 608281864034267560872252163321295376887552831379210240000000000 routes to check.

TAKE FOR ALL EXAMPLES TALKED IN THIS MAIL THAT WE ARE USING THE ARBITRATION REGION WITH 4 CITIES (although the algorithm can process the cities, but we do not care about the distance - we want to hit every possible route in brute force).

Here is a simple picture demonstrating what I'm talking about (4 cities is where I start to check if the process works correctly)

map image with cities

Here is the Brute Force algorithm (suppose all other called methods work correctly because they do it):

(see below for more details)

[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 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: the city object has the boolean variable "flag" called "visited").

(if all routes are not marked, and if the route does not contain every possible city)

• start with a route with 1 unflagged city.
• check the "last unpolluted" city (this city is a "hinge")
• Find each city that is not in ROUTE R and add it to the new route.
• call the BruteForce method recursively on each of these routes.

(if all routes are not marked, but the route contains each city)

• flag of the last city

(otherwise ... this means that the route has every city flag and contains every possible city)

• see if this is the shortest route - if there is one, save it in a global variable

This image will help me explain the problem ... Thus, the program runs correctly on the left side. However, after it reaches the bottom, it can be expected that the recursion will return to step 4, and this will happen. However, instead of R having a city A and flag B, and then recursively calling itself a “new route” containing Aflag and B, R now has all 4 cities, and all 4 are marked with an icon. It fails because it again adds city D to "newRoute", recursively calls itself again, and in another method we get an error outside the borders because there are no 5 cities in my region, but 5 cities located on route r (A, B, C, D, D).

Useful picture of a recursive tree structure

The problem is with the recursion call in the loop or the "r" route referenced by the recursive call.

If you have an idea of ​​what I need to do, I seriously appreciate some help.

Thanks to everyone who will help me. I will send the whole project to everyone who wants to help too.

---

UPDATE

Ok, so I tried 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 when we exit the recursion and the loop does not continue. Ideas?

Answer 1

You must remove the cities from the route after returning the recursive call. You do it:

  Route newRoute = r; newRoute.addToRoute(citiesNotInRoute.get(i)); BruteForceFindBestRoute(newRoute); 

but never newRoute.removeFromRoute or similar.

Note that you write Java, and in Java, the assignment of an object is done by reference. This means that r and newRoute are the same object. newRoute not an independent copy of r , as you might expect. Therefore, any modification of newRoute will also change r . You might want to explicitly copy the route there. Java term for this clone . Make sure your clone is deep enough, i.e. You clone all the relevant data structures instead of sharing them between the original and its clone.

Note. There are many places where you can make your code more efficient, but since brute force is far from effective in any case, and you are talking only about a few cities, you might care. However, if you want to explore alternatives, consider keeping a single, linked list of all undisclosed cities. Each call will iterate over this list, delete the item, return and return the item. No need to create this list from scratch in every call. The idea of dance links could be neatly applied to this task as an alternative to the loyal implementations of linked lists.

EDIT:

The following version 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); } }