python graph 算法 + 卡车运输问题

*若价格不公道,可以让提问者在平台追加赏金哦,平台是您利益的保证

已完成
python graph 算法 + 卡车运输问题-134****3077
134****3077 1年前发布
悬赏:200.0 元

问题详情:分类: python

更详细说明请加Q

Project Part 2
• 第2部分有两个task。
o 在这两个任务中,我们都说地图是无向加权图G,用图的边缘及其权重的元组的Python列表表示。 G中的每个元组(u,v,w)表示从顶点u到顶点v有一条边,使得边的权重为w。由于图形是无向的,因此您还需要考虑权重为w的从v到u的边。
o 给定从位置v1到位置vn的路径[v1,v2,...,vn],我们说路径的权重或从v1到vn的距离(采用该路径)是路径上所有边的权重之和。(请注意,这不是加权图的标准表示形式。您可能会发现将输入图转换为邻接矩阵的邻接表很有帮助。)
o 假设:
 地图是连接的,即任何两个位置之间至少有一条路径。
 每个边缘的权重都是非负的。
o 示例:
 下图表示为[(ups,b,7), (ups,c,5), (b,c,8), (b,d,9), (c,d,2)]
 从ups到b再到d点的路径为[ups, b, d]



• Task 1 (part2Task1.py)
o 给定一张地图,其中一个确切的位置是邮政局,请以邮政局为源,实施BFS,DFS和Dijkstra三种算法。
o 具体来说,编写三个函数bfs,dfs和dijkstra。每个功能的输入包括
 地图G;
 邮局office 。
o 输出是一个名为path的Python dictionary ,其中的key是地图G中的位置,因此loc的path [loc]值是从办公室到loc的路径,该路径是通过相应算法计算得出的。 另外,path [office] = [office]。
 对于BFS和DFS,可以从所访问位置的顺序重建从办公室到每个位置的路径。
 对于Dijkstra的算法,从办公室到每个位置loc的路径是从办公室到loc的最短路径。
o 提示:
 如果有多个位置可供选择,请按字母顺序选择它们。
 对于此任务,我们不关心运输package。 我们需要做的就是遍历所有位置。您不需要Package或Truck类。
o 举例:
 鉴于下面的地图,ups是唯一的邮局,



 BFS:第一级只包含ups。 第二级包含b和c,它们的前身是ups。 第三级包含d和前任b,因为b在c之前排队。 因此,输出为

 DFS:输出为

 Dijkstra:从ups开始,我们从ups到其他每个位置的最短路径计算为:



• Task 2 (part2Task2.py)
o 给定具有多个邮局的地图,请将所有邮局中的所有包裹递送到其正确地址。
o 具体来说,编写一个函数deliveryService。该函数具有三个输入:
 一个地图G;
 卡车 truck;
 Python列表package,其中包括所有涉及的package,即所有office里的所有package。
o 输出是一对(deliveredTo,stop),其中
 deliveryTo是一个Python dictionary,其keys为package ids(不是package),而值为地址,因此deliveryTo [id] = addr表示名字为ID的package将交付给addr。 (输出的这一部分用于测试包裹是否已交付到正确的地址。)
 stop是一个Python list,其中包含卡车按顺序进行的所有停靠点。例如,如果将卡车在地址addr1初始化,则开车至ups1,然后开车至addr2,因此 stop = [addr1,ups1,addr2]。 (输出的这一部分用于计算卡车行驶的里程。)
o 限制:
 如果卡车在loc 1,则只有在地图上连接了loc 1和loc 2时,它才能行驶到loc 2。
 不要更改
• 输入图中的任何内容;
• 包裹的收货address和id,
• 在不正确使用removePackage功能的情况下不要更改package的office;
• 在不正确使用driveTo功能的情况下不要更改卡车的位置
 不要从packages参数中删除项目。
o 提示:
 尽量减少代码的运行时间和卡车的行驶里程

*若价格不公道,可以让提问者在平台追加赏金哦,平台是您利益的保证。你觉得当前的价格如何呢,奉上您珍贵的一票吧

虚高0人次 适中0人次 偏低0人次

分享海报会更快解决你的问题哦!分享海报

此处可发布评论

评论(0

暂无评论,快来写一下吧
客服QQ 1913284695