COS 226 Programming Assignment 8 - Checklist

If you picked up the files before April 18, replace all occurrences of getClipRect with getClipBounds in the files Graph.java and demo.java.

A hint on Step 3: for the preprocessing step, you should be thinking about a new graph with M^2 nodes.

Help with Java: There are many possible sources for those needing help learning Java. We can recommend a few:
  • Old COS126 Lecture notes on Java (part 1,part 2)
  • A Java Tutorial (from www.javasoft.com or java.sun.com)
    • Overview: This week, the assignment has asked you to solve the shortest path problem in one of three ways (each way requires additional programming, but should result in a better algorithm) You should only turn in one program.

    Here we give an overview of the three steps. (specific requirements of your submissions will be in the following section)

  • Step 1: (you will receive up to 7 points if this step is the only one you complete)
    Compute the shortest path between two points of a graph by using the priority-first search method. The priority of a fringe node should equal the shortest observed path from the source to that node. (see lecture notes for details).

  • Step 2: (you will receive up to 9 points if you completely only the first two steps)
    This step actually consists of two improvements. The first one is essentially a "one-liner" but will already make great improvement in your search. Use the priority-first search, but change the definition of the priority for a fringe node to equal the sum of the shortest observed path in the graph from the source to that node together with the "as-the-crow-flies" distance from the fringe node to the goal.

    After making that change, do the modified search from both the source and the destination at the same time (i.e. alternate taking turns expanding). Your challenge is to figure out how to combine the two paths to get the shortest.

  • Step 3: (You will receive up to 11 points if you complete all three steps)
    In the previous step we used the "as-the-crow-flies" distance as a rough estimate of how far a fringe node is from the goal when walking along the graph. In this step we will spend a bit of preprocessing time in order to get a more accurate estimate to use.

    Consider dividing the space into an M-by-M grid. Temporarily, assume that all nodes in the same grid cell are at distance zero from each other, but that to walk between grid cells, you must walk along one of the original graph edges between a node in one cell and a node in the other. For any two cells, compute the distance of the shortest path which connects a node of one cell to a node of the other. (Truly, you only need to compute this for pairs of cells where one of the cells contains either the source node or the destination node). Once you have pre-computed these new estimates between cells, modify the method from Step 2 to replace the "as-the-crow-flies" estimate with this new estimate of the distance between the cell containing the fringe node and the cell containing the goal.

    • Requirements: No matter which method you turn in, the following is required of your program:
  • After creating the graph, either allow the user to specify the source node and the destination node, or else pick both of these nodes at random.
  • Your algorithm should NOT search the entire graph, rather it should stop as soon as the shortest path between the two nodes has been found.
  • Graphically, you are required to at least do the following:
  • draw the entire original graph.
  • highlight, using some other color, all edges/nodes which your search considered.
  • highlight, using yet another color, the eventual shortest path which was found.
  • leave the final picture on the screen for at least 5 seconds (before quitting or restarting).
    • (obviously, there is a good deal of freedom in how you choose to animate your method).
  • Textually, you must output at least the following:
  • The number of nodes which the search examined.
  • readme Analyze the performance of your method for graphs of V nodes for various values of V, and formulate a hypothesis about the number of nodes that your method examines to find the shortest path between two random nodes, on the average, as a function of V.

    If you implement several of the methods along the way, please also give a brief discussion of the number of nodes examined by the earlier methods (to see if all of the additional work paid off).

    • cos226 Class Page
    wass@cs.princeton.edu
    Last modified: April 8, 2001