I told my dad I thought about this problem often. He incredulously replied “Often?” I said “At least once a day.” I usually say I should ask the Dope, but then I don’t. So here goes, finally:
You’re a pedestrian who just parked their car, and now you’re walking to the exit, which is across the lot, though several rows of cars. A direct path is impossible, because there are many cars in the way. So unless you’re Antman, you have to walk around the parked cars. What’s the best strategy to ensure you take the shortest legal route?
Here are the rules:
No cars are driving around, so when you’re in the travel lanes, you can walk freely in any direction.
There are rows of cars parked head-to-head, and these rows are parallel to each other, but diagonal with reference to the you->exit line.
All spots are filled, so there aren’t any gaps in parking spots (or else you would’ve parked there instead!), but you can walk on the paint between any two cars. This counts side-by-side cars and head-to-head cars. That’s how you legally traverse a row.
Having thought about this problem twice a day (9:00 am and 5:00 pm) on almost every Monday-Friday for several years, I have a good idea of what I think the optimal solving algorithm is, but I want to hear your ideas before I tell you mine.
So how does a pedestrian determine the optimal (shortest) walking path? Is the problem setup clear enough?
Down one row until you can’t, then over to the exit. Seems simple enough. If your only paths are perpendicular te each other like a grid, the total disatnce will be the same regadless of how many times you zig and zag. Though if you minimize the zig zagging like in my solution, then you don’t waste time turning and trying to dodge door mirrors and what not.
I think the key is spending as much time in the lanes where you can move diagonally. Any path that maximizes that will be optimal. In order to do so, you should divide the number of rows of cars by the number of lanes to cross, and as you come out from between a row of cars, roughly make a diagonal move that goes across that number of rows of cars before heading across that row. I do this at Costco non-optimally, but that’s generally because the assumption that you can move freely in the travel lanes is not a good one.
Agreeing with snfaulkner: the distance will be the same no matter what route you take, since your assumptions force the problem into a grid format. I also agree that zig-zagging through the lot would certainly take more time, since every time you turn, you slow down, plus you’re dodging the mirrors, doors etc. ( My GPS algorithm uses “fewest turns” as one variable in calculating the “fastest route”)
Since you assume there are no moving cars travelling in the “columns”, depending on your initial assumption of where exactly you park and where exactly the exit is, you would decrease the distance slightly by cutting diagonally down the column you parked at and then diagonally across the row to the exit. Going from A to B to C in my crude diagram. But it really depends on the exact position of your car and the exit in your assumptions. Hopefully I understand your scenario.
= car
A= your car
B = bottom of column you parked in
C= Exit (at lower side of bottom row)
I agree with glowacks. If the paths forced you to travel exactly perpendicular then all paths would be equal length as long as you didn’t turn away from the direction of the exit, but the paths don’t force you to travel exactly perpendicular, they allow for slight diagonals. The shortest path will be the one that is the most diagonal overall.
Note that the OP specified “shortest” route, not the quickest, so slowing down for corners shouldn’t be a factor (not that I slow down for corners at walking pace anyway.)
I had independently reached the same conclusion as glowacks. However, my issue is that you can’t always find a place to walk between cars, so I aim exactly toward my destination if there are no cars driving in my lane, knowing that that is not an optimal angle, but it is easy to calculate and I will often have to move several rows before finding a place I can move between cars without slowing down too much.
For concreteness, let’s imagine that all the aisles in the parking lot run north-south, and suppose that we’re trying to get from the southeast to the northwest corner. The angle at which you cross the aisles is the only real choice you have in the problem.
Imagine all of the cars shoved over to one side of the lot (the east side, say), like a valet parking lot. All the “aisle space” is then consolidated on the west side. It should be pretty evident that in this case, the quickest route between the southeast and northwest corner involves walking due west along the edge of the lot, and then walking diagonally across the “consolidated” aisle along its main diagonal. This main diagonal has a particular angle.
I’m pretty sure that the shortest path between the corners of the “normal” parking lot involves crossing the aisles at this same angle, or as close as possible to it. The length of this path would be pretty close to (if not the same as) the path across the “valet lot” mentioned above; you could imagine cutting and pasting the segments of your “valet lot” path (without rotating them) into a path through the normal parking lot. And if you crossed the aisles of the normal parking lot at different angles, or walked along the middle of the rows of cars (rather than across & through them), then you could take this path, cut-and-paste it, and make it into a path in the “valet lot”. But we know that this path would be longer than the optimal path in the valet lot, and so there would exist a shorter path in the normal lot as well.
ETA: I believe this results in the same path laid out by Ludovic and glowacks.
Your problem is an application of Taxicab Geometry, first considered by Hermann Minkowski in the 19th century. Dover published a slim but interesting volume on it:
Indeed, I was going to lay out the same thought experiment where all the cars are together, and all the empty lanes are together. Must be an example of great minds thinking alike!
Just to jump in any savings will be due to the non-uniformity of the situation, not the uniformity which equates the distance. Use empty spots to short cut a bit, if there is no traffic cut across the travel lane and get those done, for when you get to the exit their may be traffic causing a delay in crossing, other pedestrians or obstacles etc.
I use a different calculus altogether. Let us assume the parking lot is at capacity or near to it; otherwise there are not so many cars to walk around.
When I’m walking to my car, my thought is with those who are looking for parking spaces. I try to walk only in the lane my car is parked in so I don’t get others following me thinking they will take my space. Zig zagging would just cause frustration on other drivers part.
When I am leaving my car and going to the shops I try to walk down my lane as far as possible then into the shop. My goal is to be obviously not leaving if that makes sense.
This sounds clear in my head but I’m taking a lot of Vicodin so ymmv
The OP’s problem allows diagonals! These diagonals allow noticeable shortening of the path.
First approximation: Walk across a lane straight at your parking spot until you reach a parked car. Go between that car to the next lane. Repeat.
This might create a bias where you are consistently walking to the left (for example) of the straightline path to you car when walking between cars.
Second approximation. Figure the current straightline path to your car. Picture where it is crossing the paint between the bumpers of the next double row of cars. Walk to the side of those pair of cars. Which side? Whichever side is closest to that crossing point.
(I.e., you are trying to “hug” the current straightline path.)
Once past that pair of cars, repeat the above.
It might be possible to do slightly better recursively rather than iteratively. I.e., set an initial target crossing the middle row of cars between you and your car. Then recursively figure the best path to that point. Stop the recursion at one intervening row. Use the above method to choose the path thru that row. Back out of the recursion one layer and onto the next.
Anyone who mistakenly believes I’m trying to leave the facility while I’m obviously walking toward the facility deserves every bit of self-inflicted frustration they incur. OP’s story is explicit that you’ve just parked the car and are walking toward the store or whatever. Since we’re talking about optimized strategies, any solution that requires backtracking is right out, and backtracking would be the only move that a rational driver would mistake for someone preparing to release a parking spot.
Just to clarify, you’re walking from the upper-left to the lower-right in the diagram below. I agree with those who say to maximize your diagonalization; i.e. your path will touch each asterisk.
There’s a large parking lot I frequently cross; I do tend to diagonalize it subconsicously in this fashion. (But that lot has other issues: often there won’t be room to pass between cars.)
There’s also the problem of locating your car again, once you come out of the store. I often find it ‘optimal’ to walk straight to the end of the row, then over to the door. Thus I know that may car was 'in ‘the 4th row over’ from the door. (Stores that make you exit on a different side from the entrance are a pain for this. I avoid shopping at them if there is a competitor nearby.)
This is guaranteed not to work. When you hit a row of cars, you’re forced off-course. Then you have to spent time getting back on course, when you could’ve used the earlier space to prepare for this eventuality.
This is exactly the conclusion I’ve come to. Instead of shifting all the cars to a “valet lot”, I use a “wormhole” idea, where any time spent in the row doesn’t count at all. Pathwise, I pop in one side of the cars and pop out at its corresponding exist point. Thus my entry angle should match my exit angle, and if it doesn’t, then I’ve misjudged the angle and need to adjust in the next aisle.
I just pretend that the pavement is folded up, like a paper airplane’s center, such that the left and right points on an aisle are joined together. The middle “spine line” is the opposite fold. Then I trace a line w/ an imaginary pen to the exit. Then I unfold the mental paper and walk the traced path.
Perhaps it’s your drawing, but I don’t see how I can touch all the asterisks and still be on the optimal path. Are those supposed to be on the left side of the aisle, or the center? Are they evenly spaced?
This raises an interesting bonus question: If the optimal path traverses all the aisles at an equal angle, there must be points where it crosses an empty lot’s optimal path…i.e., a straight line path without obstruction. Must these intersection points be in the midline of each aisle?
That is, does the best-path-with-cars intersect the best-path-without-cars at the center (midline) of aisles?
If you enjoyed this problem, later, I will present the “CS walks across campus, choosing crosswalks” problem from my college days.
