Dado: $(X,Y)$ es distribuido Uniformemente sobre un disco de radio de la unidad. A continuación, la distribución conjunta de $n$ puntos $((X_1,Y_1), ..., (X_n,Y_n))$, cada uno elegido de forma independiente, conjunta pdf:
$$f( (x_1,y_1), ..., (x_n,y_n) ) = \begin{casos}\pi^{-n}& (x_1^2 + y_1^2 < 1) & \text {y } \cdots \text {y }&(x_n^2 + y_n^2 < 1) \\ 0 & lo contrario \end{casos}$$
A continuación, vamos a $Z_n$ denotar la longitud Euclidiana de la menor poligonal ruta que visita cada punto de (al menos) una vez. Para cualquier $n$, es posible expresar $Z_n$ como una simbólica exacta construir. Lo que rápidamente se cansan de hacer manualmente, así que he creado una función PolygonPathMinDistance[points] a automatizar mismo (me han facilitado el código en la parte inferior de este post). Por ejemplo:
- Caso $n = 2$:
Con 2 puntos, el menor, de planta poligonal, la ruta $Z_2$ es, por supuesto, ... :
![]()
y así la deseada solución exacta es:
$$E[Z_2] = E\left[\sqrt{\left(X_1-X_2\right){}^2+\left(Y_1-Y_2\right){}^2}\right] \aprox 0.9054$$
donde las variables aleatorias $(X_1, Y_1, X_2, Y_2)$ conjunta pdf $f(\cdots)$ dado anteriormente.
A pesar de conseguir una solución de forma cerrada para la expectativa integral hasta ahora ha resultado difícil (tal vez la transformación a coordenadas polares podría ser una ruta que vale la pena perseguir - ver más abajo), el resultado es sólo un número, y se puede encontrar que el número de precisión arbitraria usando integración numérica en lugar de integración simbólica. Al hacerlo, produce el resultado de que: $E[Z_2] = 0.9054 ...$.
- Caso $n = 3$:
Con 3 puntos, y el más corto poligonal ruta $Z_3$ es:
![]()
y del mismo modo obtener:
$$E[Z_3] \aprox 1.49 ...$$
- Caso $n = 4$:
Con 4 puntos, y el más corto poligonal ruta $Z_4$ es:
![]()
y del mismo modo obtener:
$$E[Z_4] \aprox 1.96 ...$$
... y así sucesivamente. Para los casos por encima de los $n \ge 5$, el método funciona bien, pero la integración numérica se vuelve menos fiable, y otros métodos, tales como la simulación de Monte Carlo [es decir, en realidad, generando $n$ pseudoaleatoria puntos en el disco (es decir 100.000 veces), la evaluación de la actual ruta más corta para cada uno y cada una de las $$n-dimensional de dibujo, y el cálculo de la media de la muestra] parecen funcionar de manera más confiable. El último es, por supuesto, ya no es exactamente una metodología conceptual, sino como un práctico método de evaluación, para la mayor de $n$, parece ser la opción más práctica.
Resumen de las Parcelas y el Montaje
$$\color{red}{\text{Espera más corta polígono ruta de conexión de $n$ puntos al azar en un disco de radio de la unidad }}$$
![]()
... y con $n=50, 100$ y $150$ los puntos agregados:
![]()
El modelo ajustado es:
$$a + b \frac{n-1}{\sqrt{n}}$$
con $a = -0.11$, $b = 1.388$.
Ajuste de curvas
Un número de 'natural' contendientes se presentan, incluyendo los modelos de la forma:
$a + b n + c \sqrt{n}$ ... esto se realiza perfectamente en la muestra, pero tan pronto como uno se extiende a valores mayores de $n$, el modelo se comporta mal de la muestra, y necesita ser re-equipado dado los puntos de datos adicionales. Esto sugiere que el modelo verdadero no es simplemente la raíz cuadrada de $n$.
$a + b n^c$ ... esto funciona muy cuidadosamente dentro de la muestra, y fuera de muestra, pero el parámetro óptimo de valores muestran una cierta inestabilidad a medida que más los valores de los datos se agregan.
$a + b \frac{n-1}{\sqrt{n}}$ ... a sólo 2 parámetros, y funciona maravillosamente. La idea de este modelo fue inspirado por Ju x publicación. Los valores de los parámetros son muy estables a medida que más se agregan puntos de datos (que se mantienen constantes hasta 2 decimales, independientemente de si usamos sólo $n = 2 ... 20$, o $n = 50$ se añade, o $n=100$ se añade, todo el camino hasta $n = 300$), como se muestra aquí:
![]()
Los valores de los parámetros de $a$ y $b$ son los mismos que para el diagrama de arriba.
Código para el PolygonPathMinDistance función
He aquí algunos de Mathematica código para el exacto PolygonPathMinDistance función que calcula todos los posibles pertinentes permutaciones intervienen en el cálculo de la menor polígono camino, como una simbólica exacta/algebraicas construir:
PolygonPathMinDistance[points_] := Module[{orderings, pointorderings, pathsToCheck, ww},
orderings = Union[Permutations[Range[Length[points]]],
SameTest -> (#1 == Reverse[#2] &)];
pointorderings = Map[points[[#]] &, orderings];
pathsToCheck = Map[Partition[#, 2, 1] &, pointorderings];
Min[Map[Total[Map[EuclideanDistance @@ # &, #1] /. Abs[ww_]->ww]&, pathsToCheck]]
]
.
Especificación alternativa de problema en Coordenadas Polares
Si los puntos están distribuidos Uniformemente sobre un disco de radio de la unidad e independiente, la distribución conjunta de $n$ puntos $((X_1,Y_1), ..., (X_n,Y_n))$, con articulación pdf $f(\cdots)$ es dada anteriormente. Como alternativa, considere la posibilidad de la transformación a coordenadas polares, $(X_i \a R_i cos(\Theta_i)$, $Y_i \a R_i pecado(\Theta_i))$, $i = 1$ $n$. Entonces, la articulación de pdf es:
$$f( (r_1,\theta_1), ..., (r_n,\theta_n) ) = \frac{r_1 \times r_2 \times \cdots \times r_n}{\pi^{n}}$$
con el dominio de apoyo, $R_i=r_i \in \{r_i:0<r_i<1\}$ y $\Theta_i=\theta_i \in \{\theta_i:0<\theta_i<2 \pi\}$. Entonces, la distancia entre dos puntos al azar, digamos $(X_i,Y_i)$ y $(X_j,Y_j)$ está dada por la fórmula de la distancia para las coordenadas polares:
$$\sqrt{\left(X_j-X_i\right){}^2+\left(Y_j-Y_i\right){}^2} = \sqrt{R_i^2 + R_j^2 -2 R_i R_j \cos \left(\Theta_i-\Theta_j\right)}$$
Tomando las expectativas, a continuación, se obtiene el mismo resultado que el anterior. Para $n = 2$ caso, la integración simbólica es un poco más fácil, y se puede obtener el resultado:
$$\begin{align*}\displaystyle E\left[ Z_2\right] &= E\left[ \sqrt{R_1^2 + R_2^2 -2 R_1 R_2 \cos \left(\Theta _1-\Theta _2\right)}\right]
\\ &= \frac{8}{\pi} \int_0^1\int_0^1 |r_1 - r_2| EllipticE[\frac{-4 r_1 r_2}{(r_1-r_2)^2}]r_1 r_2 dr_1\,dr_2 \\ &= \frac{8}{\pi} \frac{16}{45} \approx 0.9054 \text{(como arriba)}\end{align*}$$
Se extiende desde un disco a una pelota
No hay ninguna razón intrínseca de los mismos métodos no puede ser extendida a una pelota ... más dimensiones (y más computacional gruñido necesario).
