¿Cuál es la Secuencia que Maximiza esta Distancia?

Question

Supongamos que tenemos $n$ segmentos de $l_1,...,l_n$ $\mathbb{R}^2$ tal que $|l_i|=i,\ \forall\ i=1,...,n$ donde $|l_i|$ es la longitud de $l_i$. Deje $\alpha_1,...,\alpha_{n-1}$ $n-1$ ángulos tales que $\alpha_i>0$$\sum_{i=1}^{n-1}\alpha_i\leq\frac{\pi}{2}$.

Considere la siguiente operación: (Todos los ángulos se supone que es "izquierda").

1) Coloque $l_{1}$ cualquier lugar en $\mathbb{R}^2$,

2) Coloque $l_{2}$ en cualquiera de los puntos finales de $l_{1}$, haciendo un ángulo de $\alpha_{1}$,

3) Coloque $l_{3}$ en el punto final de la $l_{2}$ no ocupado por $l_{1}$, haciendo un ángulo de $\alpha_{2}$,

...

n-1) Coloque $l_{n-1}$ en el punto final de la $l_{n-2}$ no ocupado por $l_{n-3}$, haciendo un ángulo de $\alpha_{n-2}$,

n) Lugar de $l_{n}$ en el punto final de la $l_{n-1}$ no ocupado por $l_{n-2}$, haciendo un ángulo de $\alpha_{n-1}$.

Ahora considere arbitraria permutaciones tanto de los ángulos $\alpha_i$ y de las longitudes $l_i$. Que el pedido de los ángulos y las longitudes maximiza la distancia entre los dos extremos de la cadena de segmentos?

Edit: El problema en la forma que se dijo en el primer tiempo era demasiado general, por lo tanto he cambiado algunos supuestos.

Answer 1

Por supuesto, una respuesta obvia es probar todas las permutaciones posibles. Yo podría tener algo un poco mejor. Supongamos que usted tiene un orden fijo de los ángulos. No estoy seguro de cómo obtener ese, así que por el momento puede suponer que un bucle exterior se itera sobre todas las posibles combinaciones de estos.

Ahora considere la posibilidad de la unidad de vectores oreinted de acuerdo a la acumulación de ángulo de sumas, es decir, apuntando a las instrucciones de su línea de segmentos haría para una determinada orientación de la primera línea. Cada vector de la unidad de longitud que tiene un componente en $x$ dirección y uno en $y$. Por el momento, suponga que su tarea no es maximizar la distancia entre los extremos, pero en lugar de la $x$ coordenadas del punto final. Entonces es fácil asignar las longitudes de los segmentos: el más grande de la $x$ de la componente correspondiente del vector unitario, la más grande es la longitud que usted desea asignar a ese segmento. Así encontrar el mejor orden de las longitudes significa simplemente ordenando las dos listas, la de uno de sus instrucciones por $x$ coordinar y, a continuación, coinciden con ellos uno a uno.

Ahora supongamos que usted gire el primer segmento de la línea de alrededor positivo (antihorario) dirección. Todos los vectores unitarios se convertirá así. Si su $y$ componente es negativo, entonces su $x$ componente aumentará, mientras que para los positivos $y$ componente de la $x$ componente disminuirá. Así que tómate tu lista de la unidad de vectores ordenados por $x$ coordenadas, y buscar pares de posteriores vectores donde el más pequeño está aumentando, pero el más grande es decreciente. En algún ángulo, los dos se ahev de la misma longitud, y después de ese ángulo, su orden por $x$ de los componentes han cambiado. Además, para algunos ángulo del segmento llegará a $y=0$, después de que su crecimiento en dirección inversa. Así que usted puede calcular un conjunto de posibles ángulos de que algo interesante va a pasar. Tomar la smalled de todos estos números, y actuar en el evento interesante: Si se trataba de un segmento llegando a ser igual en $x$ de coordenadas a otro, entonces usted puede cambiar en la lista ordenada. Si es un segmento de cambiar de dirección, a continuación, puede utilizar la nueva dirección para calcular los próximos eventos interesantes.

De esta manera, usted puede tratar de un conjunto de rotación del ángulo de configuración teniendo en cuenta solamente un número finito de eventos donde las cosas interesantes que suceden. Para cada configuración resultante, usted puede conectar su real longitudes en orden creciente de $x$ componentes, y mira el resultado de la distancia. El óptimo global no podría ser alcanzado en $x$ sentido cuando se considera solo los ángulos interesantes, pero el poco interesante ángulos entre todos comparten las mismas combinaciones, por lo que tomando el real de la distancia euclidiana entre ellos el $y$ coordinar el óptimo será entre las asignaciones que probado.

Esto debería ser más corta que la de intentar todas las permutaciones de ambos ángulos y longitudes. No se si hay una manera mejor. Yo soy no está muy feliz con el rendimiento de mi planteamiento, pero como yo no podía pensar en una mejor solución, sin embargo, y como nadie más ha respondido a esta pregunta tan lejos, tal vez la solución anterior es mejor que ninguno en absoluto.