¿Cuál es la ruta óptima entre el $2$ puntos fijos alrededor de una obstrucción invisible en la pared?

Question

Todos los días a pie de un punto a a Un punto B, que se $3$ millas de distancia. Hay un $50$% de probabilidad de cada paseo que hay una pared invisible en algún lugar estrictamente entre los dos puntos (nunca en a o B). El muro se extiende $1$ millas en cada dirección perpendicular a la línea de segmento (vía directa) entre a y B, y su posición puede ser en cualquier lugar aleatorio entre los dos puntos. Es decir, puede ser cualquier distancia entre a y B tal como se $0.1$ a millas de distancia de, $1.5$ millas de distancia, $2.9$ km de distancia.... Usted no sabe si la pared o donde está, hasta que entras en ella. Usted debe caminar alrededor de la pared si está presente ya que no hay otro modo de burlar. Asumir la pared es de espesor despreciable, todo el terreno es completamente plano, y la coordenada y en ambos a y B son $0$ (aunque no creo que la ruta óptima va a cambiar mucho si no lo estaban).

Cuál es la estrategia minimiza el promedio esperado a pie la distancia entre a y B? ¿Cómo podemos saber con certeza esta estrategia produce el menor promedio poca distancia a pie?

Para obtener el $100$ puntos de recompensa, me gustaría un argumento convincente de por qué usted siente que su solución es la óptima y no puede ser golpeado. Para aquellos de ustedes el uso de la simulación por ordenador, algo razonablemente cerca óptimo es un candidato para la recompensa. No me importa mucho si alguien te supera por $1$ pie para un $3.6$+ milla media de camino, pero que tendría una forma de comprobar el código para asegurarse de que es de fiar. Buena suerte a todos.

Answer 1

El uso de este, y el hecho de que la menor distancia Euclidiana entre dos puntos es una línea recta, podemos ver que la distancia mínima entre los puntos a y B es. (Nota: que el verde de los segmentos denotar la menor longitud de la a a la pared y la pared a B)

Límite Inferior

$$D_m(L,X)=\sqrt{H(X)+L^2}+\sqrt{H(X)+(3-L)^2}$$

Donde, $H(X)$ es la función escalón unitario y $X$ es $0$ o $1$, con igual probabilidad. Tenga en cuenta que estoy suponiendo que $L$ es una variable aleatoria uniforme en el intervalo de $(0,3)$. El valor esperado de $D_m(L)$ es,

$$E(D_m(L,X))=\frac{1}{6} \cdot \int_0^3 D_m(L,0)+D_m(L,1) \ dL$$ $$(1) \quad \Rightarrow E(D_m(L,X))=\cfrac{\ln \left(\cfrac{\sqrt{10}+3}{\sqrt{10}-3} \right)+6 \cdot (\sqrt{10}+3)}{12}=3.3842...$$

Así, el valor mínimo es (1).

Física Responder

Hace referencia al diagrama anterior, podemos observar que esencialmente no-determinista problema, tiene un muy determinista de propiedad asociados con él. Es decir, después de la pared del encuentro, el resto de la ruta óptima se puede determinar. Sin embargo, la trayectoria óptima antes de la pared encuentro es indeterminado. En otras palabras, sólo podemos saber qué camino debemos he tomado; en realidad no podemos tomar ese camino.

Imaginemos que tenemos algunos óptima estrategia que elige un camino óptimo $f(x)$. Dado que el problema no tiene memoria, la ruta óptima es única. Además, esta propiedad de la memoria, descarta la posibilidad de una estrategia mixta de la solución.

Poner estos hechos, podemos ver que $f(x)$ es determinista para $x \lt L$ y reproducción aleatoria para $x \gt L$. Sin embargo, algunas cosas acerca de la $f(x)$ son conocidos,

$$(a) \quad f(0)=0$$ $$(b) \quad \lim_{x \to L^+} f(x)=1$$ $$(c) \quad f(3)=0$$ $$(d) \quad f(x) \le 1$$

