当前位置: 首页> 学生作业 python> python graph 算法 + 卡车运输问题

python graph 算法 + 卡车运输问题

* 若价格不公道,可以让提问者在平台追加赏金哦,平台是您利益的保证
已完成
python graph 算法 + 卡车运输问题 134****3077
赏 200元 收藏

问题详情:

更详细说明请加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 提示:
 尽量减少代码的运行时间和卡车的行驶里程
* 若价格不公道,可以让提问者在平台追加赏金哦,平台是您利益的保证

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

此处可发布评论

    暂无评论

    竞答该问题的人有:

    公告
    更多相关问题
    Python Heap & Graph 问题
    Python 数据结构树 和 二分查找树
    Python 递归,查询函数
    Python的半开放式命题,更详细的instruction可加我qq联系,可议价
    链表有关问题,包括合并、删除,求大神帮忙
    Python 网考 25号九点到十二点半 有往年考试题型
    急 大学入门级python表格类作业
    编写一个爬虫,并主动对比数据,和提醒
    模拟登陆,带验证码。手动输入验证码,验证码图片下载不下来
    python项目代码详解

    第一时间了解动态

    关注我们