3 ms·

Following your example of city streets this reminds me of an algorithm my friend wrote for walking through a grid city with a slope. Let's say the west corner

Following your example of city streets this reminds me of an algorithm my friend wrote for walking through a grid city with a slope. Let's say the west corner of the lattice is the highest part and the eastern most corner is the lowest part but the gradient is not constant. The city has many local maximums and minimums, where you will walk downhill on one street just to turn towards your destination and be forced to walk up again. His algorithm attempts to minimise the amount of energy he needed to exert to walk from point a to the bar. He said "never walk downhill, unless it's the last hill". In other words when faced with an intersection, take the path with the least slope.

hodgesrm 10y ago
Indeed. This seems similar to my problem. I started thinking about the streetlight problem decades ago in Portland, which has a grid in the city center. The specific question was what if I just always went with the green light to cross the grid? In the streetlight case this clearly leads to bad outcomes if the length of the red light time is unbounded. Your conditions would seem to limit the cost of a bad decision to the number of nodes you cross times the maximum height difference between west and east ends of the grid. However, if you don't somehow limit the number of ups and downs between nodes, then the "take the downhill" algorithm seems to have the same issue as walking through streetlights. All you have to do is assume a large number of ups and downs within a block. In both cases it seems that to bound the "sub-optimality" of solutions there must be a bound on the cost of moving between nodes in the grid.