Si ahora consideramos todos los posibles caminos que $p(x)$ que satisfagan las condiciones (a-d) se puede investigar el camino de $p_m(x)$ que minimiza la longitud. La longitud de un camino de $p(x)$ $x=0$ $x=L$está dada por,

$$L_p=\int_0^3 \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx+(1-p(L)) $$

Por inspección, vemos que el lado derecho es minimizado por $p(L)$, evaluado a partir de la izquierda, más cerca de $1$. Sin embargo, esto significa que la pendiente promedio de $p(x)$ por lo tanto tendrá que ser igual a $\cfrac{p(L)}{L}$. Desde la más corta de la curva con una pendiente media igual a la cantidad es una línea, sabemos que $p_m(x)$ debe ser lineal*. Esto significa que podemos obtener una fórmula explícita para$L_p$$\cfrac{dp_m}{dx}=\lambda$. Tenga en cuenta que si una ruta excede los requerimientos de la pared, sólo puede seguir adelante en la misma dirección. No hay conocimiento que a través de un disparo de la pared, hasta el instante antes de que se alcanza el punto B.

Si tomamos el valor esperado de $L_p$ podemos encontrar el valor de $\lambda$ que minimiza la longitud. Este valor de $\lambda$ determina la pendiente de la ruta óptima. Las otras condiciones que determinan $p_m(x)$ e lo $f(x)$. Tenga en cuenta que las ecuaciones resultantes son explícitas, que son demasiado complicados para representar eficazmente aquí. De hecho, yo de hecho ni siquiera resolver la derecha en el primer intento! (Yo todavía no tengo.e física respuesta)

Tengo que $\lambda=0$ resuelve el problema. Esto da una espera de longitud de ruta de

$$E(L_p)=\cfrac{3 \cdot (\sqrt{10}+11)-\ln(\sqrt{10}-3)}{12}=3.6921$$

La intuición:

He aquí por qué el $\lambda=0$ solución debería funcionar. Desde una pared es igual de probable que se presente como para no estar presente, podemos analizar el total de las distancias verticales viajado en ambos casos. En el caso de una pared, la distancia total es de $1-\lambda \cdot L$. En el caso de que sin una pared, la distancia total es de $3 \cdot \lambda$. Por lo tanto el promedio de la distancia vertical recorrida es $1/2+\lambda \cdot (3-L)$. Cual es minimizada por $\lambda=0$.

*Puntos de bonificación si usted se da cuenta de esto sólo lleva a que localmente soluciones óptimas

La Mejor Solución

Al darse cuenta de que el argumento de una ruta lineal, es más bien artificial, vamos a ver qué pasa si se mira de todas las posibles funciones de una manera imparcial. A continuación, la duración media de una ruta arbitraria, $p(x)$, está dada por,

$$F(L,p(x))=\cfrac{1}{2} \cdot \left (\int_0^L \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx+(1-p(L))+\sqrt{1+(3-L)^2} \right)+\cfrac{1}{2} \cdot \int_0^3 \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx$$

La trayectoria esperada de la longitud de $E(F(L))$ es por lo tanto, dado por,

$$E(p(x))=\cfrac{1}{3} \cdot \int_0^3 F(L,p(x)) \ dL$$

Que puede ser resuelto mediante la matemática sujeto conocido como "Cálculo de Variaciones'. Effectivley, este tema se estudia la forma de minimizar/maximizar 'funcionales', esencialmente funciones de funciones. Vamos a utilizar de Euler-Lagrange de la Ecuación. Obtener un segundo orden de la PDE que debe ser satisfecha por un camino óptimo,

