Databases
StackOverflow2013
Postsdbo
POGraph Tour with Uniform Cost Search in Java
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGraph Tour with Uniform Cost Search in Java
    primarykey
    data
    text
    <p>I'm new to this site, so hopefully you guys don't mind helping a nub.</p> <p>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:</p> <p><a href="http://img339.imageshack.us/img339/8907/graphr.jpg" rel="nofollow noreferrer">http://img339.imageshack.us/img339/8907/graphr.jpg</a></p> <p>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).</p> <p>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.</p> <p>Basically, here's what I have:</p> <p>Vertex class -</p> <pre><code>ArrayList&lt;Edge&gt; adjacencies; String name; int costToThis; </code></pre> <p>Edge class -</p> <pre><code>final Vertex target; public final int weight; </code></pre> <p>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.</p> <p>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.</p> <p>Here's what I have so far, which is pretty far off the mark:</p> <pre><code>public static void visitNode(Vertex vertex) { ArrayList&lt;Edge&gt; firstEdges = vertex.getAdjacencies(); for(Edge e : firstEdges) { e.target.costToThis = e.weight + vertex.costToThis; queue.add(e.target); } Vertex next = queue.remove(); visitNode(next); } </code></pre> <p>Initially this takes the starting node, then recursively visits the first node in the PriorityQueue (the path with the next lowest cost).</p> <p>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.</p> <p>Help is much appreciated! Josh</p> <p><strong>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)</strong></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USjoshschreuder
    1. USjoshschreuder
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POGraph Tour with Uniform Cost Search in Java
      1. USNescio
      1. VTFavorite
    2. VO
      singulars
      1. POGraph Tour with Uniform Cost Search in Java
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POGraph Tour with Uniform Cost Search in Java
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO"... I've been asked to write code ..." - by whom? A teacher maybe? If so, please label your question 'homework' ...
      singulars
      1. POGraph Tour with Uniform Cost Search in Java
      1. USmiku
    2. COAh, 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.
      singulars
      1. POGraph Tour with Uniform Cost Search in Java
      1. USjoshschreuder
    3. COEDIT: 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)
      singulars
      1. POGraph Tour with Uniform Cost Search in Java
      1. USjoshschreuder
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload