Python代写|CM3109 Combinatorial Optimisation Coursework 1


The assignment is described in detail in the attachment.

Explain the concepts of problem state spaces and search

Credit will be awarded against the following criteria.

• [Correctness] Do the answers correctly address the requirements of each task? Does the
provided code run correctly in Task 2?

• [Clarity] Are explanations and summaries easily understandable? Is documentation
clear? Are comments provided in the code to clarify non-standard code fragments?

• [Understanding of concepts] Do the answers show an understanding of basic
optimisation concepts such as neighbourhood?

Notes before starting

• The following programming exercises may be done using a program
ming language of your own choice, though all parts should be done
using the same language. If you wish to use anything other than Java
or Python then please let me know well in advance so I can make sure
I have everything necessary to run your program installed on my com

• If you use any external sources for solving your coursework (e.g. pseu
docode from a website), you should add a comment with a reference to
these sources and a brief explanation of how they have been used.

The aim of this coursework is to use simulated annealing to solve an optimi
sation problem coming from the field of computational social choice – a hot
interdisciplinary topic currently receiving a lot of attention from researchers
in several different fields, including AI. Section 1 provides necessary back
ground to the problem, with the specific coursework tasks coming in Section

We start by introducing the problem we’re looking at, then we discuss how
to represent the input and outputs to this problem, and then we introduce
a particular proposal for approaching this problem which we will aim to
implement via simulated annealing.

Suppose we have a competition with n participants, which is decided by
playing a tournament in which each participant plays one match against each
of the others. (These participants could be football teams, chess players, or
anything). After the tournament is finished we know both (i) the winner of
each match (or if it was a draw), and (ii) the margin of victory (represented
by an integer greater than 0 if it wasn’t a draw). The question is, based
on this information, which participant should be judged to be the winner of
the tournament, who is the runner-up, who places third, and so on up to
the worst? In other words, which ranking of the participants (from best to
worst) appropriately reflects the relative quality of the participants? (We do
not allow ties in the ranking).