| OBJECTIVE | Implement a Uniform-Cost-Search Algorithm (BY YOURESELF! NO PAIR PROGRAMMING) |
| DETAILED DESCRIPTION |
In lecture we covered some pseudo code for running a breadth-first traversal of a graph. The algorithm presented, however, was ignorant of edge weights. A modification is required to generate the correct traversal. This modified BFS search is also called Uniform Cost Search. In Uniform Cost Searches, the algorithm must keep track of available edges to traverse on a priority queue. The priority queue makes sure that the algorithm is always selecting the appropriate edge. The "priority" of the elements is determined by their total, weighted distance from the root. We can prove by induction (not shown) that the outcome will be a traversal tree where the path from the root to every connected node in the tree is optimal ( However, there are some questions about what should go into the priority queue, and how the data should be handled. For example, it is possible to have two edges to a single vertex available for traversal, or available to be inserted into the queue. How do you handle that? For this homework, you must implement the UCS algorhtm for traversing a weighted graph. We are providing you a complete a working example of BFS and all of the framework you require to implement UCS. Additionally, we have provided you a GUI and command-line interface for testing your code as well as some example graphs. You may define additional graphs using the GUI if you wish. For information on using the framework please read this. Also, we would appreciate feedback. Please let us know how long this homework took you and how useful it was on a scale of 1-10. For more details, see the section "SUBMITTING" below. |
| CHECKING OUT | You can check-out the homework1 framework by checking out comp314-students/homework/homework1 from subversion. |
| SUBMITTING | You will use the "turnin" script to submit your code.
ALSO YOU MUST INCLUDE A "README.txt" FILE that says (1) how long it took you to complete the homework and (2) how useful you thought the assignment was on a scale of 1 to 10 (10 is the most useful, 1 is busy work). turnin -c comp314 -p hw1 files
comp314.algorithms.GraphUCS file (and any supporting
files if you created them).
|
| GRADING | Your UCS algorithm will be tested against various graphs, with various starting (root) nodes. Some of these graphs are provided to you, and some of them are not. The output must provide:
|
| OTHER DOCS: |
|