Imagine you are trying to plan a road trip from some where on the east coast of the United States to the west coast. For this trip you have four family members, each old enough to drive allowing you to drive non-stop (rotating people to sleep). I know for my family it was pretty intense to drive cross-country and the weaklings were shunned if they needed to use the bathroom, so we are going to ignore bathroom breaks.
This intense cross-country trip is accomplished via Minivan, in which you can only travel 270 miles until stopping for gasoline. During this trip you are trying to minimize the number of stops you take to reach your destination as fast as possible. With this in mind you go to a map and find the various gas stations and associated mile markers.
Problem Description
Ideally, you would travel exactly 270 miles before stopping, however this is rather difficult to accomplish. We will keep track of how close we are to the ideal or optimal solution via penalty points. We will calculate these points by adding a penalty for driving under 270 miles using the equation, denoted as <max distance>, implying maximum distance on a single tank of gas:
penalty = (source – destination + <max distance>), x being distance traveled.
The above equation works nicely because the source gas station will always have a lower mile marker than the destination gas station. Meaning, we will always receive a negative value from source – destination. When we then add <max distances> or 270 in this case to to the source – destination we will receive a positive number if it is within our driving range, or a negative it is not. This enables us to recognize gas stations out of range as negative penalties, which we then remove as possible destinations. If on the other hand the penalty value is positive it is within range, and we can determine how optimal the destination is by attempting to minimize the penalty; thereby accomplishing our goal of minimizing the number of gas stops we have to make.
Structuring the Data
The first step in solving this problem is to transform the real world characteristics/information into structured data we can use an algorithm on. In this case we should first layout what we know:
- Penalty equation: (x – 270), x is distance between gas stations
- Location of gas stations: a series of mile markers
- Final destination, denoted by n
For the last bullet point we can simply store an array of mile markers, as so:
mileMarker[0] = 0, mileMarker[1] = 32, …, mileMarker[n] = 3438
Then we can calculate the “Optimal Gas Stop” by using the following equation (pretty much the same as above):
((destinationGasStation – sourceGasStation) – 270)
That’s pretty much it for the mathematics and data structures, it is relatively straight forward for this problem, now the solution!
Solution
Solving mathematical/computation problems often require a fair amount of mathematical notation (go figure). For this case, I will attempt to keep the math simple and clear as possible. Let, optimalGasStop(i) denote the “optimal” or minimally penalizing path/distance (throughout the rest of this article I will call it path) from mileMarker[0] or the initial gas station (the starting location) to gas station “i” (the current location). The “base case” or most simple case, is that we are already at our destination (i.e. we didn’t travel at all), in this case optimalGasStop(0) = 0 penalty points. Then we suppose that our destination is greater than zero, mileMarker[i]. In this case we will assume “j” is the gas station just prior to our current gas station “i,” so j < i. If we then claim that mileMarker[0] to mileMarker[j] is the optimal path from station 0 to j, and mileMarker[j] to mileMarker[i] is the optimal path from j to i, then the we also have the optimal path from the starting location (mileMarker[0]) to the final gas station “i.” It is important to make this observation, because it then allows us to “build” off our current best path to find our next node. Once we have both of the above observations, we can build a recurrence:
After constructing a mathematical approach to solving this problem we can then relatively easily program the solution, so program away (or look below)!
Programming
In order to program the mathematical function above we will need to use two arrays.
- One array will store the previous gas stations in the path, this forms a (kind of) linked list, where every gas station in an array points to the previous gas station. In other words: prev[10] could contain the value 4, which means gas station #4 was the previous stop to gas station #10 and prev[4] is the previous gas station to #4.
- One array will store the penalty points associated with each gas station.
Although this may seem slightly confusing at first, I encourage you to review the code and leave any questions in a comment. Just for kicks I made the distance we were traveling the distance from New York to San Francisco (image courtesy Google Maps). 
However, rather than using actual data on where each gas station is located on various mile markers I decided to “randomly” generate gas stations along that path in varying intervals. The generated gas stations should always be close enough that an optimal path can be found, i.e. there will never be a gas station over 270 miles apart from one another. This of course means you may have different output than myself (if you run the program), but it should still be accurate. You should (almost) always receive a total of 11 stops, which is the minimum that can be achieved given the distance traveled and the max distance of the minivan. If you would like to try running the code yourself feel free to fork it off from my github:
Output:
Stop # 0 at Gas Station # 0 located at mile marker 0
Stop # 1 at Gas Station # 32 located at mile marker 215
Stop # 2 at Gas Station # 59 located at mile marker 441
Stop # 3 at Gas Station # 70 located at mile marker 651
Stop # 4 at Gas Station # 86 located at mile marker 858
Stop # 5 at Gas Station # 92 located at mile marker 1210
Stop # 6 at Gas Station # 115 located at mile marker 1531
Stop # 7 at Gas Station # 155 located at mile marker 1833
Stop # 8 at Gas Station # 168 located at mile marker 2096
Stop # 9 at Gas Station # 215 located at mile marker 2376
Stop #10 at Gas Station # 247 located at mile marker 2646
Stop #11 at Gas Station # 272 located at mile marker 2908
I encourage you to play with the code and have fun with difference destination distances and max distances of the vehicle. With real data this should work as well, I think it would be pretty fun to implement and I may do that sometime (if I ever have time).
Runtime: O(n2) – Because there are n gas stations and which can form a path with n nodes, it takes n * n time to calculate the path with the smallest amount of penalty.
Space: O(n) – We only need enough space for two dynamic arrays which are bound by n, the number of gas stations.
I would like to thank /r/CompSci for providing constructive criticism!
Related Articles
- Everyday Algorithms: Pancake Sorting
- Analytics, Experimentation, and Results of Building a Blog: Month Three
- Multithreading: Introduction to Process Scheduling
- Using SVD to Obtain Regression Lines
- Counting Sort in C
Recommended Reading
- Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein)
- Algorithms (Jeff Erickson)
- Introduction to Theory of Computation (Sipser)
If you do decide to implement this in a real-life road trip, definitely do a blog special about it! Traveling + math = cool!