Shortest path in a maze

Question

There is a maze, which is nothing but made of $2$ parallel polylines, which looks like a zig-zag road. We have to find the shortest path between the entrance and exit. Any ideas on how to proceed? Does it involve dynamic programming?

The maze can be thought of as follows:

One polyline consists of the set of points: $\{(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\}$.

The other polyline is: $\{(x_0, y_0+h), (x_1, y_1+h), \dots, (x_n, y_n+h)\}$ where $h$ is a constant.

Assume that you start from any point on the segment $\big[(x_0, y_0), (x_0, y_0+h)\big]$ and end on any point on the segment $\big[(x_n, y_n), (x_n, y_n+h)\big]$.

Answer 1

Let $$\ell_0= (x_k,y_k)_{0\leq k\leq N}$$ with $x_0<x_1<\ldots<x_N$ be the lower rim of the corridor, held fixed in the sequel, and drawn in red in the following figure. The upper rim, drawn in blue, is congruent to $\ell_0$, and at time $t=0$ coincides with $\ell_0$. On the red $\ell_0$ mark all $\wedge$-vertices red, and on the blue $\ell_0$ mark all $\vee$-vertices blue. We shall translate the upper rim slowly upwards, such that at time $t$ we have $$\ell_t= (x_k,y_k+t)_{0\leq k\leq N}\quad(0\leq t\leq h)\ .$$

Denote by $\gamma_t$ the shortest path through the corridor at time $t$. When $t>0$ is almost zero then $\gamma_t$ will pass through all marked vertices $V_k$; furthermore $\gamma_0$ has a $\wedge$ at all red vertices and a $\vee$ at all blue vertices. As $t$ is increasing the $\wedge$s as well as the $\vee$s become less outspoken, and some of them even will become straight. When such an event happens $\gamma_t$ will be uncoupled from that vertex $V$, which then falls out of consideration definitively.

This happens as follows: Assume that an "active" vertex $V_k$ has at least one neighbor of the other color. There are several cases to consider, but it will be sufficient to describe the following case: At time $t$ we have a red vertex $V_{k-1}=(x_{k-1}, y_{k-1})$ and blue vertices $V_k=(x_k,y_k+t)$, $V_{k+1}=(x_{k+1},y_{k+1}+t)$. Since $V_k$ is active we have $${y_k+t-y_{k-1}\over x_k-x_{k-1}}<{y_{k+1}-y_k\over x_{k+1}-x_k}\ .\tag{1}$$ When $t$ increases the left side of $(1)$ will increase, and the right hand side will remain constant, since both $V_k$ and $V_{k+1}$ are blue. There will be a certain value $\tau_k>t$ when equality is reached. This value $\tau_k$ is a rational function of the data appearing in $(1)$.

This leads to the following algorithm:

Put $t_0=0$, $\gamma_0=\ell_0$.

Repeat: Assume that $t_n<h$ and $\gamma_n=\gamma_{t_n}$ have been determined, and all vertices $V_k$, red or blue, of $\gamma_n$ are active. Then find $j:=\arg\min_k \tau_k$, put $t_{n+1}:=\tau_j$, and remove $V_j$ from the stack.

Stop when $t_n\geq h$.

Answer 2

There may well be a slick dynamic programming solution, but I don't know it. Here is one approach that looks like it should work, but I don't quite see how to prove termination. The idea is to model threading a string along the road and pulling it tight. In more detail, find any polyline path contained in the road that connects the end points. Now look for a vertex where you can straighten out the path: i.e., if there are consecutive vertices $u$, $v$, and $w$ such that $|\pi - \angle uvw| > 0$ and such that there is a point $v'$ on the angle bisector at $v$ with $uv'w$ still contained in the road and with $|\pi -\angle uv'w| < |\pi - \angle uvw|$, replace $v$ by the $v'$ that meets these requirements and minimises $|\pi - \angle uv'w|$. The edges $uv'$ and $v'w$ may now touch vertices on the side of the road and you need to add these as new vertices on the path. Now repeat the process. Each step decreases the length of the path, so if this is a practical problem, you could just stop when it is no longer possible to reduce the length by some given $\epsilon > 0$. I strongly suspect the process must terminate, but I don't see how to prove that just now.

Answer 3

Create a weighted graph with distances calculated with Pythagoras (or equal to $h$), and solve using Dijkstra's algorithm or similar.