(Exercise 11) As a rough guide to what your submission will look like, Im expecting something roughly like this:
# I ve chosen to implement the XXXX algorithm
%%%%
# I #
# I
# I
# I
# I
#xandywillbeusefulwhenIcometo
# # #
#
# # # #
# #
# # #
# # # # #
The initial step of the algorithm requires me to start with variable .. equal to
then do
m going to assume I m given the matrix C . . . containing costs/capacities
will also create the following variables . . . will use x to describe .
will use y to describe .
will use A to describe .
%%%%
# Initial values of x, y, A, etc. need to be .
%%%%
#This code creates an adjacency matrix A from C # Code
# Code
# Code
%%%%
# Lets test the code out for the following problem
# Pick a matrix C to test the code on
%%%%
[Code
Lets Code Code Code
[Look Check
to set initial values of variables] try it.
to see if the first iteration worked] the variable values . . . did i t work?
Think
. . . . the second iteration with the answers . from the first iteration
about how to create the loop to perform
Copy and paste code from above to try and create a loop which will perform iteration after iteration
after iteration of the algorithm .
.. (this is hard! but have a go!)
4-31
Exercise 11 (Lovelace). For this final week, you have a choice of an algorithm from the final chapter to try and implement. Try and spend an hour or so on the algorithm you pick. You can choose from
(a) Prims greedy algorithm (b) Dijkstras algorithm
(c) Bellman-Ford algorithm (d) Hungarian algorithm
Pick ONE of them to try and make progress towards implementing. Prim and Bellman-Ford are likely the easier of the algorithms to attempt. But I dont ex- pect you to necessarily create a fully working algorithm.
I recommend your target to be a function called Prim(C), or Dijkstra(C) or BellmanFord(C), or Hungarian(C) into which a user should input the cost/capacity matrix C where C[i,j] = cij for all i,j V. The code for (c) and (b) could assume the target flow is from vertex 1 to vertex n (note that n = nrow(C)). For (d) you will need to look up (online probably) a method to perform the tricky part of identifying the lines (and the 0-solution), which we only did by eye.
DO NOT dive straight in and attempt to write the function immediately, have a look at my advice below. Perhaps your last step (if you get that far) will be to put together the bits of code youve written into a nice function.
Let me also remind you that I want to just see evidence of you working productively and commenting effectively for at least an hour on the method you select. I doubt many of you will have a working prototype by this point, I am not expecting you to have one. But I would like you to reflect on the skills youve (hopefully) learnt during the term!
Whichever problem you choose these are are the sorts of things you should do, and comment on:
1. Identify what variables youre going to use (and say what their names will be in the comments).
2. PerforminitialworkonthematrixCtocreateadditionalvariableswhichmight be useful (things like: variable n, the set V , an adjacency matrix, or a list of edges that exist in the graph). #Where do you plan to use them?
3. Identify the initial values of the variables youve chosen. #Tell me what they are and why!
4. Write code that performs the first iteration of the algorithm. #Remember to comment what your code is trying to do.
5. Where it gets tricky is then trying to create a loop in your code which after an iteration, will prepare the variables to begin the second iteration again using the code already written.
4-32
Reviews
There are no reviews yet.