3 votos

El camino más corto en un laberinto

Hay un laberinto, que no está hecho más que de $2$ polilíneas paralelas, que parece un camino en zig-zag. Tenemos que encontrar el camino más corto entre la entrada y la salida. ¿Alguna idea sobre cómo proceder? ¿Implica la programación dinámica?

El laberinto puede pensarse de la siguiente manera:

Una polilínea está formada por el conjunto de puntos: $\{(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\}$ .

La otra polilínea es: $\{(x_0, y_0+h), (x_1, y_1+h), \dots, (x_n, y_n+h)\}$ donde $h$ es una constante.

Supongamos que se parte de cualquier punto del segmento $\big[(x_0, y_0), (x_0, y_0+h)\big]$ y terminan en cualquier punto del segmento $\big[(x_n, y_n), (x_n, y_n+h)\big]$ .

2voto

CodingBytes Puntos 102

Dejemos que $$\ell_0= (x_k,y_k)_{0\leq k\leq N}$$ avec $x_0<x_1<\ldots<x_N$ sea el borde inferior del corredor, mantenido fijo en la secuela, y dibujado en rojo en la siguiente figura. El borde superior, dibujado en azul, es congruente con $\ell_0$ y en el momento $t=0$ coincide con $\ell_0$ . En la red $\ell_0$ marcar todo $\wedge$ -Versos rojos, y en el azul $\ell_0$ marcar todo $\vee$ -Vertederos azules. Trasladaremos el borde superior lentamente hacia arriba, de forma que en el momento $t$ tenemos $$\ell_t= (x_k,y_k+t)_{0\leq k\leq N}\quad(0\leq t\leq h)\ .$$

enter image description here

Denota por $\gamma_t$ el camino más corto a través del corredor en el momento $t$ . Cuando $t>0$ es casi cero, entonces $\gamma_t$ pasará por todos los vértices marcados $V_k$ Además $\gamma_0$ tiene un $\wedge$ en todos los vértices rojos y un $\vee$ en todos los vértices azules. Como $t$ está aumentando la $\wedge$ s así como el $\vee$ s se vuelven menos francos, y algunos de ellos incluso se volverán heterosexuales. Cuando se produce un acontecimiento de este tipo $\gamma_t$ se desacoplará de ese vértice $V$ que entonces queda definitivamente fuera de consideración.

Esto ocurre de la siguiente manera: Supongamos que un vértice "activo" $V_k$ tiene al menos un vecino del otro color. Hay varios casos a considerar, pero será suficiente con describir el siguiente caso: En el momento $t$ tenemos un vértice rojo $V_{k-1}=(x_{k-1}, y_{k-1})$ y vértices azules $V_k=(x_k,y_k+t)$ , $V_{k+1}=(x_{k+1},y_{k+1}+t)$ . Desde $V_k$ está activo tenemos $${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}$$ Cuando $t$ aumenta el lado izquierdo de $(1)$ aumentará, y el lado derecho permanecerá constante, ya que ambos $V_k$ y $V_{k+1}$ son azules. Habrá un cierto valor $\tau_k>t$ cuando se alcanza la igualdad. Este valor $\tau_k$ es una función racional de los datos que aparecen en $(1)$ .

Esto nos lleva al siguiente algoritmo:

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

Repito: Supongamos que $t_n<h$ y $\gamma_n=\gamma_{t_n}$ se han determinado, y todos los vértices $V_k$ , rojo o azul, de $\gamma_n$ están activos. A continuación, busque $j:=\arg\min_k \tau_k$ , poned $t_{n+1}:=\tau_j$ y eliminar $V_j$ de la pila.

Deténgase cuando $t_n\geq h$ .

1voto

mrseaman Puntos 161

Es posible que haya una solución de programación dinámica muy hábil, pero no la conozco. Aquí hay un enfoque que parece que debería funcionar, pero no veo muy bien cómo probar la terminación. La idea es modelar un hilo a lo largo de la carretera y tirar de él. En más detalle, encontrar cualquier camino polilínea contenida en la carretera que conecta los puntos finales. Ahora busca un vértice donde puedas enderezar el camino: es decir, si hay vértices consecutivos $u$ , $v$ y $w$ tal que $|\pi - \angle uvw| > 0$ y tal que hay un punto $v'$ en la bisectriz del ángulo en $v$ avec $uv'w$ todavía contenida en la carretera y con $|\pi -\angle uv'w| < |\pi - \angle uvw|$ , reemplazar $v$ por el $v'$ que cumpla con estos requisitos y minimice $|\pi - \angle uv'w|$ . Los bordes $uv'$ y $v'w$ ahora puede tocar vértices en el lado de la carretera y hay que añadirlos como nuevos vértices en el camino. Ahora repite el proceso. Cada paso disminuye la longitud del camino, por lo que si se trata de un problema práctico, se podría parar cuando ya no sea posible reducir la longitud en un determinado $\epsilon > 0$ . Tengo la firme sospecha de que el proceso debe terminar, pero no veo cómo demostrarlo ahora.

0voto

Dr Xorile Puntos 832

Crear un gráfico ponderado con distancias calculadas con Pitágoras (o igual a $h$ ), y resolver mediante el algoritmo de Dijkstra o similar.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X