本次Python代写是完成破冰船问题的编程

cmpt310
Assignment 2
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 4-person 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 (warm-up: Erdos-Renyi 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 (warm-up: 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 double-check
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 re-run your experiment.
Question 4 (Approximate)
Re-do 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 re-run 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