$$\cfrac{\partial E}{\partial p}-\cfrac{d}{dL} \left[ \cfrac{\partial E}{\partial p'} \right]=0$$

Tal vez esto es correcto, o me olvidé de algo más profundo principio. De cualquier manera, el uso de este, es fácil comprobar que $p(x)=0.1 \cdot x \cdot (3-x)$ tiene una duración prevista de $3.6504$, lo cual es una clara mejoría. La solución de esta ecuación diferencial es cubierto en otras respuestas.

Answer 2

Creo que tiene una solución plausible. Si seguimos la curva de $y=y(x)$ en una pared día, luego viajamos a una distancia de $\int_0^u\sqrt{1+\left(y^{\prime}(x)\right)^2}dx$ antes de golpear la pared en $u$. Entonces tenemos que ir a $w-y(u)$ ir alrededor de la pared de la mitad de ancho de $w$, y, a continuación, un mayor $\sqrt{w^2+(B-u)^2}$ para llegar a nuestra meta en $x=B$. Suponiendo una distribución uniforme de la pared de las colocaciones $u$, el promedio de la distancia en una pared día es $$\frac1B\int_0^B\left[\int_0^u\sqrt{1+\left(y^{\prime}(x)\right)^2}dx+w-y(u)+\sqrt{w^2+(B-u)^2}\right]du$$ Sin pared día, nuestro promedio de la distancia ininterrumpida de la longitud de la ruta, $$\int_0^B\sqrt{1+\left(y^{\prime}(x)\right)^2}dx=\frac1B\int_0^BB\sqrt{1+\left(y^{\prime}(u)\right)^2}du$$ Ya que la mitad de los días son de pared días, el promedio de la distancia $$\frac1{2B}\int_0^B\left[\int_0^u\sqrt{1+\left(y^{\prime}(x)\right)^2}dx+w-y(u)+\sqrt{w^2+(B-u)^2}+B\sqrt{1+\left(y^{\prime}(u)\right)^2}\right]du$$ Ahora, podemos cambiar el orden de integración de la integral doble para obtener $$\begin{align}\int_0^B\int_0^u\sqrt{1+\left(y^{\prime}(x)\right)^2}dx\,du&=\int_0^B\sqrt{1+\left(y^{\prime}(x)\right)^2}\int_x^Bdu\,dx\\ &=\int_0^B(B-x)\sqrt{1+\left(y^{\prime}(x)\right)^2}dx\end{align}$$ Así que ahora nuestra distancia promedio lee $$\bar s=\frac1{2B}\int_0^B\left[(2B-x)\sqrt{1+\left(y^{\prime}(x)\right)^2}dx+w-y(x)+\sqrt{w^2+(B-x)^2}\right]dx$$ Ahora queremos variar la solución óptima con un pequeño ajuste, $\delta y$. La expansión de esa primera raíz cuadrada de pequeño $\delta y$, $$\sqrt{1+\left(y^{\prime}+\delta y^{\prime}\right)^2}\approx\sqrt{1+\left(y^{\prime}\right)^2+2y^{\prime}\delta y^{\prime}}\approx\sqrt{1+\left(y^{\prime}\right)^2}+\frac{y^{\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}\delta y^{\prime}$$ La integración por partes, $$\begin{align}\int_0^B(2B-x)\frac{y^{\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}\delta y^{\prime}dx&=\left.(2B-x)\frac{y^{\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}\delta y\right|_0^B-\\ &\int_0^B\delta y\left\{-\frac{y^{\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}+(2B-x)\frac{y^{\prime\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}-(2B-x)\frac{\left(y^{\prime}\right)^2y^{\prime\prime}}{\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}\right\}dx\\ &=\int_0^B\delta y\cdot\frac{y^{\prime}+\left(y^{\prime}\right)^3-(2B-x)y^{\prime\prime}}{\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}dx\end{align}$$ El integrado plazo por encima de las gotas fuera porque se supone que $\delta y(0)=\delta y(B)=0$ por Lo que la combinación con el $-\delta y$ de las grandes integral, tenemos la condición $$\int_0^B\left[\delta y\cdot\frac{y^{\prime}+\left(y^{\prime}\right)^3-(2B-x)y^{\prime\prime}}{\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}-\delta y\right]dx=0$$ para arbitrario pequeños ajustes $\delta y$ de lo que se deduce que $$\frac{y^{\prime}+\left(y^{\prime}\right)^3-(2B-x)y^{\prime\prime}}{\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}-1=0$$ Esta es una de las variables separables ecuaciones diferenciales para $y^{\prime}$ y vamos a escribir como $$\frac{dx}{2B-x}=\frac{dy^{\prime}}{y^{\prime}\left(1+\left(y^{\prime}\right)^2\right)-\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}$$ Dejando $y^{\prime}=\sinh\theta$, tenemos $$\frac{dx}{2B-x}=-\left(\frac{\sinh\theta}{\cosh\theta}+1\right)d\theta$$ Y tenemos una integral: $$-\ln(2B-x)=-\ln(\cosh\theta)-\theta-C_1$$ $$2B-x=C\sqrt{1+\left(y^{\prime}\right)^2}\left(y^{\prime}+\sqrt{1+\left(y^{\prime}\right)^2}\right)$$ Podemos establecer el valor de $C$ mediante la aplicación de las condiciones iniciales de $y^{\prime}(0)$, por lo que tenemos una relación entre el$y^{\prime}$$x$: $$f(y^{\prime})=\sqrt{1+\left(y^{\prime}\right)^2}\left(y^{\prime}+\sqrt{1+\left(y^{\prime}\right)^2}\right)-\frac{2B-x}C=0$$ Podemos diferenciar esto para configurar el método de Newton para la resolución de $y^{\prime}$$x$: $$f^{\prime}\left(y^{\prime}\right)=\frac{\left(y^{\prime}+\sqrt{1+\left(y^{\prime}\right)^2}\right)^2}{\sqrt{1+\left(y^{\prime}\right)^2}}+\frac1C$$ Entonces podemos resolver la ecuación diferencial, seguimiento de la longitud extra $$v^{\prime}(x)=\frac1{2B}\left[(2B-x)\sqrt{1+\left(y^{\prime}\right)^2}-y\right]$$ que no fueron tomadas en cuenta por la integración de los 'constante' términos $$\frac1{2B}\int_0^B\left(w+\sqrt{w^2+(B-x)^2}\right)dx=\frac14\sqrt{B^2+w^2}+\frac{w^2}{4B}\ln\left(\frac{B+\sqrt{B^2+w^2}}w\right)+\frac w2$$ A continuación, hacemos un lío con que la pendiente inicial $y^{\prime}(0)$ hasta nuestra trayectoria, llega a $(B,0)$ y tenemos una solución. La derivada de la función:

% f.m

function yprime = f(t,y);

global B C y0p

yp = y0p;
v = y(2);
x = t;
err = 1;
tol = 1.0e-6;

while abs(err) > tol,
    g = sqrt(1+yp^2)*(yp+sqrt(1+yp^2))-(2*B-x)/C;
    gp = (yp+sqrt(1+yp^2))^2/sqrt(1+yp^2)+1/C;
    err = g/gp;
    yp = yp-err;
end
y0p = yp;

yprime = [yp; ((2*B-x)*sqrt(1+yp^2)-y(1))/(2*B); sqrt(1+yp^2)];

El programa:

% Wall.m

global B C y0p

B = 3;
y0p = 0.29190595656;
C = 2*B/(sqrt(1+y0p^2)*(y0p+sqrt(1+y0p^2)));
w = 1;
y0 = [0 0 0];

xspan = [0 B];
options = odeset('AbsTol',1.0e-12);
[t,y] = ode45(@f,xspan,y0,options);
plot(t,y(:,1));
xlabel('x');
ylabel('y');
format long;
err = y(end,1)
meanlen = y(end,2)+1/4*sqrt(B^2+w^2)+w^2/(4*B)*log((B+sqrt(B^2+w^2))/w)+w/2
minlen = y(end,3)
format;

La trayectoria:

El resultado final para la pendiente inicial se $y^{\prime}(0)=0.29190595656$ y la longitud óptima se $3.648267344782407$. Sin pared día, la longitud del camino se $3.065013635851723$.

Answer 3

Deje $l$ ser la longitud $AB$ ($3$ km), $h$ el tamaño de la pared ($1$ milla), $p$ la probabilidad de que la pared aparece $(1/2)$

Supongamos que nuestra estrategia es caminar a lo largo de la curva de $y = f(x)$ donde $f(0) = f(l) = 0, 0 \le f(x) \le h$ $x \in [0 ; l]$ hasta que llegamos a la pared y, a continuación, vaya a su alrededor, a continuación, hacer un camino recto a $B$.

Llame a $g(x)$ de la longitud de la curva de $(t,f(t))$$t \in [0;x]$.

La duración prevista del viaje, entonces es :

$E(f) = (1-p)g(l) + \frac pl \int_0^l (g(x)+(h-f(x))+\sqrt{(l-x)^2+h^2}) dx$.

Minimizar $E(f)$ es equivalente a minimizar $(1-p)g(l) + \frac pl \int_0^l (g(x)-f(x)) dx$, la cual es una combinación del total de la longitud de curva, la curva media de longitud, y el área bajo $f$.

Supongamos que modificar $f$ localmente cerca de un punto de $x$, lo que significa un aumento en la longitud de $dg$ y el aumento en el área de $da$.

Esto modifica $E(f)$$(1-p)dg + p/l((l-x)dg - da) = (1-px/l)dg - (p/l)da$, por lo que mejoramos $f$ al $dg/da < p/(l-px)$ al $da,dp > 0$ e al $dg/da > p/(l-px)$ al $da,dp < 0$.

Esto muestra que si alguna vez tenemos un convexo parte en nuestra curva, que realmente sólo debe cortar en línea recta a través de ella ya que esta modificación ha $dg/da < 0 (< p/(l-px))$. Por lo tanto, el óptimo $f$ es cóncava.

El umbral en $dg/da$ se traduce directamente en la curvatura en el que no podemos mejorar nuestra puntuación más por el cambio de la curvatura. Al hacer un cambio infinitesimal de la curvatura de un arco o radius $r$, se obtiene una eficiencia $dg/da = \kappa = 1/r$ (esto es una reafirmación de la isoperimétrico teorema)

Si la curvatura no variar este sería exacto, pero este método sólo produce una simple aproximación mediante la búsqueda de la curva de $(0,0)$ $(l,0)$donde $\kappa = p/(l-px)$. la curvatura es una función creciente de $x$, obtenemos $r = l/p = 2l$ al inicio, abajo a $r = l(1-p)/p = l$ en el otro extremo.

Curiosamente, parece que la solución no se preocupan por lo $h$ realmente es hasta que cruza la línea de $y=h$

---

En nuestro caso, a partir de a $y=0$ con una pendiente de alrededor de $y'=0.3236$ y, a continuación, resolver numéricamente la ecuación diferencial

$y'' = \kappa(x) (1 + y'^2)^\frac 32= \frac{1}{6-x} (1 + y'^2)^\frac 32$

obtenemos una curva de longitud acerca de $3.0621$ km, y se espera una duración de viaje de alrededor de $3.648$ millas

Aquí es lo que la curva parece que con las dos osculating círculos en los extremos.

Answer 4

Supongamos que usted camina en línea recta y seguir la pared si se encuentra con la pared. Vamos a llamar a $x$ la distancia entre el centro de la pared y el punto donde se iba a interceptar la pared, si es que lo hubo.

Si no hay pared, la distancia del recorrido se $2\sqrt{x^2+1.5^2}$ Si hay una pared, la distancia del recorrido se $\sqrt{x^2+1.5^2}+1-x+\sqrt{1+1.5^2}$ (supongamos $x>0$)

Por lo tanto, espera que la distancia de recorrido es

$$f(x) = \sqrt{x^2+1.5^2}+ \frac{ \sqrt{x^2+1.5^2}+1-|x|+\sqrt{1+1.5^2} }{2}$$

Un estudio rápido de esta función le da un mínimo en $x = \frac{3}{4\sqrt{2}} \simeq 0.53 \text{miles}$

Answer 5

Bien, me había dado esta respuesta última noche en el post de aquí, que a escala de todo por un factor de 3: Ruta óptima alrededor de un muro invisible

Para ahorrar tiempo, voy a copiar y pegar mi respuesta aquí, y asumirá la longitud de AB es 1 y la longitud del muro es de 1/3 en cada dirección. Usted puede multiplicar todo por un factor de 3 más adelante.

---

[Voy a cambiar mi $y$-discretización para hacerla más fina, en respuesta a otro Michael comentario más abajo.]

Un enfoque es a través de la programación dinámica (que trabaja en la solución hacia atrás). Por simplicidad, vamos a picar la $x$-eje en $n$ segmentos de tamaño de $\delta_x = 1/n$, y supongamos que la pared está en una de estas picar puntos (incluyendo el punto 0, pero no el punto 1). Picar la $y$-eje en $m$ segmentos de longitud $\delta_y = (1/3)/m$. Definir el valor de la función $J(x,y)$ cuando el resto de la distancia de viaje al destino en virtud de la política óptima, dado que estamos a una distancia horizontal $x$, una distancia vertical $y$, y ninguno de nuestros anteriores se mueve encontró con una pared. El $J(x,y)$ función está definida sobre: $$ x \in \mathcal{X} = \{0, \delta_x, 2\delta_x, ..., 1\} \quad , \quad y \in \mathcal{Y}=\{0, \delta_y, 2\delta_y, ..., 1/3\}$$

Supongamos que empezamos a $(x_0,y_0)=(0,0)$. Trabajando hacia atrás, y suponiendo que no hay pared en $x=1$, obtenemos:

$$J(1,y) = y \quad \forall y \in \mathcal{Y} $$

Ahora suponga $J(k\delta_x, y)$ es conocido por todos los $y$ y, para algunos,$k$. Entonces:

\begin{align} J((k-1)\delta_x, y) &= P[\mbox{wall is here | have not yet seen it}]\left[1/3-y + \sqrt{1/9+ (1-(k-1)\delta_x)^2}\right]\\ &+P[\mbox{wall is not here | have not yet seen it}]\min_{v\in\mathcal{Y}}\left[J(k\delta_x,v)+\sqrt{\delta_x^2 +(y-v)^2} \right] \end{align} Ya hemos discretizado el problema, si la pared existe, se encuentra uniformemente a lo largo de uno de los la $n$$\{0, \delta_x, ..., (n-1)\delta_x\}$. Por lo tanto, si estamos en la ubicación de $(k-1)\delta_x$ y aún no hemos visto una pared en cualquiera de las localizaciones $\{0, \delta_x, ..., (k-2)\delta_x\}$, obtenemos: $$ P[\mbox{Wall here | not before}]=\frac{\frac{1}{2n} }{\frac{1}{2}+\frac{1}{2}\left(\frac{n-(k-1)}{n}\right)} $$

---

Nota: escribí un programa en C para implementar la anterior. El uso de $m=n$ restringe la pendiente opciones y conduce a trapecio-trayectorias. Que me llevó a incorrectamente conjetura de que los trapecios eran óptimas. El uso de un fino pendiente opción (como se sugiere por otro Michael en un comentario más abajo), como $m=100n$, da trayectorias curvas que parece coherente con los dos más recientes respuestas que se ven en la optimización de toda la trayectoria a través de análisis variacional. Aquí está una optimización sobre el (óptimo) trapecio funciones y por el continuo versión del problema: Vamos a $f(x)$ ser la altura como una función de la $x$, siendo la trayectoria a seguir hasta chocar contra la pared (si alguna vez lo hacen). Así que empezamos a $f(0)=0$. Una clase de funciones es: $$ f(x) = \left\{ \begin{array}{ll} x/3 &\mbox{ if %#%#%} \\ \theta/3 & \mbox{ if %#%#%}\\ -(x-1)/3 & \mbox{ if %#%#%} \end{array} \right.$$

El mejor $x \in [0, \theta]$ más de esta clase da un promedio mínimo de distancia de:
\begin{align} dist^* &= -7 + 5\sqrt{\frac{5}{2}} + \frac{1}{2}\int_{0}^1 \sqrt{1/9 + x^2}dx \approx 1.21973\\ 3dist^* &\approx 3.6592 \end{align} Esto se logra por $x \in [\theta, 1-\theta]$. Esto es estrictamente mejor que la ingenuidad política de ir recto hasta que te encuentras con una pared, lo que demuestra la ingenuidad política es subóptima.