aco/strategy/GraphStrategy.java

   1 package aco.strategy;
   2
   3 import aco.mediator.*;
   4
   5 public class GraphStrategy {
   6
   7   protected ACOMediator acom;
   8
   9   public GraphStrategy(ACOMediator acom) {
  10     this.acom = acom;
  11   }
  12
  13   public void computeNearestNeighbourListDepth() {
  14     if (acom.getNearestNeighbourListDepth() == 0) {
  15       if (acom.getNumOfCities() <= 30)
  16         acom.setNearestNeighbourListDepth(acom.getNumOfCities() - 1);
  17       else if (acom.getNumOfCities() > 30 && acom.getNumOfCities() < 80)
  18         acom.setNearestNeighbourListDepth(acom.getNumOfCities()/2);
  19       else
  20         acom.setNearestNeighbourListDepth(40);
  21     } else if (acom.getNearestNeighbourListDepth() > acom.getNumOfCities()) {
  22       acom.setNearestNeighbourListDepth(acom.getNumOfCities());
  23     }
  24   }
  25
  26   public int nearestNeighbourHeuristicRandomStart() {
  27
  28     boolean[] visited = new boolean[acom.getNumOfCities()];
  29
  30     for (int i = 0; i < acom.getNumOfCities(); i++)
  31       visited[i] = false;
  32
  33     return nearestNeighbourHeuristic(
  34         (int)( Math.random() * acom.getNumOfCities() ),
  35         visited,
  36         acom.getNumOfCities());
  37   }
  38
  39   public int nearestNeighbourHeuristic(int city, boolean[] visited, int remaining) {
  40
  41     int nextmin = acom.getInfinity();
  42     int nextcity = 0;
  43
  44     for (int i = 0; i < acom.getNumOfCities(); i++) {
  45       if ( (i != city) &&
  46           (! visited[i]) &&
  47           (acom.getDistance(i, city) < nextmin) ) {
  48         nextmin = acom.getDistance(i, city);
  49         nextcity = i;
  50           }
  51     }
  52
  53     visited[nextcity] = true;
  54
  55     if (remaining == 1)
  56       return nextmin;
  57     else
  58       return nextmin + nearestNeighbourHeuristic(nextcity, visited, remaining - 1);
  59   }
  60
  61 }