Hi guys,
Long story short, 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 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 THAT WE ARE GOING TO BE USING AN ARBITRARY REGION WITH 4 CITIES (we don't care about distances- we want to hit every possible route).
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)
MEGA EDIT*
I cleaned up the post and simplified the code. The new code still doesn't work, but for a different reason.
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? I'm getting desperate...
Edited by om3n - 7/28/12 at 4:49pm
Long story short, 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 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 THAT WE ARE GOING TO BE USING AN ARBITRARY REGION WITH 4 CITIES (we don't care about distances- we want to hit every possible route).
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)
MEGA EDIT*
Code:
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;
}
}
I cleaned up the post and simplified the code. The new code still doesn't work, but for a different reason.
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? I'm getting desperate...
Edited by om3n - 7/28/12 at 4:49pm
om3n rev. 2.8
(14 items) |
|
om3n rev. 2.8
(14 items) |
