Swap Methode

[Heda]

Hi,
ich bin gerade dabei ein Travelling Salesman Problem zu programmieren und
stecke nun so kurz vorm Ende fest. Ich muss 2 aus den 10 ausgewählten "Städten" mit 2 zufälligen anderen "Städten" aus der Tabelle vertauschen. Nur stehe ich einfach komplett auf dem Schlauch und kriege seit Tagen nichts richtiges hin.
Hoffentlich kann mir jemand hier helfen.

Hier der Code:

public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[][] distance = new int[10][10];
        Random random = new Random();
        int sum = 0;
        int sr = 0;

        System.out.println("Tabelle - Entfernungen zwischen den Städten");

        // create a table with distances
        for (int i = 0; i < distance.length; i++) {
            for (int j = 0; j < distance[i].length; j++) {
                //random max/min = (max + 1 - min) + 1
                distance[i][j] = random.nextInt(100 + 1 - 1) + 1;
                distance[j][i] = random.nextInt(100 + 1 - 1) + 1;
                distance[i][j] = distance[j][i];
                distance[i][i] = 0;
                distance[j][j] = 0;
            }
        }

        // print table in console
        for (int[] row : distance) {
            printRow(row);
        }

        System.out.println("");
        System.out.println("Städtereise");

        // print random route
        for (int[] array : distance) {
            sr = getRandom(array);
            System.out.println(sr);
            sum = sum + sr;
        }

        // print total of random route
        System.out.println("");
        System.out.println("Gesamt");
        System.out.println(sum);
       


    }

    // method for table
    public static void printRow(int[] row) {
        for (int i : row) {
            System.out.print(i);
            System.out.print("\t");
        }
        System.out.println();
    }

    // method for 10 random cities
    public static int getRandom(int[] array) {
        int rnd = new Random().nextInt(array.length);
        return array[rnd];
    }

}

 

[TheWhiteShadow]

Du speicherst die "ausgewählten Städte" nicht ab sondern addierst nur die Kosten auf. So kannst du nichts mehr tauschen. Du musst die Städte zuerst auflisten und dann die Kosten für die Reise berechnen.

int[] route = new int[10];
for (int i=0; i < distance.length; i++) {
route[i] = getRandom(distance[i]);
}

Außerdem hast du noch einen Fehler in getRandom. Du schließt nicht aus, dass der Reisende zur gleichen Stadt reist. Das verursacht zwar keine Kosten, führt aber dazu, dass du eine Stadt auslässt. Im Schlimmsten Fall reist er gar nicht ab.

Davon ab sind diverse Mängel in der Doppel-Schleife:
1. Du erstellst 2 zufalls Zahlen und verwirfst eine wieder.
2. Was soll das 100+1-1 aussagen? Es bleibt trotzdem 100
3. Du iterierst über alle Distanzen und setzt jeweils 4 Werte. Das sind 300% zu viel!
Als Abbruchbedingugn reicht in der 2. forschleife: j < i, dadurch iterierst du deine Tabelle nur halb durch.
Dann reicht es wenn du immer den Index [ i][j] und [j][ i] auf den gleichen Wert setzt. [ i][ i] bzw. [j][j] käme hier auch gar nicht vor und bleibt 0.