Tests de eficiencia sobre algoritmos de creación de números aleatorios sin repetición.

Código Java (AleatorioSinRepeticion1.java):

/**
 * Tests de eficiencia sobre diferentes algoritmos de creación de números
 * aleatorios sin repetición.
 */

package aleatoriosinrepeticion1;

import java.util.Random;
import java.util.Stack;

public class AleatorioSinRepeticion1 {

    public static void main(String[] args) {

        long precision = 1000000;
        int nNodos = 13;

        test1(nNodos, precision);// Eficiencia base
        test2(nNodos, precision);// Eficiencia +620%
        test3(nNodos, precision);// Eficiencia +1156%

    }

    private static void test1(int nNodos, long precision) {

        int perm[] = new int[nNodos];
        int pos;

        long tiempo1 = System.nanoTime();
        for (int k = 0; k < precision; k++) {
            Stack<Integer> pRuta = new Stack<Integer>();
            for (int i = 0; i < nNodos; i++) {
                pos = (int) Math.floor(Math.random() * nNodos);
                while (pRuta.contains(pos)) {
                    pos = (int) Math.floor(Math.random() * nNodos);
                }
                pRuta.push(pos);
                perm[i] = pos;
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo1: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

    private static void test2(int nNodos, long precision) {

        Stack<Integer> pRef = new Stack<Integer>();
        int perm[] = new int[nNodos];
        Random rnd = new Random();
        int pos;

        long tiempo1 = System.nanoTime();
        for (int k = 0; k < precision; k++) {
            for (int i = 0; i < nNodos; i++) {
                pRef.add(i);
            }
            for (int i = 0; i < nNodos; i++) {
                pos = rnd.nextInt(pRef.size());
                perm[i] = pRef.remove(pos);
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo2: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

    private static void test3(int nNodos, long precision) {

        int[] aux_perm = new int[nNodos];
        Random rnd = new Random();
        int[] perm = new int[nNodos];
        int aux_nNodos = nNodos;
        int pos;

        long tiempo1 = System.nanoTime();
        for (int index = 0; index < precision; index++) {
            aux_nNodos = nNodos;
            for (int i = 0; i < nNodos; i++) {
                aux_perm[i] = i + 1;
            }
            for (int i = 0; i < nNodos; i++) {
                pos = rnd.nextInt(aux_nNodos);
                perm[i] = aux_perm[pos] - 1;
                aux_perm[pos] = aux_perm[aux_nNodos - 1];
                aux_nNodos--;
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo3: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

}

Resultado:

run:

Tiempo1: 9470.44684 ms

Tiempo2: 1515.179325 ms

Tiempo3: 823.204608 ms

BUILD SUCCESSFUL (total time: 11 seconds)

Uso CPU Multinúcleo. Cálculo TSP por el Método Montecarlo.

Este es un ejemplo de cálculo del TSP utilizando método Montecarlo y ejecución de N hilos simultáneos. Para ello se dispone de un apartado de configuración donde se pondrá el número de hilos a ejecutar simultáneamente y la precisión (número de interacciones). A más interacciones, mayor precisión en los cálculos.


* Entrada de parámetros de configuración:

  >Parámetro 1 (Número de CPUs/Hilos):
  Mi PC consta de una CPU Intel Core 2 Duo (2 núcleos), por lo que lo ideal en este caso seria indicarle 2 Hilos (Fig.1)
  

Fig 1. Test velocidad según número de hilos ejecutados simultáneamente [sobre una CPU Intel Core 2 Duo]

  >Parámetro 2 (Precisión):

  En el ejemplo consta de 13 nodos que permite hasta un total de 6.227.020.800 rutas distintas. Si le indicamos una precisión de 100.000.000 interacciones obtendremos una ruta bastante óptima con un 18.84% de probabilidades de dar con la ruta más corta posible.

Fig. 2 - Relación entre el Número Interacciones (método Montecarlo) con el % de probabilidades de dar con la ruta más óptima posible.

Código 1 (TSP_Optimizar.java):

package tsp_optimitzar;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class TSP_Optimitzar {

    @SuppressWarnings("empty-statement")
    public static void main(String[] args) throws InterruptedException {
        String[] nombre_nodos = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"};
        int nNodos = nombre_nodos.length;

        System.out.println("Configuración:\n");
        System.out.println(">Número de CPUs/Hilos?");
        Scanner reader = new Scanner(System.in);
        int nHilos = Integer.parseInt(reader.next());
        System.out.println(">Precisión?");
        reader = new Scanner(System.in);
        double precision = Double.parseDouble(reader.next());

        float[] vDistancias = {
            0.0F, 820.8666F, 475.23F, 630.9444F, 175.44064F, 360.75314F, 755.7496F, 186.8207F, 591.06683F, 298.11227F, 681.6526F, 289.17914F, 995.64746F,
            8.357133F, 0.0F, 366.78992F, 83.80908F, 217.9351F, 237.86781F, 581.63153F, 925.394F, 453.48624F, 636.67017F, 200.24031F, 695.21234F, 890.6944F,
            70.59399F, 368.34445F, 0.0F, 764.7878F, 182.2146F, 93.2886F, 194.98314F, 180.56621F, 363.5746F, 443.70917F, 641.6165F, 549.982F, 931.1095F,
            874.7707F, 874.603F, 605.9038F, 0.0F, 25.786762F, 147.78946F, 533.5506F, 47.42154F, 108.01653F, 471.1008F, 261.24738F, 656.25104F, 99.16098F,
            4.8551674F, 361.6684F, 245.69385F, 652.172F, 0.0F, 100.449036F, 633.9419F, 670.09125F, 150.59242F, 907.34863F, 275.1372F, 938.0571F, 38.05818F,
            652.2065F, 238.30981F, 927.4687F, 318.43414F, 429.15936F, 0.0F, 595.4067F, 431.22238F, 388.80447F, 283.0264F, 249.39452F, 8.14694F, 899.722F,
            671.8014F, 811.3296F, 355.1809F, 8.395913F, 157.35182F, 596.0345F, 0.0F, 306.99182F, 192.86949F, 298.59897F, 432.59073F, 633.6216F, 817.70074F,
            301.66046F, 462.99008F, 147.49551F, 730.2186F, 902.4855F, 160.01877F, 485.22964F, 0.0F, 495.07837F, 358.40677F, 555.7709F, 983.111F, 318.58316F,
            160.77138F, 3.104256F, 998.9104F, 310.08047F, 295.39194F, 466.86356F, 673.8137F, 499.67224F, 0.0F, 423.98648F, 855.799F, 779.7313F, 947.50555F,
            372.0423F, 715.80835F, 866.05927F, 57.02963F, 696.6522F, 65.42037F, 388.12494F, 826.8198F, 912.82697F, 0.0F, 304.32504F, 886.0547F, 788.8762F,
            157.58907F, 235.23514F, 575.64496F, 682.70575F, 689.79407F, 57.43567F, 877.0111F, 659.9925F, 658.1151F, 196.0468F, 0.0F, 549.32043F, 440.2496F,
            957.9573F, 699.2848F, 57.796417F, 461.52716F, 881.24054F, 752.86084F, 748.3989F, 42.0304F, 459.0128F, 424.106F, 206.15532F, 0.0F, 386.36868F,
            69.71372F, 877.4519F, 881.0224F, 954.1217F, 924.6164F, 813.5333F, 743.41473F, 956.4676F, 509.52542F, 867.4073F, 202.12968F, 515.76715F, 0.0F};


        List<String> lista_nombre_nodos = new ArrayList<>();
        lista_nombre_nodos.addAll(Arrays.asList(nombre_nodos));
        
        // mostrar tabla distancias
        tDistancias(vDistancias, nNodos);

        System.out.println("\nCalculando...");
        long tiempo1 = System.nanoTime();
        TSP_Montecarlo tsp[] = new TSP_Montecarlo[nHilos];
        for (int i = 0; i < nHilos; i++) {
            tsp[i] = new TSP_Montecarlo(lista_nombre_nodos, vDistancias, precision, nHilos);
            tsp[i].start();
        }

        // Control de finalización hilos
        int cont;
        do {
            try { // +15%
                Thread.sleep(500);
            } catch (Exception e) {
            }
            cont = 0;
            for (int i = 0; i < nHilos; i++) {
                if (!tsp[i].isAlive()) {
                    cont++;
                }
            }
        } while (cont != nHilos);

        long tiempo2 = System.nanoTime();

        // Balance final hilos
        float minimo = Float.MAX_VALUE;
        String ruta = "";
        System.out.println("\nResultados Hilos:");
        for (int i = 0; i < nHilos; i++) {
            System.out.println("Thread " + i + ": " + tsp[i].getDistancia());
            if (tsp[i].getDistancia() < minimo) {
                minimo = tsp[i].getDistancia();
                ruta = tsp[i].getRuta();
            }
        }

        // Mostrar resultados
        System.out.println("\nResultado más óptimo encontrado: ");
        System.out.println("Ruta: " + ruta + "\nDistancia: " + minimo);
        System.out.println("Tiempo empleado: " + (tiempo2 - tiempo1) / 1e6 + " ms");

    }

    private static void tDistancias(float[] vDistancias, int n) {
        n = (int) Math.sqrt(vDistancias.length);
        double[][] tabla = new double[n][n];
        String str;
        int cont = 0;
        System.out.println("\nTabla distancias:");
        for (int x = 0; x < n; x++) {
            str = "| ";
            for (int y = 0; y < n; y++) {
                tabla[y][x] = vDistancias[cont];
                str += tabla[y][x] + " | ";
                cont++;
            }
            System.out.println(str);
        }
    }

}

Código 2 (TSP_Montecarlo.java):

package tsp_optimitzar;

import java.util.List;

import java.util.Random;

public class TSP_Montecarlo extends Thread {

    // Entradas

    private final List<String> lista_nombre_nodos;

    private final float[] v_distancias;

    private final double precision;

    // Resto variables 

    private float minimo = Float.MAX_VALUE;

    private float sumatorio = 0;

    private int[] vRuta = null;

    private final int nNodos;

    // Contructor

    public TSP_Montecarlo(List<String> lista_nombre_nodos, float[] v_distancias, double precision, int nHilos) {

        this.lista_nombre_nodos = lista_nombre_nodos;

        this.nNodos = lista_nombre_nodos.size();

        this.v_distancias = v_distancias;

        this.precision = Math.abs(precision / nHilos);

    }

    @Override

    public void run() {

        // Control parametros correctos

        if (lista_nombre_nodos.size() == Math.sqrt(v_distancias.length)) {

            float[][] t_distancias = conversorVT(v_distancias);

            int[] aux_perm = new int[nNodos];

            int[] perm = new int[nNodos];

            Random rnd = new Random();

            int aux_nNodos = nNodos;

            int cont = 0;

            int res;

            do {

                sumatorio = 0;

                // Busqueda de rutas aleatorias evitando repeticiones de nodos.

                // +1338%

                aux_nNodos = nNodos;

                for (int i = 0; i < nNodos; i++) {

                    aux_perm[i] = i + 1;

                }

                for (int i = 0; i < nNodos; i++) {

                    res = rnd.nextInt(aux_nNodos);

                    perm[i] = aux_perm[res] - 1;

                    aux_perm[res] = aux_perm[aux_nNodos - 1];

                    aux_nNodos--;

                }

                

                sumatorio += t_distancias[perm[nNodos - 1]][perm[0]];

                for (int i = 0; i < (nNodos - 1); i++) {

                    sumatorio += t_distancias[perm[i]][perm[i + 1]];

                    if (sumatorio > minimo) { // +200%

                        break;

                    }

                }

                if (sumatorio < minimo) {

                    minimo = sumatorio;

                    vRuta = perm.clone();

                }

            } while (cont++ < precision);

        }

    }

    public float[][] conversorVT(float[] v_distancias) {

        float[][] t_distancias = new float[nNodos][nNodos];

        int cont = 0;

        for (int i = 0; i < nNodos; i++) {

            for (int j = 0; j < nNodos; j++) {

                t_distancias[j][i] = v_distancias[cont];

                cont++;

            }

        }

        return t_distancias;

    }

    public float getDistancia() {

        return minimo;

    }

    public String getRuta() {

        String ruta = lista_nombre_nodos.get(vRuta[0]) + " - ";

        for (int i = 1; i < nNodos - 1; i++) {

            ruta += lista_nombre_nodos.get(vRuta[i]) + " - ";

        }

        ruta += lista_nombre_nodos.get(vRuta[nNodos - 1]);

        return ruta;

    }

}

Resultado:

run:

Configuración:
>Número de CPUs/Hilos? 
2
>Precisión? 
100000000

Tabla distancias:
| 0.0 | 820.8665771484375 | 475.2300109863281 | 630.9443969726562 | 175.44064331054688 | 360.7531433105469 | 755.7495727539062 | 186.82069396972656 | 591.0668334960938 | 298.1122741699219 | 681.652587890625 | 289.17913818359375 | 995.6474609375 | 
| 8.357132911682129 | 0.0 | 366.7899169921875 | 83.80908203125 | 217.9351043701172 | 237.86781311035156 | 581.6315307617188 | 925.3939819335938 | 453.4862365722656 | 636.670166015625 | 200.2403106689453 | 695.2123413085938 | 890.6943969726562 | 
| 70.59398651123047 | 368.3444519042969 | 0.0 | 764.7877807617188 | 182.214599609375 | 93.2885971069336 | 194.98313903808594 | 180.5662078857422 | 363.5745849609375 | 443.70916748046875 | 641.6165161132812 | 549.9819946289062 | 931.1094970703125 | 
| 874.7706909179688 | 874.60302734375 | 605.90380859375 | 0.0 | 25.786762237548828 | 147.78945922851562 | 533.5505981445312 | 47.421539306640625 | 108.01653289794922 | 471.1007995605469 | 261.24737548828125 | 656.2510375976562 | 99.16098022460938 | 
| 4.855167388916016 | 361.66839599609375 | 245.69384765625 | 652.1719970703125 | 0.0 | 100.44903564453125 | 633.94189453125 | 670.0912475585938 | 150.59242248535156 | 907.3486328125 | 275.13720703125 | 938.05712890625 | 38.05818176269531 | 
| 652.2064819335938 | 238.309814453125 | 927.4686889648438 | 318.43414306640625 | 429.15936279296875 | 0.0 | 595.4066772460938 | 431.2223815917969 | 388.8044738769531 | 283.0263977050781 | 249.39451599121094 | 8.146940231323242 | 899.7219848632812 | 
| 671.8013916015625 | 811.32958984375 | 355.180908203125 | 8.395913124084473 | 157.35182189941406 | 596.0344848632812 | 0.0 | 306.9918212890625 | 192.86949157714844 | 298.5989685058594 | 432.5907287597656 | 633.62158203125 | 817.7007446289062 | 
| 301.66046142578125 | 462.9900817871094 | 147.49551391601562 | 730.2186279296875 | 902.4854736328125 | 160.01876831054688 | 485.2296447753906 | 0.0 | 495.078369140625 | 358.4067687988281 | 555.7708740234375 | 983.1110229492188 | 318.5831604003906 | 
| 160.77137756347656 | 3.1042559146881104 | 998.910400390625 | 310.0804748535156 | 295.3919372558594 | 466.8635559082031 | 673.813720703125 | 499.6722412109375 | 0.0 | 423.9864807128906 | 855.7990112304688 | 779.7313232421875 | 947.5055541992188 | 
| 372.04229736328125 | 715.808349609375 | 866.0592651367188 | 57.02962875366211 | 696.6522216796875 | 65.42037200927734 | 388.12493896484375 | 826.81982421875 | 912.8269653320312 | 0.0 | 304.3250427246094 | 886.0546875 | 788.876220703125 | 
| 157.5890655517578 | 235.23513793945312 | 575.6449584960938 | 682.7057495117188 | 689.7940673828125 | 57.4356689453125 | 877.0111083984375 | 659.9924926757812 | 658.1151123046875 | 196.0467987060547 | 0.0 | 549.3204345703125 | 440.2496032714844 | 
| 957.957275390625 | 699.2847900390625 | 57.796417236328125 | 461.52716064453125 | 881.2405395507812 | 752.86083984375 | 748.39892578125 | 42.030399322509766 | 459.0127868652344 | 424.1059875488281 | 206.1553192138672 | 0.0 | 386.3686828613281 | 
| 69.7137222290039 | 877.451904296875 | 881.0223999023438 | 954.1217041015625 | 924.6163940429688 | 813.5333251953125 | 743.4147338867188 | 956.4675903320312 | 509.5254211425781 | 867.4072875976562 | 202.1296844482422 | 515.7671508789062 | 0.0 | 

Calculando...

Resultados Hilos:
Thread 0: 1497.1041
Thread 1: 1340.8267

Resultado más óptimo encontrado: 
Ruta: M - E - A - B - I - D - J - G - C - H - L - F - K - 
Distancia: 1340.8267
Tiempo empleado: 44039.191597 ms
BUILD SUCCESSFUL (total time: 56 seconds)


Nota: Lo marcado como [// +XXX%] significa el grado de mejora en la eficiencia del algoritmo con respecto a códigos anteriores.