首页
网站开发
桌面应用
管理软件
微信开发
App开发
嵌入式软件
工具软件
数据采集与分析
其他
首页
>
> 详细
代做program、Python程序语言代写
项目预算:
开发周期:
发布时间:
要求地区:
Background
Spatial Networks for Locations
Locations are connected via roads (we assume traders can travel in both
directions!) These locations form a spatial network. As traders used horses for travelling, they couldn’t travel too far!
Pottery Trade
Pottery trade was very active at that times. Each location had its own supply and demandfor pottery. The supply and demand were communicated by traders who also formed their
own networks. They also potentially communicated the prices, but in these project wewill
disregard this information.
Social Networks for Traders
Traders living in some locations know each other and exchange information about supplyand demand via postal services. These traders for a social network.
How to Represent Networks
Each network can be presented as a graph. In this project, we will focus on undirectedgraphs: both social and spatial networks can be represented as graphs:
1. Spatial networks: nodes correspond to locations, and edges —to roads betweenthem (both directions)
2. Social networks: nodes correspond to traders, and edges connect those who
know each other (communicate)
Networks/graphs can be very different!
Project Questions
1. Represent road maps and trader networks as graphs
2. Find the shortest path between any two locations (return the shortest path andthedistance)
3. (Static traders) Find the best trading options for a particular trader residing in aparticular location. Core concepts: Itineraries
Itineraries provide the basis for our spatial network. They are provided as a list of (L1,L2, distance) tuples; listed in any order. L1 and L2 are provided as strings, distance is an integer number (miles).
In the example:
>>> itineraries = [('L1', 'L2', 20), ('L2', 'L3', 10), ('L1', 'L4', 15), ('L4','L5',5), ('L4', 'L8', 20), ('L5', 'L8', 22), ('L5', 'L6', 6), ('L6', 'L7', 20)]
Supply and Demand of Goods (Pottery)
Each location has its own supply and demand in pottery: supply is provided as a positivenumber, demand — as a negative. Locations with the highest demand should be servedfirst. Assume both numbers are integers. This is provided as a dictionary (in no particular order)
>>> status = {'L1':50, 'L2':-5, 'L4':-40, 'L3':5, 'L5':5, 'L8':10, 'L6':10, 'L7':-30}Trader Locations
Traders reside in some but not all locations. Only locations where traders are present cantrade. Each location can have maximum a single trader. Traders are provided as strings.
Trader locations are provided as a dictionary (in no particular order). In the example:
>>> trader_locations = {'T1':'L1', 'T2': 'L3', 'T3':'L4', 'T4':'L8', 'T5':'L7','T6':'L5'}
Social network of Traders
Traders also form a social network. A trader only trades within their own network
(considers friends only). Traders also have access to supplies and demands in the
corresponding locations. Trader friendships are provided as a list of tuples (in no particular order):
>>> traders = [('T1','T2'), ('T2', 'T5'), ('T3', 'T1'), ('T3', 'T5'), ('T3', 'T6')]Q1
Write a function create_spatial_network(itineraries) that takes itineraries (a list of
tuples) and returns for each location its neighbors and distances to them. A location is
considered to be a neighbour of another location if it can be reached by a single road (oneedge).
Input:
itineraries: a list of tuples, where each tuple is of the
form (location1, location2, distance). location1 and location2 are the stringlabels for these locations and distance is an integer. Your function should return a list of tuples, where each tuple is of the
form (location, neighbours). neighbours should be of the
form [(neighbour1, distance1), (neighbour2, distance2), ...] and be sorted by their
distances (in the increasing order). If two or more neighbors have the same distance tothe location, tie-break by alphanumeric order on their labels. Note that in addition to the neighbors, the overall list has to be sorted. You may assume: Distances are non-negative integer values
Inputs are correctly formatted data structures and types
There are no duplicate entries itineraries, and in each neighbor pair only appear
once (i.e. no [('L1', 'L2', 20), ('L2', 'L1', 20)])
Here is a diagram of an example network:
For the network above, this would be a possible itineraries and the function should
return the following:
>>> itineraries = [('L1', 'L2', 20), ('L2', 'L3', 10), ('L1', 'L4', 15), ('L4','L5',5), ('L4', 'L8', 20), ('L5', 'L8', 22), ('L5', 'L6', 6), ('L6', 'L7', 20)]
>>> create_spatial_network(itineraries)
[('L1', [('L4', 15), ('L2', 20)]), ('L2', [('L3', 10), ('L1', 20)]), ('L3', [('L2',10)]),('L4', [('L5', 5), ('L1', 15), ('L8', 20)]), ('L5', [('L4', 5), ('L6', 6), ('L8', 22)]),('L6', [('L5', 6), ('L7', 20)]), ('L7', [('L6', 20)]), ('L8', [('L4', 20), ('L5', 22)])]A different example (not pictured):
>>> itineraries = [('L4', 'L1', 2), ('L3', 'L1', 5), ('L1', 'L5', 5), ('L2', 'L5',1)]>>> create_spatial_network(itineraries)
[('L1', [('L4', 2), ('L3', 5), ('L5', 5)]), ('L2', [('L5', 1)]), ('L3', [('L1',5)]),('L4', [('L1', 2)]), ('L5', [('L2', 1), ('L1', 5)])]
Q2
Write a function sort_demand_supply(status) that takes a dictionary of demands andsupplies and returns the information as a list of tuples sorted by the value so that locationswith greatest demands (the most negative number) are provided first.
Input: status: a dictionary of demands and supplies. The keys are the location labels
(strings) and the values are integers, where a positive value represents supply
and a negative value represents demand. Your function should return a list of tuples, where each tuple is of the
form (location, demand_supply), and the list should be sorted in ascending order by
their demand_supply (i.e. greatest demand to greatest supply). If two or more locationshave the same demand or supply, tie-break by alphanumeric order on their labels. You may assume: Inputs are correctly formatted data structures and types
>>> status = {'L1':50, 'L2':-5, 'L4':-40, 'L3':5, 'L5':5, 'L8':10, 'L6':10, 'L7':-30}>>> sort_demand_supply(status)
[('L4', -40), ('L7', -30), ('L2', -5), ('L3', 5), ('L5', 5), ('L6', 10), ('L8',10),('L1', 50)]
Another example:
>>> status = {'L1':30, 'L2':-20, 'L4':100, 'L3':-50, 'L5':-60}
>>> sort_demand_supply(status)
[('L5', -60), ('L3', -50), ('L2', -20), ('L1', 30), ('L4', 100)]
Q3
Write a function create_social_network(traders) that takes traders, a list of tuples
specifing trader connections (edges in the trader social network) and returns a list
containing (trader, direct_connections) for each trader in traders.
Input: traders: a list of tuples specifing trader connections (edges in the trader social
network). Each tuple is of the
form (trader1, trader2) where trader1 and trader2 are string names of
each trader.
Your function should return list of tuples in alphanumeric order of trader name, where
each tuple is of the form (trader, direct_connections), and direct_connections is analphanumerically sorted list of that trader's direct connections (i.e. there exists an edgebetween them in the trader social network). You may assume: Inputs are correctly formatted data structures and types. Just like Q1a, you don't
need to guard against something like [('T1', 'T2'), ('T2', 'T1')] or duplicate
entries.
The pictured example:
>>> traders = [('T1','T2'), ('T2', 'T5'), ('T3', 'T1'), ('T3', 'T5'), ('T3', 'T6')]>>> create_social_network(traders)
[('T1', ['T2', 'T3']), ('T2', ['T1', 'T5']), ('T3', ['T1', 'T5', 'T6']), ('T5', ['T2','T3']),('T6', ['T3'])]
Another example (not pictured):
>>> traders = [('T1', 'T5'), ('T2', 'T6'), ('T3', 'T7'), ('T4', 'T8'), ('T1', 'T6'),('T2', 'T7'), ('T3', 'T8'), ('T4', 'T5'), ('T1', 'T7'), ('T2', 'T8'), ('T3', 'T5'),('T4','T6')]
>>> create_social_network(traders)
[('T1', ['T5', 'T6', 'T7']), ('T2', ['T6', 'T7', 'T8']), ('T3', ['T5', 'T7', 'T8']),('T4', ['T5', 'T6', 'T8']), ('T5', ['T1', 'T3', 'T4']), ('T6', ['T1', 'T2', 'T4']),('T7',['T1', 'T2', 'T3']), ('T8', ['T2', 'T3', 'T4'])]
Q4
Write a function shortest_path(spatial_network, source, target, max_bound) that
takes a spatial network, initial (source) location, target location and the maximumdistance(that a trader located in the initial location can travel) as its input and returns a tuple withashortest path and its total distance.
Input: spatial_network: a list of tuples, where each tuple is of the
form (location, neighbours) and neighbours is of the
form [(neighbour1, distance1), (neighbour2, distance2), ...]. This
corresponds with the output of the function you wrote for Q1a. source: the location label (string) of the initial location. target: the location label (string) of the target location. max_bound: an integer (or None) that specifies the maximum total distance that
your trader can travel. If max_bound is None then always return the path withminimum distance. Your function should return a tuple (path, total_distance), where path is a string of
each location label in the path separated by a - hyphen character, and total_distanceisthe total of the distances along the path.
If there's two paths with the same minimum total distance, choose the path with morelocations on it. If there's two paths with the same minimum total distance and they havethe same number of locations on the path then choose alphanumerically smaller pathstring.
If there is no path with a total distance within the max_bound then your function shouldreturn (None, None). You may assume:
Inputs are correctly formatted data structures and types. Distances are non-negative integer values. The network is connected, so a path always exists, although it may not have atotal distance within the maximum bound.
>>> spatial_network = [('L1', [('L4', 15), ('L2', 20)]), ('L2', [('L3', 10), ('L1',20)]),('L3', [('L2', 10)]), ('L4', [('L5', 5), ('L1', 15), ('L8', 20)]), ('L5', [('L4',5),('L6', 6), ('L8', 22)]), ('L6', [('L5', 6), ('L7', 20)]), ('L7', [('L6', 20)]), ('L8',[('L4', 20), ('L5', 22)])]
>>> shortest_path(spatial_network, 'L1', 'L3', 50)
('L1-L2-L3', 30)
>>> shortest_path(spatial_network, 'L1', 'L3', 0)
(None, None)
>>> shortest_path(spatial_network, 'L1', 'L3', 10)
(None, None)
>>> shortest_path(spatial_network, 'L1', 'L3', None)
('L1-L2-L3', 30)
Q5
In this question you will be writing a
function trade(spatial_network, status_sorted, trader_locations, trader_network, max_dist_per_unit=3) that makes a single trade.
Input:
spatial_network: a list of tuples, where each tuple is of the
form (location, neighbours) and neighbours is of the
form [(neighbour1, distance1), (neighbour2, distance2), ...]. This
corresponds with the output of the function you wrote for Q1a. status_sorted: a list of tuples, where each tuple is of the
form (location, demand_supply), and the list is sorted in ascending order by
their demand_supply (i.e. greatest demand to greatest supply) with ties brokenalphanumerically on location label. This corresponds with the output of the
function you wrote for Q1b. trader_locations: a dictionary of trader locations. The structure of this
is trader_name: trader_location, where
both trader_name and trader_location are strings. trader_network: a list of tuples in alphanumeric order of trader name, whereeach tuple is of the form (trader, direct_connections), and direct_connections is an alphanumerically sorted list of that trader's direct
connections (i.e. there exists an edge between them in the trader social network). This corresponds with the output of the function you wrote for Q1c. max_dist_per_unit: a float or integer value that represents the maximumthetrader is willing to travel per unit. This parameter should have a default of 3in your
function. Your function should return a single trade as a
tuple (supplier_location, consumer_location, amount) where supplier_locationand consumer_location are location labels (strings) and amount is a positive integer. If notrade is possible return (None, None, None).
Traders from the locations with highest demand contact their social network asking for
help. Then they choose the contacts worth travelling to, based on distance and the
amount of supply there. The trade shoud be determined as follows:
1. Find the location with the highest demand, this will be the consumer location. 2. Find the trader at the consumer location (skip this location and go back to step1if
there are no traders at this location) and consider the trader's connections. 3. A supplier location can only supply to the consumer location if their status is
positive (i.e. they have items to supply) and can supply an amount up to this value(i.e. they can't supply so much that they result in having a demand for the itemthey are supplying). 4. If a supplier location is directly neighbouring by a single road (adjacent) to theconsumer location then the distance used is the direct distance between the twolocations, even if there exists a shorter route via other locations. If the supplier andconsumer are not adjacent then the shortest_path function should be used todetermine the distance. 5. The trader will trade with the connection that has the highest amount of units tosupply, subject to meeting the max_dist_per_unit of the distance/units ratio. 6. Then if no trade is possible in this location, consider the next location. Return (None, None, None) if all locations have been considered. You may assume: Inputs are correctly formatted data structures and types. Distances are non-negative integer values. There will be at most one trader at any particular location.
Consider the spatial and trader network in the image above. With a
default max_dist_per_unit of 3, the trader will only consider travelling maximum3 milesfor each unit (one direction), i.e. they will agree to travel 6 miles for get 2 pottery units but
not a single one.
In the example, we have 'L4' as the location with the highest demand of 40 units
(demand_supply=-40) and the trader 'T3' who resides there. 'T3''s direct connectionsare ['T1', 'T5', 'T6']. We can't trade with 'T5' because at their location ('L7') there is
also demand for the items. We compare the units able to be supplied and the distance-units ratio for each potential
supplier: T1:
o location: L1
o supply max: 50
o distance: 15
o so they could supply all 40 units that are demanded at L4
o distance/units = 15/40 = 0.375
T6:
o location: L5
o supply max: 5
o distance: 5
o so they could supply 5 of the units that are demanded at L4
o distance/units = 5/5 = 1.0
Since T1 has the largest amount of units able to be supplied, and the distance/units ratiois below the maximum (3), this trade goes ahead and the function would
return ('L1', 'L4', 40). >>> spatial_network = [('L1', [('L4', 15), ('L2', 20)]), ('L2', [('L3', 10), ('L1',20)]),('L3', [('L2', 10)]), ('L4', [('L5', 5), ('L1', 15), ('L8', 20)]), ('L5', [('L4',5),('L6', 6), ('L8', 22)]), ('L6', [('L5', 6), ('L7', 20)]), ('L7', [('L6', 20)]), ('L8',[('L4', 20), ('L5', 22)])]
>>> status_sorted = [('L4', -40), ('L7', -30), ('L2', -5), ('L3', 5), ('L5', 5), ('L6',10), ('L8', 10), ('L1', 50)]
>>> trader_locations = {'T1':'L1', 'T2': 'L3', 'T3':'L4', 'T4':'L8', 'T5':'L7','T6':'L5'}
>>> trader_network = [('T1', ['T2', 'T3']), ('T2', ['T1', 'T5']), ('T3', ['T1','T5','T6']), ('T5', ['T2', 'T3']),('T6', ['T3'])]
>>> trade(spatial_network, status_sorted, trader_locations, trader_network)
('L1', 'L4', 40)
More examples:
>>> spatial_network = [('L1', [('L4', 2), ('L3', 5), ('L5', 5)]), ('L2', [('L5',1)]),('L3', [('L1', 5)]), ('L4', [('L1', 2)]), ('L5', [('L2', 1), ('L1', 5)])]
>>> status = {'L1':30, 'L2':-20, 'L4':100, 'L3':-50, 'L5':-60}
>>> status_sorted = [('L5', -60), ('L3', -50), ('L2', -20), ('L1', 30), ('L4',100)]>>> trader_locations = {'T1': 'L1', 'T2': 'L2'}
>>> trader_network = [('T1', ['T2']), ('T2', ['T1'])]
>>> trade(spatial_network, status_sorted, trader_locations, trader_network)
('L1', 'L2', 20)
>>> trade(spatial_network, status_sorted, trader_locations, trader_network,
max_dist_per_unit=0.001)
(None, None, None)
Q6
In this part you'll be using the trade() function from part 3a iteratively to determine thestatus after several trades. Write a
function trade_iteratively(num_iter, spatial_network, status, trader_locations, trader_network, max_dist_per_unit=3) that takes the number of iterations to perform,
the spatial network, status dictionary, trader locations dictionary, trader network, and
maximum distance per unit and returns a tuple containing the sorted status list
after num_iter trades along with a list of trades performed.
Input: num_iter: the number of iterations to perform as an integer or None if the
iteration should continue until no further trades can be made. spatial_network: a list of tuples, where each tuple is of the
form (location, neighbours) and neighbours is of the
form [(neighbour1, distance1), (neighbour2, distance2), ...]. This
corresponds with the output of the function you wrote for Q1a. status: a dictionary of demands and supplies. The keys are the location labels
(strings) and the values are integers, where a positive value represents supply
and a negative value represents demand. trader_locations: a dictionary of trader locations. The structure of this
is trader_name: trader_location, where
both trader_name and trader_location are strings. trader_network: a list of tuples in alphanumeric order of trader name, whereeach tuple is of the form (trader, direct_connections), and direct_connections is an alphanumerically sorted list of that trader's direct
connections (i.e. there exists an edge between them in the trader social network). This corresponds with the output of the function you wrote for Q1c.
max_dist_per_unit: a float or integer value that represents the maximumthetrader is willing to travel per unit. This parameter should have a default of 3in your
function. At each iteration, the next trade to be performed is determined by the process in part 3a. We strongly suggest using the provided trade() function to find this trade. Your functionshould update the status dictionary at each iteration. Your function should return a tuple (final_supply_sorted, trades) containing the sorteddemand-supply status after num_iter trades along with a list of trades performed. The final_supply_sorted should be a list of tuples, where each tuple is of the
form (location, demand_supply), and the list should be sorted in ascending order by
their demand_supply (i.e. greatest demand to greatest supply). If two or more locationshave the same demand or supply, tie-break by alphanumeric order on their
labels. trades should be a list of each trade performed, where a trade is of the
form (supplier_location, consumer_location, amount) where supplier_locationandconsumer_location are location labels (strings) and amount is a positive integer. You may assume: Inputs are correctly formatted data structures and types. Distances are non-negative integer values. There will be at most one trader at any particular location.
In the example pictured, only one trade can occur:
>>> spatial_network = [('L1', [('L4', 15), ('L2', 20)]), ('L2', [('L3', 10), ('L1',20)]),('L3', [('L2', 10)]), ('L4', [('L5', 5), ('L1', 15), ('L8', 20)]), ('L5', [('L4',5),('L6', 6), ('L8', 22)]), ('L6', [('L5', 6), ('L7', 20)]), ('L7', [('L6', 20)]), ('L8',[('L4', 20), ('L5', 22)])]
>>> status = {'L1': 50, 'L2': -5, 'L4': -40, 'L3': 5, 'L5': 5, 'L8': 10, 'L6': 10,'L7':-30}
>>> trader_locations = {'T1': 'L1', 'T2': 'L3', 'T3': 'L4', 'T4': 'L8', 'T5': 'L7','T6':'L5'}
>>> trader_network = [('T1', ['T2', 'T3']), ('T2', ['T1', 'T5']), ('T3', ['T1','T5','T6']), ('T5', ['T2', 'T3']),('T6', ['T3'])]
>>> trade_iteratively(1, spatial_network, status, trader_locations, trader_network)([('L7', -30), ('L2', -5), ('L4', 0), ('L3', 5), ('L5', 5), ('L1', 10), ('L6', 10),('L8',10)], [('L1', 'L4', 40)])
>>> trade_iteratively(None, spatial_network, status, trader_locations, trader_network)([('L7', -30), ('L2', -5), ('L4', 0), ('L3', 5), ('L5', 5), ('L1', 10), ('L6', 10),('L8',10)], [('L1', 'L4', 40)])
软件开发、广告设计客服
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-23:00
微信:codinghelp
热点项目
更多
cis432代做、代写python/java程...
2024-05-04
eeen3007j代写、c++程序设计代...
2024-05-04
代写data程序、代做c/c++, jav...
2024-05-04
comp2006代做、代写c++程序语言
2024-05-04
comp26020代做、java/c++设计编...
2024-05-04
csci251 advanced programming...
2024-05-03
cs 6290: high-performance co...
2024-05-03
assignment 2: executing and ...
2024-05-03
ecse427/comp310 programmin...
2024-05-03
cs 452 (fall 22): operating...
2024-05-03
comp9414 23t2 assignment 2 ...
2024-05-03
dpst1091 23t1 assignment 2 ...
2024-05-03
program代做、代写python设计编...
2024-05-03
热点标签
finm8007
comp2006
comp26020
comp1721
eeen3007j
cis432
csci251
comp5125m
com398sust
32022
mth6158
comp328
finn41615
2024
mec302
mgmt3004
mgt7158
com160
as.640.440
econ3016
finm7405
econ7021
fin600
infs4205/7205
mktg2510-
f27sb
csse2310/csse7231
rv32i
eecs 113
comp1117b
cs 412
comp 315
econ7300
comp2017
ecs 116
fit5046
com6511
comp30024
acs341
econ1020
isys3014
acc408
comp1047
csc 256
cs 6347
finm7008
comp34212
csmde21
estr2520
comp285/comp220
mds5130/iba6205
finc6010
is3s665
busi2194
125.785
iom209
msin0041
econ339
cmt218
mast10007
comp5349
ecx2953/ecx5953
bios706
comp3310
mth6150
comp30027
comp20005
eec286
busi2211
bff2401
fnce90046
visu2001
mang6554
finc6001
125785
data423-24s1
engi 1331
fint2100
(520|600).666
can202
cs 61b
mast20029
info20003
stat512
econ3208
cmpsc311
engg1340
ecmt1010
fit5216
basc0003
ee3121
acct2002
comp5313
busi2131
ise529
elec372/472
csit940/csit440
cenv6141
comp3027/comp3927
ftec5580
comp1433
msci223
mark203
en3098
eden1000
ece6483
econ4410
mats16302
cs 6476
com6521
comp222
comp3211
comp10002
csc1002
chc6186
cs 161
comp27112
comp282
swen20003
comm1190
elec9764
acfi3308
acct7101
fin6035
comp2048
geog0163
comp2013
coen 146
dts101tc
sehh2042
comp30023
comp4880/8880
cs 455
07
stat0045.
fil-30023
celen085
psyc40005
math40082
are271
comp9311
ee5311
imse2113
comp 2322
acct2102
fnd109
int102
is3s664
is6153
data4000
accfin5034
fit5212
cs536-s24
fit5225
ecos3006
mes202tc
finc5001
stat3061
csc171
cs1b
7ssmm712
bu.450.760
cs170
comp3411
swen90004
cpt206
comp5313/comp4313—large
bl5611
kxo206
comp532
elec207
kxo151
cs 2820
cpt108
math2319
dts204tc
qm222
comp2511
ccs599
infs1001
mat2355
eeee4123
25721
ifn647
pols0010
hpm 573
qbus6860
comp9417
csci 1100
stat0023
cse340
comp2003j
cs 2550
cs360
fin 3080
ierg 4080
cs6238
cit 594
finm7406
hw6
联系我们
- QQ: 9951568
© 2021
www.rj363.com
软件定制开发网!