4 ms·

Counting Lattice Paths

44 points by espeed 10y ago

hodgesrm 10y ago
Ooh! I love these problems. One variation on the lattice problem is to pretend the lattice is actually a set of city streets with stoplights on each corner. Let's say you want to walk the lattice; at each corner you take the route that has the green light or wait. The question I always wondered was--is there an optimal algorithm to cross the city that works for any timing pattern on the lights without knowing the timing pattern for the entire grid? The answer seems emphatically "no". You can prove this simply by having the lights at the corner of the lattice stay red indefinitely (or arbitrarily long period of time, call them "pernicious lights"). In that case any path that ends up on the corner of the lattice will be slower than all other routes. It follows from this that you need more than just knowledge of the local lights. (I believe the proof extends to all nodes by adding more pernicious lights.) Any other fun lattice problems? Edit: For clarity.
- abulletforfree 10y ago
  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.
- repsilat 10y ago
  > city streets with stoplights on each corner. I used to think about this because my commute strongly resembled it. My model was, - Signals alternate in the two major directions, - Lights always last the same amount of time, - No phasing correlations, and - Some assumption about crossing time and signal length I can't remember. Might not matter, probably simplest to model it as "crossing takes no time, one or the other direction is always green." Under those assumptions you want to stay close to the diagonal. If you end up on an edge you'll have to wait at most lights, but if you're on the inside you can always cross in one or the other direction. Sometimes it's worth waiting to cross if it'll keep you closer to the diagonal, but I don't know that I ever say down and worked out when, and how long you should be willing to wait if there are countdown clocks.

44 points by espeed 10y ago

Ooh! I love these problems. One variation on the lattice problem is to pretend the lattice is actually a set of city streets with stoplights on each corner. Let's say you want to walk the lattice; at each corner you take the route that has the green light or wait. The question I always wondered was--is there an optimal algorithm to cross the city that works for any timing pattern on the lights without knowing the timing pattern for the entire grid? The answer seems emphatically "no". You can prove this simply by having the lights at the corner of the lattice stay red indefinitely (or arbitrarily long period of time, call them "pernicious lights"). In that case any path that ends up on the corner of the lattice will be slower than all other routes. It follows from this that you need more than just knowledge of the local lights. (I believe the proof extends to all nodes by adding more pernicious lights.) Any other fun lattice problems? Edit: For clarity.

abulletforfree 10y ago
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.
repsilat 10y ago
> city streets with stoplights on each corner. I used to think about this because my commute strongly resembled it. My model was, - Signals alternate in the two major directions, - Lights always last the same amount of time, - No phasing correlations, and - Some assumption about crossing time and signal length I can't remember. Might not matter, probably simplest to model it as "crossing takes no time, one or the other direction is always green." Under those assumptions you want to stay close to the diagonal. If you end up on an edge you'll have to wait at most lights, but if you're on the inside you can always cross in one or the other direction. Sometimes it's worth waiting to cross if it'll keep you closer to the diagonal, but I don't know that I ever say down and worked out when, and how long you should be willing to wait if there are countdown clocks.