Part 1: Solving the "Please take me out of here!" with Exhaustive Search
Back to labs page.
The first task requires you to solve the "Please take me out of here!"
problem by implementing an algorithm based on exhaustive search or one of its refinements. Plain exhaustive search simply
generates all possible subsets of edges, tests for each subset whether
it is an hamiltonian path, checks whether it is the best tour seen so far, and
finally outputs the best solution. It is clear that some subsets are
useless to be tested, so blind exaustive search can be improved a
little bit. The only difficulty at this stage is to make sure that no potential solution gets
lost: how do you generate all subsets of edges in a systematic way? How can
you avoid memory overflow if the number of nodes is rather large? Think carefully about
these questions before you start writing code.
As explained in the assignment policy, the submission for this
first part will contain exactly two files, one for the report and one
for the program. Here we collected the requirements we expect from your
files.
PROGRAM REQUIREMENTS
- INPUT: Your program must be able to read input data from files. Two
instances (which define the standard input format we will use to
check your program) are
available as an example:
Please note files are structured in this way:
- The first line contains a natural number bigger than 0, the
number of nodes; let us call it n.
Line does not contain spaces and it is terminated by a newline character.
- Following there are n lines containing probabilities for each
node. Please note all those probabilities must be bigger
than 0, and the sum of them must be exactly 1. All lines
are spaces free and terminated by a newline character.
- Then a matrix for edge costs is printed. Since the graph is
complete, the matrix has n lines and in each line n natural
numbers (bigger than 0) are presented, separated by one space
character. All lines are terminated by a newline character.
- INTERNALS: Since this assignment focuses on algorithms, the
programming related overhead should be as low as possible. Complex
class hierarchies, awkward programming style and all other
distractions can only hide your ideas and result in a negative feedback.
- OUTPUT: your program must output both the value
and the composition (i.e. the set of edges) of the optimal path
Please remember a solution always starts from node 1.
REPORT REQUIREMENTS
For this part your report will be a document written in ENGLISH with the following structure:
- First page: put there your group number on the fire system,
your names, personal numbers and email addresses.
- Chapter 1: Explain how your algorithm works
Use words, high level pseudocode and illustrations. The important
thing is to reveal the underlying idea and as a help to understand
the pseudocode in the next step. A "dry swim" of some steps is very good here.
- Chapter 2: Give the abstract algorithm in pseudocode
This is a mixture of programming language, mathematics, english and
other suitable notation. You can use abstract data types (for instance lists...)
and sentences like "for every edge e in E loop"
- Chapter 3: Justify its correctness
Your algorithm works fine if it produces a feasible solution (the
solution is a tour) and it is the best among all the feasible
solutions. It means you have to convince the reader your code does
not forget to consider any solution, and it always picks the best
one.
Common techniques to do this in a formal way are induction proof and proof by
contradiction.
- Chapter 4: Analyze its complexity
It is not enough to say what it is, you must motivate the complexity from your
algorithm.
It is not enough to analyze the problem, for instance to say that "since we are
traversing a list it must be O(the number of elements in the list)". This only gives a
lower bound. You must analyze your algorithm, refer to your pseudocode/code.
Also state clearly which operations you count as elementary (unit time) operations.
- Chapter 5: Test its performances
Run your program on several instances and record the running
time.
Each instance is characterized by the following features:
- Different number of nodes.
- Different edge costs
- Different probability distributions
What we expect here is a sequence of experiments to show how
variations of graph's features affect performances.
One obvious experiment is to test the behavior of your program when
the number of nodes is increased. But one might ask what happens
when number of nodes and distribution is fixed, while edge costs are
changing.
For all the experiments you perform, try to interpret the result you
see and relate it to the theoric estimation of performance you gave
in Chapter 4.
We strongly recommend you to collect your results in tables like the following one:
| Nodes |
Execution time |
| ... |
... |
and then draw cartesian graphs to visualize the relation between the
parameters you are considering.
Avoid testing the application on instances that take more
than 5 minutes to be completed.
- Appendix: references to all sources you used, if any. And an
example about how to compile and run your program
Submission
To submit you will use the Fire system.
Deadline for this assignment is 9 Semptember, and the deadline is
strict.