1    // ============================================================================
2    //   Copyright 2006, 2007, 2008 Daniel W. Dyer
3    //
4    //   Licensed under the Apache License, Version 2.0 (the "License");
5    //   you may not use this file except in compliance with the License.
6    //   You may obtain a copy of the License at
7    //
8    //       http://www.apache.org/licenses/LICENSE-2.0
9    //
10   //   Unless required by applicable law or agreed to in writing, software
11   //   distributed under the License is distributed on an "AS IS" BASIS,
12   //   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   //   See the License for the specific language governing permissions and
14   //   limitations under the License.
15   // ============================================================================
16   package org.uncommons.watchmaker.examples.travellingsalesman;
17   
18   import java.util.ArrayList;
19   import java.util.Collection;
20   import java.util.Iterator;
21   import java.util.List;
22   import org.uncommons.maths.combinatorics.PermutationGenerator;
23   import org.uncommons.watchmaker.framework.FitnessEvaluator;
24   
25   /**
26    * Naive brute-force solution to the travelling salesman problem. It would take about
27    * a day and a half to brute-force the 15-city travelling salesman problem on a home
28    * computer using this implementation.  However, this is a not the best possible
29    * implementation that is guaranteed to find a the shortest route (for example there
30    * is no branch-and-bound optimisation).
31    * @author Daniel Dyer
32    */
33   public class BruteForceTravellingSalesman implements TravellingSalesmanStrategy
34   {
35       private final DistanceLookup distances;
36   
37   
38       /**
39        * @param distances Information about the distances between cities.
40        */
41       public BruteForceTravellingSalesman(DistanceLookup distances)
42       {
43           this.distances = distances;
44       }
45   
46       
47       /**
48        * {@inheritDoc}
49        */
50       public String getDescription()
51       {
52           return "Brute Force";
53       }
54   
55       
56       /**
57        * To reduce the search space we will only consider routes that start
58        * and end at one city (whichever is first in the collection).  All other
59        * possible routes are equivalent to one of these routes since start city
60        * is irrelevant in determining the shortest cycle.
61        * @param cities The list of destinations, each of which must be visited
62        * once.
63        * @param progressListener Call-back for receiving the status of the
64        * algorithm as it progresses.  May be null.
65        * @return The shortest route that visits each of the specified cities once.
66        */
67       public List<String> calculateShortestRoute(Collection<String> cities,
68                                                  ProgressListener progressListener)
69       {
70           Iterator<String> iterator = cities.iterator();
71           String startCity = iterator.next();
72           Collection<String> destinations = new ArrayList<String>(cities.size() - 1);
73           while (iterator.hasNext())
74           {
75               destinations.add(iterator.next());
76           }
77   
78           FitnessEvaluator<List<String>> evaluator = new RouteEvaluator(distances);
79           PermutationGenerator<String> generator = new PermutationGenerator<String>(destinations);
80           long totalPermutations = generator.getTotalPermutations();
81           long count = 0;
82           List<String> shortestRoute = null;
83           double shortestDistance = Double.POSITIVE_INFINITY;
84           List<String> currentRoute = new ArrayList<String>(cities.size());
85           while (generator.hasMore())
86           {
87               List<String> route = generator.nextPermutationAsList(currentRoute);
88               route.add(0, startCity);
89               double distance = evaluator.getFitness(route, null);
90               if (distance < shortestDistance)
91               {
92                   shortestDistance = distance;
93                   shortestRoute = new ArrayList<String>(route);
94               }
95               ++count;
96               if (count % 1000 == 0 && progressListener != null)
97               {
98                   progressListener.updateProgress(((double) count) / totalPermutations * 100);
99               }
100          }
101          if (progressListener != null)
102          {
103              progressListener.updateProgress(100); // Finished.
104          }
105          return shortestRoute;
106      }
107  }
108