本次Python代写是完成破冰船问题的编程
cmpt310
Assignment 2
In this assignment weʼre going to explore the Ice Breaker problem: given a group of people, whatʼs the minimum number of teams they can be partitioned into such that no team has 2 (or more) members who are friends.
The hope is that this encourages people to make new friends.
We assume the people are named 0, 1, 2, …, , and that we have a friendship graph, i.e. a graph with
nodes labeled 0 to (each node is a person), where nodes and are connected by an edge just when and
are friends. Friendship is symmetric: if is a friend of , then is a friend of . Plus a person cannot be friends
with themselves.
This assignment permits solutions where a team can have only 1 person on it. While this is not a very practical assumption for a real ice breaker event, we use it here to simplify things.
As with the first assignment, do not use any modules or code except those from the standard Python 3 library, or
from the textbook code from Github.
Solving the Ice Breaker Problem with CSPs
We want you to model this as a constraint satisfaction problem (CSP). Use one CSP variable for each of the
people: . The domains for these variables are team names, which will be integers 0, 1, 2, … etc. All the
domains are the same. The constraints on the CSP are all notequal constraints that come from the friendship
graph: if person and are friends, then we have the constraint , i.e. two friends cannot be on the same
team.
The problem is to find the smallest number of teams that satisfies all the constraints. In other words, we
want to find the smallest domain size for the variables that satisfies all the constraints of the friendship graph.
The word smallest is very important here. If we were satisfied with any number of teams, then we could just put
each person on a team by themselves.
Using csp.py
For this assignment, use the code in csp.py from the textbook code. You can modify this code if you want to
(donʼt actually modify the file csp.py — copy the code you want to change into the appropriate .py and modify it
there), but do not change the input or output formats for any of the functions.
Represent a friendship graph as a Python dictionary where the keys are the people (integers from 0 to ),
and the corresponding values are their friends in a list. For example, here is a 4person friendship graph:
g = {0: [1, 2], 1: [0], 2: [0], 3: []} # format of graphs for this assignment
This graph has 4 people, named 0 to 3, and it looks like this:
0—2


