Graphical tour with uniform cost search in Java
I'm new to this site so hopefully you guys don't mind helping the nose.
Anyway, I was asked to write a code to find the shortest cost of a graphics tour on a specific timeline, whose data is read from a file. The graph is shown below:
http://img339.imageshack.us/img339/8907/graphr.jpg
This is for an AI class, so I have to use a decent enough search method (brute force allowed, but not for full labels).
I've read and I think what I'm looking for is an A * search with constant heuristic value, which I believe is a single cost search. I am having trouble 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 this point, I am struggling to figure out how to apply a uniform concept of value to my desired goal path. Basically I have to start at a specific node, visit all other nodes, and end up at the same node, with the lowest cost.
As I understand it, I could use a PriorityQueue to store all my traversed paths, but I can't wrap my head around the way I show the state of the target as a start node with all other visited nodes.
Here's what I have so far, which is pretty far from the sign:
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 a starting node and then recursively visits the first node in the PriorityQueue (the path with the next low cost).
My problem is basically how can I stop my program after traversing the path specified in the queue if that path is in target state? The queue currently stores Vertex objects, but in my opinion this will not work as I cannot save if other vertices have been visited inside the Vertex object.
Help is greatly appreciated! Josh
EDIT: I should mention that the paths taken earlier can be visited again. In case I indicated that this is not beneficial, but there might be a case where visiting a node previously visited to go to another node will result in a shorter path (I think). So I can't just do it based on the nodes already visited (that was my first thought too)
a source to share
Two comments:
1) When you set costToThis from a vertex, you are overriding the existing value and this affects all paths in the queue, since the vertex is shared by many paths. I will not store the cost of this with the Vertex. Instead, I would define a Path class that contains the total cost of the path and the list of nodes that make up it.
2) I'm not sure if I understood your target state problem correctly. However, the way to add partial paths to the queue is as follows: if the path is & lt; N-1, going back to any node visited is illegal. When length = N-1, the only option goes back to the start node. You can add visitSet to your Path class (like HashSet) so that you can efficiently check if a given node has been visited or not.
Hope this helps ...
a source to share