Find the path with the smallest weight from the bunch of possible paths

Question

I need help / homework assignment pointers. I would really appreciate it if someone could point me in the right direction on how to solve this problem :)

Appointment

"An angry bird named Mo takes a long way to take revenge on pigs. To save energy for fighting, the bird will take advantage of the jet streams that reduce its flying energy consumption. Before flying BirdHQ gave the bird an input file in the following format:

• The first line contains only 1 integer, which is the constant energy required to fly 1 mile WITHOUT jet streams.
• Each subsequent line contains 3 integers separated by spaces: the marker of the beginning of the target of the jet stream, the marker of the end of the mile per jet stream and, finally, an integer indicating the total energy needed to fly that jet stream distance.

For example, the line "3 7 12" means that it takes 12 units of energy 4 miles between miles 3 and 7.

Note that the jet streams may overlap, but the bird cannot be on more than one stream stream at a time, and it cannot fly in partial streams.

For simplicity, consider the end-mile marker of the farthest jet as the end of a journey.

Write a python program that takes the input file “jetstreams.txt” to plan the optimal sequence of inkjet streams. Mo should fly to minimize energy consumption throughout the trip. All integers in the input file are non-negative. As an output, print the minimum total energy and a list of tuples representing the jet streams endpoints.

For example, given the sample jetstreams.txt, the minimum total energy needed to fly all 24 miles - 352 units of energy, 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 

Will it be something like solving the shortest path of the chart?

Answer 1

Yes.

You have a "do not use the flow path at all", which consists of vertices with numbers 0, 1, 3, 5, 6, 7, 11, 14, 17, 19, 21, 22, 24. edges that connect to each of these peaks, they have a "weight" of 50 * distances - therefore, edge 0-> 1 is weighted 50, edge 1> 3 is weighted 100, etc.

Then you have additional ribs representing the stream of jets - one of 0-> 5, weighted 10, one of 1-> 3 weighted 5, etc.

Together they form a directed acyclic graph (DAG).

Now that you have it, you can use the usual graph traversal methods to find the “cheapest” route from vertex 0 to vertex 24.

Answer 2

Yes, this is the shortest problem with the energy replaced by the length of each rib. When plotting problems with a sample, start with a straight line from 0 to 24 with a cost of 50 energy units per mile. Then, draw the edges of the jet stream and their energy consumption to complete the graph.

Answer 3

This is easily expressed as an algorithm for planning the minimum weighted interval. Each reactive stream represents an interval with weight, and the goal is to select intervals that minimize weight.

See the following planning links with maximum weighted intervals or google to find out more: You can replace the max calculations with min for your problem.

Algorithm to find the best combination of elements under certain restrictions

Weighted Interval Planning Task and Dynamic Program