1 3
0 and 2 are friends, and 0 and 1 are friends. Person 3 is not friends with anyone. In Python, g[0] is the list of all
people that 0 is friends with, g[1] is the list of all people that 1 is friends with, and so on.
To solve this ice breaker problem, we use four CSP variables: . The constraints correspond to edges
in the graph, and for g they are: .
It is not hard to see for this graph that 2 teams are enough, e.g. put 0 and 3 on team 0, and 1 and 2 on on team
1. As a CSP solution, this would be written . In Python, it would be represented
by this dictionary:
X = {0:0, 1:1, 2:1, 3:0}
Make sure that graphs and CSP solutions have exactly the format described here!
Question 1 (warmup: ErdosRenyi random graphs)
Create a function called rand_graph(p, n) that returns a new random graph with nodes numbered 0 to
such that every different pair of nodes is connected with probability . Assume , and .
For example:
>>> rand_graph(0.5, 5)
{0: [2], 1: [2, 4], 2: [0, 1, 4], 3: [], 4: [1, 2]}
n
n n − 1 n
n − 1 i j i j
i j j i
n
X1, … , Xn
i j Xi ≠ Xj
n − 1
X0, X1, X2, X3
X0 ≠ X1, X0 ≠ X2
X0 = 0, X1 = 1, X2 = 1, X3 = 0
n n − 1
p n > 1 0 ≤ p ≤ 1
06/06/2020 Assignment 2 — cmpt310summer2020 documentation
https://www2.cs.sfu.ca/CourseCentral/310/tjd/a2.html 2/3
>>> rand_graph(0.1, 10)
{0: [4, 7], 1: [3, 6], 2: [9], 3: [1, 6], 4: [0, 5],
5: [4], 6: [1, 3], 7: [0], 8: [], 9: [2]}
Notice that if a appears in the list for key b, then b also appears in the list for key a.
The higher the value of , the more edges the resulting graph will have.
Put all your code for this into a file named a2_q1.py so that the marker can test it.
Question 2 (warmup: Checking Solutions)
Write a function called check_teams(graph, csp_sol) that returns True if the given CSP solution dictionary
csp_sol satisfies all the constraints in the friendship graph, and False otherwise. graph and csp_sol are dictionaries formatted as described above.
Do not use any code from csp.py to implement check_teams. The idea is to use check_teams to doublecheck
the correctness of your results in the questions that follow.
Remember that teams of 1 person are permitted.
Put all your code for this into a file named a2_q2.py so that the marker can test it.
Question 3 (Exact)
For , generate 6 random friendship graphs as follows:
graphs = [rand_graph(0.1, 31), rand_graph(0.2, 31), rand_graph(0.3, 31),
rand_graph(0.4, 31), rand_graph(0.5, 31), rand_graph(0.6, 31)]
For each of these friendship graphs, calculate the exact minimum number of teams that the people can be put
into such that no team has 2 (or more) people on it who are friends.
Important: This question asks for an exact answer, so make sure the method you use to solve this problem
guarantees this!
Note: If you like, you can calculate answers for graphs with values greater than 0.6, but the running times
might be very slow.
Repeat the above step at least 5 times, using 6 different random graphs each time (make sure to use the same
values for each set of 6 graphs). For each solution, keep track of:
the number of teams that the people are divided into
the running time of the solver (donʼt include the time to create the graphs)
the count of the number of times CSP variables were assigned and unassigned
at least one other piece of information (your choice) that you think is useful for helping to understand the
performance of the algorithm; choose something useful!
When you are done, you should have 40 different solutions, with the above data recorded for each solution.
In an Excel worksheet named a2_q3.xlsx (e.g. use Excel, or Google Sheets to make it), make a neat and easy to
understand table summarizing all the data you collected. You should include things like averages for the 5 runs
for each value, and a chart/graph to help visualize your results.
Put all your code for this into a file named a2_q3.py, and include a function called run_q3() that the marker
can, if they like, call to rerun your experiment.
Question 4 (Approximate)
Redo the above experiment, but this time for . For such a large graph, exact values are going to be
hard to calculate in a reasonable amount of time, so you can (should!) use an algorithm that returns an approximate solution, i.e. something close to the smallest number of teams for a given friendship graph, but not necessarily the smallest.
Put your results into an Excel worksheet named a2_q4.xlsx. Put all your code for this question in a file named
a2_q4.py and include a function called run_q4() that the marker can, if they like, call to rerun your
experiment.
What to Submit
For this assignment you should submit at least these 6 files:
a2_q1.py
a2_q2.py
p
n = 31
p
p
p
n = 105
06/06/2020 Assignment 2 — cmpt310summer2020 documentation
https://www2.cs.sfu.ca/CourseCentral/310/tjd/a2.html 3/3
a2_q3.py and a2_q3.xlsx
make sure a2_q3.py contains a function called run_q3() that runs the code that generates your data
a2_q4.py and a2_q4.xlsx
make sure a2_q4.py contains a function called run_q4() that runs the code that generates your data
Make the spreadsheets beautiful, informative, and easy to read. Be sure to include helpful descriptive statistics
like the min, max, average, and median values. You are encouraged to include helpful or informative graphs of
your data. Spelling, grammar, and neatness count!
In addition, donʼt modify any of the files in the textbook code. The markers will be running your code using
the textbook software asis. If you do want to modify textbook code, copy the code you want to change into the
appropriate .py file this assignment asks for, and make the changes there.
As with the first assignment, do not use any modules or code except from the standard Python 3 library, or from
the textbook Python code from Github.
Put all the files needed to rerun your questions into a single .zip archive named a2.zip, and submit it on Canvas before the due date listed there.
Hints
At the Linux commandline, you can use the zip command to compress a folder. For example, if you do all
your work in a folder named aimaa2, then this creates a2.zip:
zip r a2.zip aimaa2
The r option causes zip to recursively include all folders in the resulting .zip file.
Remember, teams of 1 person are permitted. This is just a simplifying assumption for this assignment, and
is not realistic.
Note that there are a couple of extreme cases to be aware of in the ice breaker problem:
If no one is friends with anyone else, then only 1 team — the entire group of people — is needed.
If everyone is friends with everyone else, then teams are needed. Everyone would have to be on a
team by themselves.
If there is someone who is friends with everyone else, then they must be on a team by themselves.
Someone who is friends with no one can be added to any team.
In the file csp.py from the textbook code, there is a useful class called MapColoringCSP.
The ice breaker problem is really just asking you to find the chromatic number of a graph.
n
n
程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
Email: [email protected] 微信:itcsdx
如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。