1

i'm trying to solve travelling salesman. for the example below, i have a Tour t that is an ArrayList of cities, a city being defined as a class with an x and y coordinate. i use Collections.shuffle to randomize the order of cities in Tour t, then i want to see if the new shuffled tour has a totalDistance < the current saved value of finalTour. if has a lower totaldistance, then i want to save that as the final tour. i am only looping 1o times right now in order to troubleshoot my code. in the below example, however, finalTour always gets updated to be Tour t, even if the distance is already lower than Tour t totalDistance. not sure what i am doing wrong. seems to be a problem with Tour t being "remembered" from previous iteration and not being a new copy ?

 Tour finalTour = new Tour();

    for (int x = 0; x < 10; x++) {

        Tour t = new Tour(cityArray);

        t.shuffle();

        if (finalTour.getTourDistance() == 0.0 || (t.getTourDistance() < finalTour.getTourDistance())) {

            finalTour = t;

        }

        System.out.print("T" + x + ": " + t.getTourDistance());
        System.out.println(" finalTour: " + finalTour.getTourDistance());
    }

here is sample output:

T0: 5.23606797749979 finalTour: 5.23606797749979
T1: 4.0 finalTour: 4.0
T2: 5.446461113496085 finalTour: 5.446461113496085
T3: 6.06449510224598 finalTour: 6.06449510224598
T4: 4.0 finalTour: 4.0
T5: 4.0 finalTour: 4.0
T6: 4.618033988749895 finalTour: 4.618033988749895
T7: 4.82842712474619 finalTour: 4.82842712474619
T8: 4.618033988749895 finalTour: 4.618033988749895
T9: 5.03224755112299 finalTour: 5.03224755112299

my getTourDistance method returns Euclidean distance summed for the total array of cities. note, i have no static classes or methods....

 public double getTourDistance() {

    double totalDistance = 0.0;

    if (this.tour.size() > 0) {

        for (int x = 0; x < this.tour.size() - 1; x++) {

            totalDistance += Math.sqrt(Math.pow((this.tour.get(x + 1).getY() - this.tour.get(x).getY()), 2) + Math.pow((this.tour.get(x + 1).getX() - this.tour.get(x).getX()),2));

        }

        totalDistance += Math.sqrt(Math.pow((this.tour.get(0).getY() - this.tour.get(this.tour.size() - 1).getY()), 2) + Math.pow((this.tour.get(0).getX() - this.tour.get(this.tour.size() - 1).getX()),2));
    }

    return totalDistance;

}
Andrew Tobilko
  • 48,120
  • 14
  • 91
  • 142
Niko
  • 67
  • 1
  • 4
  • Assuming `t.shuffle()` shuffles the `cityArray` given tho the constructor, and that the constructor does copy the array, then there is only one array, and shuffling it will update all `Tour` object using that array, which is why shuffling updates both `Tn` and `finalTour` in your output. Closing as duplicate of slightly related question that has same cause. – Andreas Aug 15 '17 at 22:04
  • can you show me how to fix it or point me to the answer in the original post ? i'm not quite sure what to do...i don't have static defined variables. – Niko Aug 15 '17 at 22:07
  • @Niko You're probably using `Arrays.asList()` - see the problems here https://stackoverflow.com/q/16748030/330057 - Also I put together a working example that properly keeps your fastest tour (I use some slightly different wordage but you'll figure it out I'm sure) check it out http://ideone.com/XIAd9C – corsiKa Aug 15 '17 at 23:17

0 Answers0