Need implementation for recursiveGenerateTours method in Java for bruteForceTSP
ID: 3698308 • Letter: N
Question
Need implementation for recursiveGenerateTours method in Java for bruteForceTSP
public List<Edge> nearestNeighborTsp() {
LinkedList<Edge> tour = new LinkedList<>();
//creates a source variable that starts at first vertex generated and stored in hashMap
Vertex source= vertexNames.get(0);
//makes the starting position the source
Vertex start = source;
// we don't want to visit the same vertex twice so this keeps track using LinkedList of vertices visited
LinkedList<Vertex> visited = new LinkedList<>();
//adds source to visited list
visited.add(source);
//if visited list does not equal the number of vertices we should keep adding vertices to visited list
while(visited.size() != vertexNames.size()) {
//sorts adjacent edges by distance using compareTo method in edge.java and collections in ascending order and in place
Collections.sort(source.adjacentEdges);
//cycles through all the adjacentEdges for the source given
for(Edge e: source.adjacentEdges){
//moves to new vertices from source
Vertex to = source.equals(e.source) ? e.target : e.source;
//if that vertex we are going to is not in visited set then
if(!visited.contains(to)) {
//adds edge to the path of edges in tour list
tour.add(e);
//updates the source to be the new Vertex visited
source = to;
//add vertex to this list of visited vertices
visited.add(to);
break;
}
}
}
//this for loop completes the cycle btwn the last edge visited and the source to complete cycle
for(Edge e: source.adjacentEdges){
//this would be the last edge that completes cycle back to source
if(e.source.equals(start) || e.target.equals(start))
//add this last edge to list of all the edges visited in path
tour.add(e);
}
return tour;
}
public List<Edge> bruteForceTsp() {
//a list of list of vertices, essentially a list of tours for each vertex in list.
//need to figure out how to generate all the tours recursively to put into list
LinkedList<LinkedList<Vertex>> tours = recursiveGenerateTours();
double minDist = Integer.MAX_VALUE;
LinkedList<Vertex> bestTour = tours.get(0);
//cycle through all the tours for each tour to compare
for (LinkedList<Vertex> tour : tours) {
//initiates length of tour as 0
double length = 0;
for (int i=0; i<tour.size()-1; i++) {
//computes all the lengths btwn sequence of vertices given from start to finish
double dist = computeEuclideanDistance(tour.get(i), tour.get(i+1));
//updates the length of tour here
length += dist;
}
//computes the length btwn the last vertex and the starting vertex to close cycle
length += computeEuclideanDistance(tour.get(tour.size()-1), tour.get(0));
//updates the minDist
if (minDist > length) {
bestTour = tour;
minDist = length;
}
}
LinkedList<Edge> edgeTour = new LinkedList<>();
//cycles through the list of vertices in bestTour to get the list of edges
for(int i = 0; i<bestTour.size()-1; ++i) {
for (Edge e:bestTour.get(i).adjacentEdges) {
if(e.source.equals(bestTour.get(i+1)) || e.target.equals(bestTour.get(i+1))) {
edgeTour.add(e);
break;
}
}
}
//adds the edge btwn the last vertex and the starting vertex to close cycle
for (Edge e:bestTour.get(bestTour.size()-1).adjacentEdges) {
if(e.source.equals(bestTour.get(0)) || e.target.equals(bestTour.get(0))) {
edgeTour.add(e);
break;
}
}
return edgeTour;
}
//this needs to give me all the different permutations of vertices in LinkedList and where I AM STUCK
private LinkedList<LinkedList<Vertex>> recursiveGenerateTours() {
return null;
}
Explanation / Answer
import java.util.*; class S { private static ArrayList bestRoute; public static void bruteForceFindBestRoute (ArrayList r, ArrayList citiesNotInRoute) { if(!citiesNotInRoute.isEmpty()) { for(int i = 0; iRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.