Optimierungsalgorithmus alá Travelling Salesman Problem

[TeddyFlippsi]

Hallo Leute,
Ist mein erster Beitrag und ich würde euch gern erst mal die Aufgabe zeigen:
,,Schreiben Sie eine Vertauschungsfunktion, die 2 zufällige Stadte in einer Rundreise vertauscht. Der Optimierungsalgorithmus in der main() Funktion soll nun immer nur dann die mit Vertauschung generierte Rundreise übernehmen, wenn sie kürzer als die vorherige ist. Falls es Verbesserung gibt, schreiben Sie die neue Rundreise und die Entfernung auf den Bildschirm. Wie lang ist Ihre kürzeste Rundreise?"
Also ich weiß, dass ich hier anhand eines Arrays die Werte optimieren soll, hab in einer früheren Aufgabe schon Distanzen anzeigen lassen etc. was ich aber jetzt überhaupt nicht verstehe, ist wie die kürzere Rundreise dann berechnet bzw. ausgegeben werden soll... Ich weiß, dass ist nicht viel wissen, aber hab gerade die 5. Woche vom 1. Semester überlebt und bin jetzt ratlos.
Danke im vorraus

 

[Tarrew]

Für mich liest sich das so als wäre das eine Erweiterung zu einer anderen Aufgabe. Falls ja, dann wäre es mal nützlich den ersten Aufgabenteil bzw. die Lösung dazu zu sehen. Ich persönlich kann mir dann besser ein Bild davon machen.

 

[TeddyFlippsi]

Travelling Salesman Problem:
Ein Mann möchte eine Rundreise durch 10 Städte machen und dabei eine möglichst kurze Wegstrecke zurücklegen. Eine Tabelle soll ihm Auskunft darüber geben, welche Entfernung er von Stadt A zu Stadt B zurücklegen muss. Erstellen Sie im ersten Schritt solch eine 2 Dimensionale Entfernungstabelle und füllen Sie sie mit Zufallszahlen. Achten Sie darauf, dass die Entfernung zwischen A und B die gleiche ist wie die zwischen B und A.

Nun schreiben Sie eine Funktion, welche für eine Rundreise, die in einem int Array gespeichert ist (5,7,2,4 heisst Stadt 5 nach Stadt 7 nach Stadt 2 nach Stadt 4 nach Stadt 5) die Länge der Rundreise zurückgibt.

Schreiben Sie eine Vertauschungsfunktion, die 2 zufällige Stadte in einer Rundreise vertauscht. Der Optimierungsalgorithmus in der main() Funktion soll nun immer nur dann die mit Vertauschung generierte Rundreise übernehmen, wenn sie kürzer als die vorherige ist. Falls es Verbesserung gibt, schreiben Sie die neue Rundreise und die Entfernung auf den Bildschirm. Wie lang ist Ihre kürzeste Rundreise?

 

[TeddyFlippsi]

public class Aufgabe1 {

public static void main(String[] args) {
// declare an empty array with a predestined size
int reise [][] = new int [10][10];

for (int a = 0; a < 10; a++)
{
for (int b = 0; b < 10; b++)
{
if (a == b)
{
// if a and b are equal, print an "0"
reise [a] = 0;
}
else
{
// The array is being filled randomly
reise [a] = (int)(Math.random() * 10);
reise [a] = reise [a];
}
}
}
for (int a = 0; a < 10; a++)
{
for (int b = 0; b < 10; b++)
{
// The output is specifically aligned and formated
System.out.printf("%5d", reise [a]);
}
System.out.println();
}
}
}

____________________________________________________________________________________________

import java.lang.reflect.Array;

public class aufgabe2 {

public static void main(String[] args) {

System.out.println("Die Rundfahrt beginnt bei Stadt 5, dann 7, 2, 4 und wieder zurück nach Stadt 5");

int staedtereise [] = {5, 7, 2, 4};
int abstaende [] = {2, 5, 2, 1};

int laenge = (abstaende[0]+abstaende[1]+abstaende[2]+abstaende[3]);

System.out.println("Die Länge der Rundfahrt beträgt: " +laenge+" km");
}
}

 

[TeddyFlippsi]

Das ist meine Lösung bis jetzt