Matriz de conectividad circular.

Este código Java genera puntos aleatorios en la línea de la circunferencia de un círculo y crea una matriz de distancias entre ellos. Esta matriz de distancias generada, que representa un grafo completo con propiedades geométricas especiales, es el núcleo del programa. Es ideal para probar diversos algoritmos, especialmente variantes del Problema del Viajante de Comercio (TSP).
La disposición circular de los puntos ofrece una característica importante: la ruta óptima del TSP es conocida (seguir la circunferencia), y el algoritmo del del TSP Vecino Más Cercano la encuentra eficientemente. Esto proporciona un valioso punto de referencia para evaluar y comparar el rendimiento de diferentes algoritmos de optimización sobre la misma matriz de distancias.


Código Java (CircunferenciaDistancias.java):

package circunferenciadistancias;

import java.util.Random;

public class CircunferenciaDistancias {

    public static int N = 16;
    public static int diametro = 1024;

    public static void main(String[] args) {
        double radio = diametro / 2.0;
        double[][] puntos = new double[N][2];
        double[][] distancias = new double[N][N];
        Random random = new Random();

        // Generar N puntos aleatorios en la circunferencia
        for (int i = 0; i < N; i++) {
            double angulo = random.nextDouble() * 2 * Math.PI;
            double x = radio + radio * Math.cos(angulo);
            double y = radio + radio * Math.sin(angulo);
            puntos[i][0] = x;
            puntos[i][1] = y;
        }

        // Calcular la matriz de distancias entre los puntos y mostrarlas en pantalla
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i != j) {
                    distancias[i][j] = Math.sqrt(
                            Math.pow(puntos[i][0] - puntos[j][0], 2)
                            + Math.pow(puntos[i][1] - puntos[j][1], 2)
                    );
                } else {
                    distancias[i][j] = 0;
                }
                System.out.printf("%6d", Math.round(distancias[i][j]));
            }
            System.out.println();
        }
    }
}


Resultado:

run:
     0   264   299   950   996   894   199   901   673  1023   895   941   258   701  1024   812
   264     0   541   820   901   993    67   996   452   998   993   805   505   485   981   946
   299   541     0  1020  1022   710   483   720   869   968   711  1018    42   888   988   595
   950   820  1020     0   149   796   858   787   465   414   795    26  1016   432   352   881
   996   901  1022   149     0   693   930   684   593   274   693   174  1024   562   209   796
   894   993   710   796   693     0   974    13  1002   467     1   811   740   993   525   149
   199    67   483   858   930   974     0   978   511  1011   975   844   446   543   998   918
   901   996   720   787   684    13   978     0   999   455    12   803   749   990   514   162
   673   452   869   465   593  1002   511   999     0   795  1001   442   846    37   751  1022
  1023   998   968   414   274   467  1011   455   795     0   466   437   981   770    67   595
   895   993   711   795   693     1   975    12  1001   466     0   811   741   993   524   150
   941   805  1018    26   174   811   844   803   442   437   811     0  1012   409   376   894
   258   505    42  1016  1024   740   446   749   846   981   741  1012     0   867   998   629
   701   485   888   432   562   993   543   990    37   770   993   409   867     0   725  1019
  1024   981   988   352   209   525   998   514   751    67   524   376   998   725     0   648
   812   946   595   881   796   149   918   162  1022   595   150   894   629  1019   648     0
BUILD SUCCESSFUL (total time: 0 seconds)