Graph Tour with Uniform Cost Search in Java

Question

I'm new to this site, so hopefully you guys don't mind helping a nub.

Anyway, I've been asked to write code to find the shortest cost of a graph tour on a particular graph, whose details are read in from file. The graph is shown below:

http://img339.imageshack.us/img339/8907/graphr.jpg

This is for an Artificial Intelligence class, so I'm expected to use a decent enough search method (brute force has been allowed, but not for full marks).

I've been reading, and I think that what I'm looking for is an A* search with constant heuristic value, which I believe is a uniform cost search. I'm having trouble wrapping my head around how to apply this in Java.

Basically, here's what I have:

Vertex class -

ArrayList<Edge> adjacencies;
String name;
int costToThis;

Edge class -

final Vertex target;
public final int weight;

Now at the moment, I'm struggling to work out how to apply the uniform cost notion to my desired goal path. Basically I have to start on a particular node, visit all other nodes, and end on that same node, with the lowest cost.

As I understand it, I could use a PriorityQueue to store all of my travelled paths, but I can't wrap my head around how I show the goal state as the starting node with all other nodes visited.

Here's what I have so far, which is pretty far off the mark:

public static void visitNode(Vertex vertex) {
      ArrayList<Edge> firstEdges = vertex.getAdjacencies();
      for(Edge e : firstEdges) {
         e.target.costToThis = e.weight + vertex.costToThis;
         queue.add(e.target);
      }
      Vertex next = queue.remove();
      visitNode(next);
   }

Initially this takes the starting node, then recursively visits the first node in the PriorityQueue (the path with the next lowest cost).

My problem is basically, how do I stop my program from following a path specified in the queue if that path is at the goal state? The queue currently stores Vertex objects, but in my mind this isn't going to work as I can't store whether other vertices have been visited inside a Vertex object.

Help is much appreciated! Josh

EDIT: I should mention that paths previously visited may be visited again. In the case I provided this isn't beneficial, but there may be a case where visiting a node previously visited to get to another node would lead to a shorter path (I think). So I can't just do it based on nodes already visited (this was my first thought too)

"... I've been asked to write code ..." - by whom? A teacher maybe? If so, please label your question 'homework' ... — miku
Ah, yes, sorry, it is homework. My bad. I hope this is within the rules. I should be clear, I'm not asking for fully written code (I don't want to cheat myself out of an education!), just an explanation (preferably using standard libraries) of how I could perform a search the right way. — joshschreuder
EDIT: I should mention that paths previously visited may be visited again. In the case I provided this isn't beneficial, but there may be a case where visiting a node previously visited to get to another node would lead to a shorter path (I think). So I can't just do it based on nodes already visited (this was my first thought too) — joshschreuder

Eyal Schneider Eyal Schneider · Accepted Answer · 2010-04-24T10:40:37

Two comments:

1) When you set costToThis of a vertex, you override the existing value, and this affects all paths in the queue, since the vertex is shared by many paths. I would not store the costToThis as a part of Vertex. Instead, I would have defined a Path class that contains the total cost of the path plus a list of nodes composing it.

2) I am not sure if I understood correctly your problem with the goal state. However, the way I would add partial paths to the queue is as follows: if the path has a length<N-1, a return to any visited node is illegal. When length=N-1, the only option is returning to the starting node. You can add visitedSet to your Path class (as a HashSet), so that you can check efficiently whether a given node has been visited or not.

I hope this helps...

Graph Tour with Uniform Cost Search in Java

1 Answers