C++ to Java: The Travelling Salesman Problem

When I first started android coding, the language I had been doing the most work in was C++. To regain familiarity with java, I gave myself the task of porting from C++ to Java a recursive breadth-first search solution to The Travelling Salesman Problem. The difference between C++ and Java that these two solutions highlight is that you cannot pass by reference in Java as you can in C++. Java does manipulate objects by reference, but passes by value when objects are inputted to a method. In the java solution, I overcome this by adding in the copyArrayListOverAnother() method. It allows us to do what keeping a reference would do, we do not lose track of the changes we’ve made to the tourSoFar object.

double computeTourCost(Vector& tour) {
  double cost = 0.0;
  for (int i = 0; i < tour.size() - 1; i++) {
    cost += distance(tour[i], tour[i + 1]);
  }
  return cost;
} 

bool isAcceptableTour(Vector& tour, double maxDistance) {
  double reachDistance = 0; 
  for (int i = 0; i < tour.size() - 1; i++) {
    if (tour[i].hasFuel) reachDistance = maxDistance;
    double hopDistance = distance(tour[i], tour[i + 1]);
    if (hopDistance > reachDistance) return false;
    reachDistance -= hopDistance;
  }
  return true;
}

void computeOptimalTour(Vector& tourSoFar, Vector& remaining,
double maxDistance, Vector& optimalTour, double& optimalDistance) {
  if (remaining.isEmpty()) {
    tourSoFar.add(tourSoFar[0]);
    if (isAcceptableTour(tourSoFar, maxDistance)) {
      double totalCost = computeTourCost(tourSoFar);
      if (totalCost < optimalDistance) {
        optimalTour = tourSoFar;
        optimalDistance = totalCost;
      }
    }
    tourSoFar.removeAt(tourSoFar.size() - 1);
    return;
  }
  if (!isAcceptableTour(tourSoFar, maxDistance)) return; // optional
    for (int i = 0; i < remaining.size(); i++) {
    island next = remaining[i];
    remaining.removeAt(i);
    tourSoFar.add(next);
    computeOptimalTour(tourSoFar, remaining, maxDistance, optimalTour, optimalDistance);
    tourSoFar.removeAt(tourSoFar.size() - 1);
    remaining.insertAt(i, next);
  }
}

Vector computeOptimalTour(Vector& islands, double maxDistance) {
  double optimalDistance = DBL_MAX;
  Vector workingTour;
  Vector optimalTour;
  computeOptimalTour(workingTour, islands, maxDistance, optimalTour, optimalDistance);
  return optimalTour;
}

Solving the problem in java:

public class IslandTour extends ConsoleProgram {
	
	private class island {
		private double longitude;
		private double latitude;
		private String name;
		
		public island(String name, int latitude, int longitude) {
			this.latitude = latitude;
			this.longitude = longitude;
			this.name = name;
		}
		
		public double getLatitude() {
			return latitude;
		}
		
		public double getLongitude() {
			return longitude;
		}
		
		public String getName() {
			return name;
		}
		
		public String toString() {
			return name+ "("+latitude+","+longitude+")";
		}
	}
	
	private class OptimalDistance {
		double dist;
	}
	
	/* Uses Pythagorean theorem to find the distance between two sets of coordinates */
	public double distance(island one, island two) {
		double a = Math.abs((two.getLatitude() - one.getLatitude()));
		double b = Math.abs((two.getLongitude() - one.getLongitude()));
		double distance = Math.sqrt((a * a) + (b * b));
		return distance;
	}
	
	/* Calculate the distance of a tour */
	public double computeTourCost(ArrayList tour) {
		double cost = 0.0;
		for(int i=0; i < tour.size() - 1; i++) {
			cost += distance(tour.get(i), tour.get(i+1));
		}
		return cost;
	}
	
	/* Copies one ArrayList over another */
	public void copyArrayListOverAnother(ArrayList overwriteThis, ArrayList copyThis) {
		overwriteThis.clear();
		for(int i=0; i < copyThis.size(); i++) {
			overwriteThis.add(copyThis.get(i));
		}
	}
	
	
	/* Parent method to the recursive computeOptimalTour method */
	ArrayList computeOptimalTour(ArrayList islands, double maxDistance) {
		OptimalDistance optimalDistance = new OptimalDistance();
		optimalDistance.dist = Double.MAX_VALUE;
		int initialSize = islands.size();
		ArrayList workingTour = new ArrayList(initialSize);
		ArrayList optimalTour = new ArrayList(initialSize);
		computeOptimalTour(workingTour, islands, maxDistance, optimalTour, optimalDistance);
		println("optimal distance: "+optimalDistance.dist);
		return optimalTour;
	}
	
	/* Recursive Breadth-First Search Method */
	void computeOptimalTour(ArrayList tourSoFar, ArrayList remaining, double maxDistance, ArrayList optimalTour, OptimalDistance optimalDistance) {
		
		if(remaining.isEmpty()) {
			tourSoFar.add(tourSoFar.get(0));
			double totalCost = computeTourCost(tourSoFar);
			if(totalCost < optimalDistance.dist) {
				copyArrayListOverAnother(optimalTour, tourSoFar);
				optimalDistance.dist = totalCost;
			}
			tourSoFar.remove(tourSoFar.size() - 1);
			return;
		}
		
		for(int i = 0; i < remaining.size(); i++) {
			island next = remaining.get(i);
			remaining.remove(i);
			tourSoFar.add(next);
			computeOptimalTour(tourSoFar, remaining, maxDistance, optimalTour, optimalDistance);
			tourSoFar.remove(tourSoFar.size() - 1);
			remaining.add(i, next);
		}
		
	}
	
	public void run() {
		ArrayList islands = new ArrayList();
		island mark = new island("mark", 0, 0);
		island john = new island("john", 3, 4);
		island thomas = new island("thomas", 3, 5);
		island stephen = new island("stephen", 16, 16);
		islands.add(mark);
		islands.add(stephen);
		islands.add(john);
		islands.add(thomas);
		ArrayList result = computeOptimalTour(islands, 1000.00);
		println(result.toString());
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *