从一堆可能的路径中找到权重最小的路径
我需要一些关于家庭作业问题的帮助/指导。如果有人能指出我如何解决这个问题的正确方向，我将非常感激
:)
“一只名叫莫的愤怒的小鸟正在长途跋涉去复仇 在猪身上。为了节省战斗的能量，鸟会采取 喷射流的优势会降低他的飞行能量 消耗。在飞行之前，BirdHQ 给了鸟一个输入文件 格式如下：
- 第一行仅包含 1 个整数，即在没有急流的情况下飞行 1 英里所需的恒定能量。
- 接下来的每一行都包含 3 个空格分隔的整数：喷射流的起始英里标记、喷射流的结束英里标记 流，最后一个整数表示所需的总能量 飞过急流的距离。
例如，“3 7 12”这行表示需要 12 个能量单位才能飞行 3 英里和 7 英里之间的 4 英里。
请注意，急流可以重叠，但鸟不能超过 一次只能喷射一个喷射流，不能飞行部分喷射流。
为简单起见，请考虑最远喷气机的结束英里标记 流作为旅程的终点。
编写一个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
这类似于求解图的最短路径吗？
I needed some help/pointers on a homework problem. I would really appreciate it if someone could point me in the right direction on how to go about solving this problem :)
Assignment
"An angry bird named Mo is flying a long journey to exact his revenge
on the pigs. To save energy for the fight, the bird will take
advantage of jet streams that will lower his flying energy
consumption. Before the flight, BirdHQ gave the bird an input file in
the following format:
- First line contains only 1 integer, which is the constant energy it takes to fly 1 mile WITHOUT jet streams.
- Every subsequent line contains 3 space-separated integers: the start mile marker of the jet stream, the end mile marker of the jet
stream, and lastly an integer denoting the overall energy needed to
fly that jet stream’s distance.For instance, the line “3 7 12″ means it takes 12 energy units to fly
the 4 miles between miles 3 and 7.Note that jet streams can overlap, but the bird cannot be on more than
one jet stream at a time, and it cannot fly partial jet streams.For simplicity, consider the end mile marker of the farthest jet
stream as the end of the journey.Write a python program that takes in an input file “jetstreams.txt” to
plan out the optimal sequence of jet streams Mo should fly on to
minimize his energy consumption throughout the entire journey. All
integers in the input file are non-negative. As output, print out the
mininum total energy and a list of tuples denoting the jet streams’
endpoints.For example, given the sample jetstreams.txt, the minimum total energy
needed to fly all 24 miles is 352 energy units, and the optimal
sequence of jet streams is [(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
Would this be anything like solving the shortest path of a graph?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的。
您有一条“根本不使用喷射流”的路径，该路径由编号为 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 的“最便宜”路线。
Yes.
You have a "don't use the jetstream at all" path, which consists of vertices numbered 0, 1, 3, 5, 6, 7, 11, 14, 17, 19, 21, 22, 24. The edges which join each of these vertices has a "weight" of 50* the distance - so the 0->1 edge is weighted 50, the 1->3 edge is weighted 100, etc.
Then, you have additional edges representing the jetstreams - one from 0->5 weighted 10, one from 1->3 weighted 5, etc.
Together, these form a directed acyclic graph (a DAG).
Now you have that, you can apply the usual graph traversal techniques to find the "cheapest" route from vertex 0 to vertex 24.
是的，这是一个最短路径问题，用能量代替每条边的长度。构建示例问题的图表时，从 0 到 24 的直线开始，每英里的能量单位成本为 50。然后画出急流边缘及其能量消耗来完成图表。
Yes, this is a shortest path problem, with energy substituted for the length of each edge. When constructing the graph of the sample problem, start out with a straight line from 0 to 24, with a 50 energy unit cost for each mile. Then draw in the jet stream edges and their energy consumption to complete the graph.
这可以很容易地表示为最小加权间隔调度算法。
每个急流都是一个具有权重的间隔，目标是选择使权重最小化的间隔。
请参阅以下链接了解最大加权间隔调度或谷歌以了解更多信息：
对于您的问题，您可以将
max计算替换为min。寻找最佳组合的算法某些约束下的项目
加权间隔调度问题&动态程序
This can be easily expressed as a Minimum weighted interval scheduling algorithm.
Each jetstream is an interval with a weight, and the goal is to choose intervals that minimize the weight.
See the following links for Maximum weighted interval scheduling or google to learn more:
You can replace the
maxcalculations tominfor your problem.Algorithm to find the best combination of items under certain constraints
Weighted Interval Scheduling problem & Dynamic program