Cómo escribir matemáticamente n número de bucles

Question

Tengo el siguiente código. Quiero escribirlo matemáticamente. Cualquier ayuda sería apreciada.

int in1=1, in2=-1;
double totalDistance=0.0;
double min_dis = Double.MAX_VALUE;
for(int i=0;i<N1;i++){
    for(int j=0;j<N2;j++){
        dis = calculateDistance(Solutions(i),Solutions(j));
                totalDistance = dis;
                if(totalDistance< min_dis){
                    min_dis=totalDistance;
                    in1=i;
                    in2=j;
            }   
        }
    }
print(in1, in2)

Matemáticamente, lo escribo de la siguiente manera: \begin{equation} argmin_{i,j \in \{1,2, \dots, n_1\} \times \{1,2, \dots, n_2\}} dis(S_i, S_j) \end{equation} $\times$ se refiere al producto cartesiano entre conjuntos y ${dis(S_i, S_j)}$ es la distancia.

Quiero saber si es una representación matemática correcta. Si es correcta, quiero extenderla a n bucles. A continuación se muestra un ejemplo de 3 bucles.

int in1=1, in2=-1, in3=-1;
    double totalDistance=0.0;
    double min_dis = Double.MAX_VALUE;
    for(int i=0;i<N1;i++){
        for(int j=0;j<N2;j++){
            double dis1 = calculateDistance(**S1**(i), **S2**(j));
            for(int z=0;z<N3;z++){
                double dis2 = calculateDistance(**S2**(j), **S3**(z));
                totalDistance = dis1+ dis2;
                if(totalDistance< min_dis){
                    min_dis=totalDistance;
                    in1=i;
                    in2=j;
                    in3=z;
                }
            }
        }
    }
    print(in1 in2 in3);

¿Cómo puedo representar la versión generalizada en notación matemática?

Gracias de antemano.

Answer 1

La expresión matemática no es correcta. Aquí nos centramos en el primer fragmento de código. La consideración para la segunda parte y el caso general es similar.

Algunos aspectos deben estudiarse con más detalle:

• Puede haber más de un par con distancia mínima, mientras que el código devuelve siempre un único elemento.

• En pedir de los bucles for: Esto es importante en caso de que haya más de un elemento con distancia mínima.

• Detalles técnicos: La gama de índices es $0\leq i < N$ en lugar de $1\leq i\leq N$ .

A continuación utilizaremos la notación \begin{align*} \operatorname{calculateDistance(Solutions(i),Solutions(j))}\quad&\longrightarrow\quad d(S_i,S_j)\\ \operatorname{N1}\quad&\longrightarrow\quad N_1\\ \operatorname{N2}\quad&\longrightarrow\quad N_2\\ \operatorname{in1}\quad&\longrightarrow\quad i_1\\ \operatorname{in2}\quad&\longrightarrow\quad i_2\\ \end{align*}

Primer paso: $2$ bucles

Sea $N_1,N_2>0$ . Obtenemos, suponiendo simetría de la función distancia

\begin{align*} A_2&:={\operatorname{argmin}}_{0\leq i_2<i_1<\max\{N_{i_1},N_{i_{2}}\}}\{d(S_{i_1},S_{i_2})\}\\ &=\{(i_1,i_2):d(S_{i_1},S_{i_2})\leq d(S_{j_1},S_{j_2}),0\leq i_1,j_1<N_1, 0\leq i_2,j_2<N_2\}\\ \\ B_2&:=\min_{0\leq i_2<N_2}\min_{0\leq i_1<N_1}\{(i_1,i_2):(i_1,i_2)\in A_2\} \end{align*} con $B_2$ formado por el único elemento que devuelve el código.

Puede haber más de un par con la misma distancia mínima, de modo que $A_2$ contendrá normalmente más de un elemento. Supongamos que el conjunto $A_2$ contiene los cuatro elementos \begin{align*} A_2=\{(4,3),(4,5),(8,2),(10,6)\} \end{align*} En este caso, el código devolverá $(4,3)$ . Desde $4$ es el valor más pequeño de las primeras coordenadas, los candidatos de $A_2$ son $(4,3)$ y $(4,5)$ . De estos dos valores, el código selecciona el que tenga la segunda coordenada más baja, dando como resultado $(4,3)$ .

Esto implica que el pedir de los ajustes mínimos en $B_2$ es esencial. Tenga en cuenta que \begin{align*} B_2=&\min_{0\leq k_2<N_2}\min_{0\leq k_1<N_1}\{(k_1,k_2):(k_1,k_2)\in A_2\}=\{(4,3)\}\quad\text{while}\\ &\min_{0\leq k_1<N_1}\min_{0\leq k_2<N_2}\{(k_1,k_2):(k_1,k_2)\in A_2\}=\{(8,2)\}\\ \end{align*}

Paso general: $k$ bucles

Sea $N_1,N_2,\ldots,N_k>0,k\geq 2$ . Obtenemos

\begin{align*} A_k&:={\displaystyle{{\text{argmin}}_{{0\leq i_l<i_{l+1}<\max\{N_{i_l},N_{i_{l+1}}\}}\atop{1\leq l\leq k-1}}} \left\{\sum_{j=1}^{k-1}d(S_{i_j},S_{i_{j+1}})\right\}}\\ \\ B_k&:=\min_{0\leq i_k<N_k}\min_{0\leq i_{k-1}<N_{k-1}} \cdots\min_{0\leq i_1<N_1}\{(i_1,i_2,\ldots,i_k):(i_1,i_2,\ldots,i_k)\in A_k\} \end{align*} con $B_k$ formado por el único elemento que devuelve el código.

Revisión del código:

• $\operatorname{in1}$ debe inicializarse con $-1$

• Dado que ambos índices $i$ un $j$ son el argumento para la llamada $\operatorname{calculateDistance(S(i),S(j))}$ y la llamada es simétrica con respecto a los argumentos no es sólida, que $i$ y $j$ tienen diferente alcance. Preferimos suponer \begin{align*} &0\leq i_1,i_2< N_1\\ \end{align*}

• Esperamos un función de distancia $d$ actuar simétricamente: $d(x,y)=d(y,x)$ para todos $x,y$ y también $d(x,x)=0$ para todos $x$ . Por lo tanto, preferimos codificar \begin{align*} &0\leq i_2 < i_1<N_1\\ \end{align*}

Answer 2

Definir el conjunto de minimizadores:

$S = \arg\min_{ x \in \mathbb{N}^n} \{ \sum_{i=0}^{n-2} dis(S_{x_i},S_{x_{i+1}}) : x_i < n_i \; i = 0,1,\ldots,n-2 \}$

La solución es el primer elemento lexicográfico de $S$ :

$\min\{x \in S \}$

donde $\min$ realiza una minimización lexicográfica. Esto devuelve el mismo elemento de $S$ que produce su código.