Traveling_Salesman_Problem - Brute force algorithm - 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.




**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)


[picture of map with cities][1]



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 region r (A,B,C,D,D). 

[Helpful picture of recursive tree structure][2]

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. 


  [1]: http://www.emeraldinsight.com/content_images/fig/0050300707002.png
  [2]: http://i264.photobucket.com/albums/ii191/om3n07/46049b90.jpg