logo标签列表

从众多可能路径中找到权重最小的路径

algorithmgraph-algorithm
4

我在作业问题上需要一些帮助/指导。如果有人能指点我如何解决这个问题，我会非常感激 :)

作业

"一只名叫Mo的愤怒鸟正在飞行中，他要飞很长的路程去向猪复仇。为了节省能量以备战，这只鸟将利用降低飞行能耗的气流。在起飞前，BirdHQ给了这只鸟一个以下格式的输入文件：

  1. 第一行只包含1个整数，表示不使用气流飞行1英里所需的恒定能量。
  2. 每个后续行都包含3个以空格分隔的整数：气流的起始英里标记、气流的结束英里标记，以及表示飞越该气流距离所需的总能量的整数。

例如，“3 7 12”这一行意味着飞越从第3英里到第7英里的4英里距离需要12个能量单位。

请注意，气流可以重叠，但鸟不能同时处于多个气流中，并且它不能飞行部分气流。

为简单起见，将最远气流的结束英里标记视为旅程的结束。

编写一个Python程序，输入文件“jetstreams.txt”，以规划Mo应该飞行的最佳气流序列，以使他在整个旅程中能量消耗最小。输入文件中的所有整数均为非负整数。输出最小总能量和表示气流端点的元组列表。

例如，对于给定的样本jetstreams.txt，飞越全部24英里所需的最小总能量为352个能量单位，最佳气流序列为[(0,5), (6,11), (14,17), (19,24)]。"

jetstreams.txt

50
0 5 10
1 3 5
3 7 12
6 11 20
14 17 8
19 24 14
21 22 2

这是否类似于解决图形的最短路径问题？
+1 分针对涉及愤怒的小鸟的作业问题。 - blahman
我已经撤销了将大部分问题移动到外部站点的编辑。1）人们通常不会跟随外部链接，2）这里的问题应该是自包含的。 - dty
3个回答
4

是的。

您有一条“完全不使用喷气流”的路径，它由顶点0、1、3、5、6、7、11、14、17、19、21、22、24编号组成。连接这些顶点的边的“权重”为50*距离-因此，0 -> 1边的权重为50，1 -> 3边的权重为100，依此类推。

然后，您还有额外的边表示喷气流-从0 -> 5加权10，从1 -> 3加权5，等等。

这些构成了一个有向无环图（DAG）。

现在您已经有了这个，可以应用通常的图遍历技术来找到从顶点0到顶点24的“最便宜”的路线。

2

是的，这是一个最短路径问题，其中能量被替代为每条边的长度。在构建示例问题的图形时，从0到24开始用一条直线，每英里50个能量单位的成本。然后绘制喷气流边缘及其能量消耗以完成图形。

1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接