Extending to Traveling Salesman Problem

My next step in my A.I. investigation was to extend the route-finding problem to do a touring problem. This is basically a simplified traveling salesman problem where you pick a starting node and have to visit each node one time.

This turned out to be pretty easy with the code I already had. I first created a new interface called Goal with just one method:

public interface GoalInterface {
  public boolean goalMet(State currentState);
}

For the existing route finding problem, I moved the goalTest method to an implementation of this interface:

@Override
public boolean goalMet(State currentState) {
  return currentState.getCurrentNode().getNodeName()
          .equalsIgnoreCase(goalNode.getNodeName());
}

Note that the constructor for this goal takes in the goalNode

Then I just updated the RouteFindingProblem to take a Goal (described below) instead of an goalNode.

The new signature for solve:

public Path solve(final Node initialNode, final GoalInterface goal) { }

And instead of calling the goalTest method, I just call goal.goalMet(). At this point the initial route-finiding problem produces the same results and all the tests still pass.

For the touring problem, I just had to create a new goal. The goalMet() method just checks if every node has been visited by calling this method:

private boolean isEveryNodeVisited(final State currentState) {
  boolean tourComplete = true;
  final List<Action> currentPathActions = currentState.getCurrentPath()
          .getActions();
  final Set<Node> currentlyVisitedNodes = new HashSet<Node>();
  for (Action nextPathAction : currentPathActions) {
      currentlyVisitedNodes.add(nextPathAction.resultOfAction(allNodes));
  }

  // make sure all nodes were visited
  for (Node nextNode : allNodes) {
      if (!currentlyVisitedNodes.contains(nextNode)
              && !nextNode.getNodeName().equalsIgnoreCase(
                      initialNode.getNodeName())) {
          tourComplete = false;
          break;
      }
  }
  return tourComplete;
}

A couple things about this. First, it is not very efficient, but for my testing that is not a big deal. Next, I had to add an extra check for the initialNode since the path that is stored in currentState has a list of actions after the initialNode, but does not include the initialNode.

The last thing I had to do was simplify the map. Since my map of Romania had a few branches that had only one route, there was no way to visit each city only one time. I just "trimmed" the branches and ended up with these segments:

segments = [
      new Segment(start:"Arad", end:"Zerind", cost:75),
      new Segment(start:"Arad", end:"Sibiu", cost:140),
      new Segment(start:"Arad", end:"Timisoara", cost:118),
      new Segment(start:"Bucharest", end:"Fagaras", cost:211),
      new Segment(start:"Bucharest", end:"Pitesti", cost:101),
      new Segment(start:"Craiova", end:"Drobeta", cost:120),
      new Segment(start:"Craiova", end:"Pitesti", cost:138),
      new Segment(start:"Craiova", end:"Rimnieu Vilcea", cost:146),
      new Segment(start:"Drobeta", end:"Mehadia", cost:75),
      new Segment(start:"Fagaras", end:"Sibiu", cost:99),
      new Segment(start:"Lugoj", end:"Mehadia", cost:70),
      new Segment(start:"Lugoj", end:"Timisoara", cost:111),
      new Segment(start:"Oradea", end:"Sibiu", cost:151),
      new Segment(start:"Oradea", end:"Zerind", cost:71),
      new Segment(start:"Pitesti", end:"Rimnieu Vilcea", cost:97),
      new Segment(start:"Rimnieu Vilcea", end:"Sibiu", cost:80)
  ];

Then I ran these tests in Groovy:

//make sure each node results in a path
nodes.each {assert problem.solve(it, new TouringGoal(it, nodes)) != null}
//check a couple paths
assert 1327 == (problem.solve(findNode(nodes, "Arad"), new TouringGoal(findNode(nodes, "Arad"), nodes))).getPathCost();
assert 1294 == (problem.solve(findNode(nodes, "Sibiu"), new TouringGoal(findNode(nodes, "Sibiu"), nodes))).getPathCost();

And finally I did a test to display the results in Groovy:

Node testNode = findNode(nodes, "Bucharest");
Path resultPath = problem.solve(testNode, new TouringGoal(testNode, nodes));
//display the results
println("Shortest tour from " + testNode.toString());
if(resultPath == null){
  println("No route found");
} else {
  for (Action nextAction : resultPath.getActions()) {
      println(nextAction.toString());
  }
}

With the results:

Shortest tour from In(Bucharest)
Go(Pitesti)(101)
Go(Rimnieu Vilcea)(97)
Go(Craiova)(146)
Go(Drobeta)(120)
Go(Mehadia)(75)
Go(Lugoj)(70)
Go(Timisoara)(111)
Go(Arad)(118)
Go(Zerind)(75)
Go(Oradea)(71)
Go(Sibiu)(151)
Go(Fagaras)(99)

Let me know if you have any questions or suggestions on improvements!

Update 7/27/10: Uploaded the source code.