编程思维训练趣味任务(十二)
2022-05-26 本文已影响0人
Python_Camp
一个社区由9个城镇由一个广泛的道路系统连接起来。要求拓宽一些现有的道路。一项调查显示了拓宽每一段道路的成本,结果如下图所示。费用以当地货币表示。委员会不关心卡车是否走最短的路线。它只要求有一种方式,卡车将能够从任何一个城镇行驶到社区中的任何其他城镇。委员会必须支付的最小的总费用是多少?
image.png策略思路:
1、每个节点与相邻节点之间中最短的线
2、每三个相邻节点之间避开最长的边;
3、选择易于算法编码实现的表达方式;
图1-4 表达策略的实现过程
image.png image.png image.png image.png算法实现易于字典结构表达:
image.png# 字典表达图的节点连接
graph = {'A': set(['B', 'C', 'D']),
'B': set(['A', 'C', 'J']),
'C': set(['A','B', 'D', 'E','F']),
'D': set(['A', 'C', 'F']),
'E': set(['C', 'G', 'H']),
'F': set(['D', 'G']),
'G': set(['E', 'F', 'H']),
'H': set(['E', 'G', 'J']),
'J': set(['B', 'H'])}
print(graph['A'])
再继续算法实现之前,请参考历史文章,关于最短路径的一种效率比较低的写法。
疫情后想游遍中国几个大城市,每个城市之间坐高铁。为了节省成本需要规划线路,约束条件是:
每个城市只去一次;
整个旅程的总费用最少;