Después de de una larga compilación de información solucionamos esta inconveniente que presentan muchos los usuarios. Te regalamos la solución y nuestro deseo es servirte de gran apoyo.
Solución:
Doy una solución alternativa sin solucionadores numéricos.
Los cuatro puntos forman un cuadrilátero. Permítanme mostrar primero que la configuración óptima forma un cuadrilátero convexo. Una configuración de cuatro puntos en la que ningún orden de los vértices forma un cuadrángulo convexo es un triángulo con un punto en el interior, vea la imagen a continuación:
Suponga primero que una de las tres diagonales tiene una longitud mayor que $ d $. Sin generalidad de pérdida, suponga que $ CD $ tiene una longitud mayor que $ d $. Al menos uno de los lados $ AC $ y $ BC $ tiene una longitud mayor que $ d $. Si no, los cuatro puntos forman un cuadrilátero convexo. Sin pérdida de generalidad, suponga que $ AC $ tiene una longitud mayor que $ d $. Rotando $ C $ alrededor $ B $ hacia $ A $ reducimos $ AC $ y $ CD $; por tanto, la configuración no es mínima.
Entonces podemos suponer que las tres diagonales tienen una longitud $ d $, entonces estamos en una configuración de tres triángulos isósceles con lados iguales $ d $.
Al menos uno de los lados del triángulo tiene una longitud mayor que $ d $, de lo contrario, una de las diagonales tiene una longitud menor que $ d $. Así que asuma sin pérdida de generalidad que $ AC $ es el más grande de los tres bordes exteriores. Esto significa que el ángulo $ ADC $ Por lo menos $ frac 2 pi 3 $; por eso $ AC $ Por lo menos $ sqrt 3 d $. Si $ AC> sqrt 3 d $, luego $ P> 5d + sqrt 3 d $; lo cual no es mínimo porque ha encontrado una mejor configuración. Si $ AC = sqrt 3 d $, entonces al menos uno de los ángulos $ CDB $ y $ ADB $ es $ geq frac 2 pi 3 $. Entonces al menos un lado de $ BC $ y $ AB $ tiene longitud $ geq sqrt 3 d $. Esto significa que $ P geq 4d + 2 sqrt 3 d> d (5 + sqrt 3) $. Esto prueba que esta configuración no es mínima. Esto muestra que en la configuración mínima los cuatro puntos forman un cuadrilátero convexo.
Ahora demuestro que en la configuración mínima, los cuatro puntos forman un rombo. Si tres lados tienen una longitud $ d $ y un lado tiene una longitud mayor que $ d $, luego podemos acortar este lado mediante una de las siguientes acciones:
- Solo moviéndote $ A $, girando $ A $ alrededor $ B $.
- Solo moviéndote $ D $, girando $ D $ alrededor $ C $.
La primera acción es posible si $ AC $ Es mas grande que $ d $ y la segunda acción es posible si $ BD $ Es mas grande que $ d $. Si ambos $ AC $ y $ BD $ son iguales a $ d $, luego $ AD $ tiene longitud $ d $ así como; por lo tanto, al menos una de estas acciones es posible. El resultado de las acciones es:
- Moviente $ A $: todo permanece igual, excepto $ AC $ y $ AD $ reducir.
- Moviente $ D $: todo permanece igual, excepto $ BD $ y $ AD $ reducir.
Esto significa que esta configuración no puede ser óptima.
Supongamos ahora que tenemos dos lados adyacentes de longitud $ d $ y los otros lados tienen una longitud mayor que $ d $ (vea la imagen a continuación)
Si nos movemos $ A $ sobre $ AC $, mientras arregla los otros puntos, luego $ AC $, $ AB $, y $ AD $ reducir en longitud, mientras que los otros permanecen iguales. Esta acción solo es posible si $ AC $ tiene una longitud mayor que $ d $. Si $ AC $ tiene longitud $ d $, entonces podemos rotar $ B $ alrededor $ C $ hacia la diagonal $ AC $ reduciendo la longitud de $ AB $ y $ BC $. Por lo tanto, en todas las situaciones, esta configuración no puede ser óptima.
Supongamos que ahora tenemos dos lados opuestos de longitud $ d $ y los otros dos lados tienen una longitud mayor que $ d $, vea la imagen a continuación.
Moviendo simultáneamente $ A $ y $ B $ (a la misma velocidad) en una dirección perpendicular a $ CD $, disminuimos tanto las diagonales como los lados $ BC $ y $ AD $. Esta acción solo es posible si ambas diagonales $ AC $ y $ BD $ tener una longitud mayor que $ d $. Si una de las diagonales tiene longitud $ d $ (sin pérdida de generalidad suponga que $ AC $ tiene longitud $ d $), entonces podemos rotar $ B $ alrededor $ A $ hacia $ AC $ para reducir la longitud de $ BC $. Esto demuestra que en todos los casos esta configuración no es la óptima.
Suponga que un lado tiene longitud $ d $ y todos los demás lados tienen una longitud mayor que $ d $, vea la imagen a continuación.
Si una de las diagonales tiene una longitud mayor que $ d $ (asumir sin pérdida de generalidad que $ AC $ tiene una longitud mayor que $ d $), entonces podemos movernos $ A $ sobre $ AC $ hacia $ C $ para reducir las longitudes de $ AC $, $ AB $, y $ AD $. Si ambas diagonales tienen una longitud $ d $, luego $ AB $ tiene una longitud $ leq d $, que es una contradicción. Por tanto, esta situación no puede ser mínima.
Si todos los lados son más grandes que $ d $, entonces al menos en diagonal es mayor que $ d $. Moviendo los puntos externos de esta diagonal hacia adentro obtenemos una mejor configuración; por tanto, no es mínimo.
Por lo tanto, puede asumir que los puntos forman un rombo con longitud de lado $ d $. Toma un ángulo $ alpha $ de este cuadrilátero (los otros son $ pi- alpha $, $ alpha $, y $ pi- alpha $).
La longitud de las diagonales son $ d sqrt 2-2 * cos ( alpha) $ y $ d sqrt 2 + 2 * cos ( alpha) $ (ver por ejemplo wikipedia)
Las diagonales son al menos $ d $ cuando $ – frac 1 2 leq cos ( alpha) leq frac 1 2 $; que es cuando $ frac pi 3 leq alpha leq frac 2 pi 3 $.
Esto significa que para minimizar $ P $, tenemos que minimizar $ sqrt 2-2 * cos ( alpha) + sqrt 2 + 2 * cos ( alpha) $ en el intervalo $ left[fracpi3, frac2pi3right]PS.
La segunda derivada (wrt la variable $ alpha $) de esta función es
$$ frac cos ( alpha) sqrt 2-2 cos ( alpha) – frac cos ( alpha) sqrt 2 + 2 cos ( alpha ) – frac sin ^ 2 ( alpha) (2-2 cos ( alpha)) ^ frac 3 2 – frac sin ^ 2 ( alpha) (2 + 2 cos ( alpha)) ^ frac 3 2, $$
que es negativo en el intervalo $ left[fracpi3, frac2pi3right]PS.
Por tanto, la función de minimizar es cóncava; por tanto, el mínimo se obtiene en el borde del intervalo, es decir, $ alpha = frac pi 3 $ o $ alpha = frac 2 pi 3 $.
Completando uno de esos valores para $ alpha $ obtenemos que el mínimo de $ P $ es igual a
$$ 4d + d sqrt 2-2 cos ( alpha_ min) + d sqrt 2 + 2 cos ( alpha_ min) = d (5 + sqrt 3). $ PS
Permítanme expresar esto como un problema de optimización. Hay al menos dos puntos que están a distancia $ d $ aparte, ya que de lo contrario puedes contraer los puntos y conseguir una mejor solución. Asumamos el punto $ A $ está en las coordenadas $ (0,0) $ y $ B $ Me senté $ (0, d) $. Entonces el desafío es encontrar puntos $ C $ a $ (v, w) $ y $ D $ a $ (x, y) $. He expresado esto como un problema de optimización en formato AMPL para $ d = 1 $:
var v;
var w;
var x;
var y;
minimize total_distance: sqrt(v^2 + w^2) + sqrt(x^2+y^2) + sqrt(v^2+(w-1)^2) + sqrt(x^2+(y-1)^2) + sqrt((v-x)^2+(w-y)^2);
subject to min_dist_AC: sqrt(v^2 + w^2) >= 1;
subject to min_dist_AD: sqrt(x^2+y^2) >= 1;
subject to min_dist_BC: sqrt(v^2+(w-1)^2) >= 1;
subject to min_dist_BD: sqrt(x^2+(y-1)^2) >= 1;
subject to min_dist_CD: sqrt((v-x)^2+(w-y)^2) >= 1;
Luego dejo que el solucionador de optimización global Baron lo resuelva:
*************************************************************
NEOS Server Version 5.0
Disclaimer:
This information is provided without any express or
implied warranty. In particular, there is no warranty
of any kind concerning the fitness of this
information for any particular purpose.
*************************************************************
Job 8432228 has finished.
You are using the solver baron.
Checking ampl.mod for baron_options...
Checking ampl.com for baron_options...
Executing AMPL.
processing data.
processing commands.
Executing on prod-exec-6.neos-server.org
4 variables, all nonlinear
5 constraints, all nonlinear; 12 nonzeros
5 inequality constraints
1 nonlinear objective; 4 nonzeros.
BARON 19.12.7 (2019.12.07): threads=4
BARON 19.12.7 (2019.12.07): 107 iterations, optimal within tolerances.
Objective 5.732032769
v = 0.866025
w = 0.5
x = 0.866026
y = -0.499992
Ésta es exactamente la solución que obtuvo. Desde que Baron encontró la solución óptima a nivel mundial, esta es una prueba de que no puede hacerlo mejor.