Traveling Salesman Problem [Arrays]

J

johannes2308

Mitglied
Hallo,
ich muss gerade im Studium ein Traveling Salesman Problem programmieren. Dabei war die erste Aufgabe eine Entfernungstabelle für 10 verschiedenen Städten zu machen, die mit Zufallswerten gefüllt werden soll. Das habe ich geschafft, aber nun mein Problem:
Die nächst Aufgabe laute: "
Nun schreiben Sie eine Funktion, welche für eine beliebige Rundreise, die in einem int Array gespeichert ist (z.B. 5,7,2,4,1,3,6,8,9,0 heißt Stadt 5 nach Stadt 7 nach Stadt 2 nach Stadt 4 nach Stadt 5 ...) die Länge der Rundreise zurückgibt."
Dabei bin ich gerade komplett verloren obwohl wir sogar einen kleinen Ansatzpunkt erhalten haben, ich bin jedoch trotzdem gerade sehr gefangen hierbei.
Würde mich sehr freuen, wenn mir jemand helfen könnte!
Schonmal Dankeschön im Voraus! ;)
Hier erstmal der jetzige Code + der Ansatzpunkt für das weitere.

Traveling Salesman Problem:
public class TravellingSalesman {

    public static void main(String[] args) {
        
        int tab[][] = new int[10][10]; // size 10 two-dimensional array
        
        for (int i = 0; i < 10; i++) // creates random numbers for a 10x10 chart
        {
            for (int j = 0; j < 10; j++)
            {
                tab[i][j] = (int)(Math.random()*199); // every position in the array gets a random number between 0-199
                tab[j][i] = tab[i][j]; // makes sure that it is reversed the same
                tab[i][i] = 0; // if its the same town there is no distance
            }
        }
        
        for (int i = 0; i < 10; i++) // puts the random numbers in a visual chart
        {
            for (int j = 0; j < 10; j++)
            {
                System.out.print(tab[i][j] + "    ");
            }
            System.out.println();
        }
        
        // Ansatzpunkt für die weitere Aufgabe
        
    /*    int tour[] = {5,7,2,4,1,3,6,8,9,0};
        
        int dist = 0;
        
        for ()
        {
            dist += distance(tour[i], tour[i+1]);
        }
    */
 
mihe7

mihe7

Top Contributor
Du hast doch schon alles dastehen, wo liegt das Problem?!? i läuft von 0 bis tour.length-2.
 
J

johannes2308

Mitglied
Du hast doch schon alles dastehen, wo liegt das Problem?!? i läuft von 0 bis tour.length-2.
Naja also ich versteh nicht ganz woher das distance(tour[]...) kommt,(also primär das distance) und mir zeigt es wenn ich es laufen lasse an, dass "Index 10 out of bounds for length 10", aber nur wenn ich des untere ab 26 miteinbeziehe.
 
Zuletzt bearbeitet:
mihe7

mihe7

Top Contributor
Das distance ist eine Methode, die Du entweder bekommen hast oder selbst schreiben sollst. Und was die IndexOutOfBoundsException betrifft: wenn Du dem Stacktrace nach unten folgst, wirst Du die Stelle finden, an der die Exception in Deinem Code aufgetreten ist.
 
J

johannes2308

Mitglied
Das distance ist eine Methode, die Du entweder bekommen hast oder selbst schreiben sollst. Und was die IndexOutOfBoundsException betrifft: wenn Du dem Stacktrace nach unten folgst, wirst Du die Stelle finden, an der die Exception in Deinem Code aufgetreten ist.
Erstmal danke, dass du mir hilfst. Zu dieser Distance Methode ist nichts vorgegeben und ich weiß jetzt auch nicht was ich darein schreiben muss.
Bin mir auch nicht sicher was du mit "Stacktrace" meinst. Sorry bin mit den Begriffen teilweise noch nicht wirklich vertraut.
 
Blender3D

Blender3D

Top Contributor
Nun schreiben Sie eine Funktion, welche für eine beliebige Rundreise, die in einem int Array gespeichert ist (z.B. 5,7,2,4,1,3,6,8,9,0 heißt Stadt 5 nach Stadt 7 nach Stadt 2 nach Stadt 4 nach Stadt 5 ...) die Länge der Rundreise zurückgibt."
Schreibe eine Funktion, die die Distanzen in einer Rundreise (int []) aufsummiert. Die Funktion soll diese Summe dann zurückgeben.
 
Blender3D

Blender3D

Top Contributor
Distance:
int distance(  int[][] tab, int[] route ){
    int distance = 0;
    ...
    return distance;
}
 
F

fhoffmann

Top Contributor
Du hast doch eine "Abstandstabelle" in tab definiert.
Die Methode distance muss docnh nur die Werte aus dieser Abstandstabelle zurückliefern.
Und der "Handlungsreisende" ("traveling salsemen") möchte am Abend möglicherweise wieder zu Hause sein (wenn das in des Aufgabenstellung gefordert ist - aber die Bezeichnung "Rundreise" suggeriert das). Dann musst du den Abstand vom letzten Punkt der Reise zum ersten Punkt der Reise noch addieren.
 
J

johannes2308

Mitglied
Du hast doch eine "Abstandstabelle" in tab definiert.
Die Methode distance muss docnh nur die Werte aus dieser Abstandstabelle zurückliefern.
Und der "Handlungsreisende" ("traveling salsemen") möchte am Abend möglicherweise wieder zu Hause sein (wenn das in des Aufgabenstellung gefordert ist - aber die Bezeichnung "Rundreise" suggeriert das). Dann musst du den Abstand vom letzten Punkt der Reise zum ersten Punkt der Reise noch addieren.
Ich muss doch aber die werte bei tab also i und j als route und route[] benutzen wenn ich mir bei Route[] eine random 10er abfolge geben lasse und wenn ich das mit @Blender3D hinweis versuche habe ich dabei Übertragungsprobleme zwischen den Methoden. Ich soll ja die Komponente, welche mir eine Zufallsrundreise wiedergibt auch als eigene Funktion schreiben und das bringt mir dann weitere Probleme :/
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
Messoras Traveling Salesman Problem (TSP) Java Basics - Anfänger-Themen 4
J "travelling salesman problem" mit Java Editor Java Basics - Anfänger-Themen 17
T Optimierungsalgorithmus alá Travelling Salesman Problem Java Basics - Anfänger-Themen 4
J Allgemeines Problem mit Klassen Java Basics - Anfänger-Themen 2
U Problem mit dem initialisieren meines Strings in einer Schleife Java Basics - Anfänger-Themen 4
amgadalghabra algorithmisches Problem Java Basics - Anfänger-Themen 19
R ArrayList Problem Java Basics - Anfänger-Themen 6
InfinityDE Problem mit Datenübergabe an Konstruktor Java Basics - Anfänger-Themen 7
C RegEx Problem Java Basics - Anfänger-Themen 4
J Anfänger TicTacToe, Problem bei Gewinnoption, sowohl Unentschieden Java Basics - Anfänger-Themen 8
E Taschenrechner GUI Problem mit Fehlerhandling Java Basics - Anfänger-Themen 6
M Input/Output Fallunterscheidung Problem Java Basics - Anfänger-Themen 17
P Problem beim Überschreiben einer vererbten Methode Java Basics - Anfänger-Themen 4
M Problem bei Ausgabe Java Basics - Anfänger-Themen 7
S Java Array Problem... Java Basics - Anfänger-Themen 2
G Problem bei der Ausgabe einer Main Claase Java Basics - Anfänger-Themen 7
F Problem mit KeyListener in kombination mit dem ActionListener Java Basics - Anfänger-Themen 4
L Subset sum problem mit Backtracking Java Basics - Anfänger-Themen 18
N Problem mit Scanner Java Basics - Anfänger-Themen 2
J Klassen Problem Java Basics - Anfänger-Themen 8
A Out.format problem. Java Basics - Anfänger-Themen 3
J Problem bei der Programmierung eines Tannenbaums Java Basics - Anfänger-Themen 9
A Array problem Java Basics - Anfänger-Themen 16
2 Taschenrechner mit GUI Problem bei der Berechnung Java Basics - Anfänger-Themen 8
W Remote Method Invocation RMI - Problem Java Basics - Anfänger-Themen 0
I Ich habe ein Problem Java Basics - Anfänger-Themen 3
A Problem bei returnen eines Wertes Java Basics - Anfänger-Themen 6
M Regex Erstellung Problem Java Basics - Anfänger-Themen 2
D Input/Output Problem bei der Benutzereingabe eines Befehls Java Basics - Anfänger-Themen 14
M (Sehr großes Problem) Listen als static in anderen Klassen verwendet Java Basics - Anfänger-Themen 12
F Habe ein problem mit dem ActionListener Java Basics - Anfänger-Themen 3
C Regex-Problem Java Basics - Anfänger-Themen 4
J Problem beim vergleich von zwei Integer Java Basics - Anfänger-Themen 3
M Problem in der Modellierung Java Basics - Anfänger-Themen 20
W Wo ist das URL-Problem ? Java Basics - Anfänger-Themen 1
S Generics-Problem: Class, Class<?>, Class<Object> Java Basics - Anfänger-Themen 4
D FileWriter / FileReader Problem Java Basics - Anfänger-Themen 10
G Problem beim Speichern von Objekten in einer Datei Java Basics - Anfänger-Themen 7
S Compiler-Fehler Exception in thread "main" java.lang.Error: Unresolved compilation problem: Java Basics - Anfänger-Themen 6
J Problem mit Array: 2 Klassen Java Basics - Anfänger-Themen 2
S Collections funktionale Listen (ListNode<E>) review und problem beim clone Java Basics - Anfänger-Themen 0
W OOP Vererbung und Problem bei Zählschleife in einer Methode Java Basics - Anfänger-Themen 10
C Problem mit If Else If und Überprüfung eines Counters Java Basics - Anfänger-Themen 3
F Problem mit Listen Java Basics - Anfänger-Themen 5
I wieder mit einer Umwandelung habe ich Problem (diesmal von char Array zu char) Java Basics - Anfänger-Themen 1
J Problem bei Umrechnung von Hex in Bin Java Basics - Anfänger-Themen 4
W Problem bei Programmierung von Monte-Carlo-Integration Java Basics - Anfänger-Themen 12
C Java Methoden "Parameter" Problem Java Basics - Anfänger-Themen 16
T Bruchrechner Problem Java Basics - Anfänger-Themen 16
M Problem mit meinem Programm Java Basics - Anfänger-Themen 6
pkm Problem mit der JSP-Syntax Java Basics - Anfänger-Themen 2
J Rückgabe-Problem Java Basics - Anfänger-Themen 10
D Problem mit der Serialisierung Java Basics - Anfänger-Themen 31
W Problem mit dem Wert von boolean-Variable Java Basics - Anfänger-Themen 3
W Problem mit Konsolenausgabe bei StringTokenizer Java Basics - Anfänger-Themen 2
O Verständniss Problem bei abstract class Java Basics - Anfänger-Themen 7
K Java Problem mit Übergabe von argumenten Java Basics - Anfänger-Themen 3
M Problem mit ArrayList Java Basics - Anfänger-Themen 32
B Array Problem Java Basics - Anfänger-Themen 3
O Problem mit SOAP / javax.xml importieren Java Basics - Anfänger-Themen 7
V Variablen Problem mit Matheaufgabe / int first = mScanner.nextInt(); Java Basics - Anfänger-Themen 5
X Problem mit Arraylist in Arraylist Java Basics - Anfänger-Themen 2
cpt.Tomato Scanner problem mit Passwort Login Java Basics - Anfänger-Themen 3
F Switch Case Problem mit Regex lösen? Java Basics - Anfänger-Themen 6
CT9288 Mini Anfänger-Problem mit loops, statements und ; Java Basics - Anfänger-Themen 4
C Two-Center Problem in Java Java Basics - Anfänger-Themen 0
H regex-Problem Java Basics - Anfänger-Themen 2
J Problem bei seriellem Start von Threads Java Basics - Anfänger-Themen 11
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
C Problem: PC ohne Internet und keine Möglichkeit Programme zu laden Java Basics - Anfänger-Themen 5
E Problem mit static Methode Java Basics - Anfänger-Themen 4
J Problem bei Aufgabe "Geldstückelung" Java Basics - Anfänger-Themen 5
P Problem bei Java-Aufgabe Java Basics - Anfänger-Themen 12
T Rückgabewert Problem Java Basics - Anfänger-Themen 2
O Problem gleiche Zahlen Java Basics - Anfänger-Themen 2
C Methoden Problem beim Speichern von Variablen Java Basics - Anfänger-Themen 1
W Problem bei JUnit Test Aufgabe Java Basics - Anfänger-Themen 15
D Break Sprungmarken Problem einer While True in While True Java Basics - Anfänger-Themen 6
J "Tetris" - Problem bei der Grafik Java Basics - Anfänger-Themen 5
L Klassen NFC Reader und JavaFx Problem -> threads? Java Basics - Anfänger-Themen 2
C Hamster Simulator Problem Java Basics - Anfänger-Themen 2
S CSV auslesen UTF-8 Problem Java Basics - Anfänger-Themen 7
F Problem beim entfernen von mehreren Listenelementen auf einmal (Programmierung des Spiels Arschloch) Java Basics - Anfänger-Themen 1
felix92 eclipse Problem Java Basics - Anfänger-Themen 12
J unzip Problem Java Basics - Anfänger-Themen 5
J Pizza und Pasta Problem.. Java Basics - Anfänger-Themen 19
F Problem mit der Aufgabe(Array) Java Basics - Anfänger-Themen 21
X Erste Schritte Problem mit scanner Java Basics - Anfänger-Themen 2
J GUI-Problem Java Basics - Anfänger-Themen 4
C Problem mit der Aufgabe Java Basics - Anfänger-Themen 3
L Problem mit Android ListView Java Basics - Anfänger-Themen 2
J String Problem kann das einer erklären Java Basics - Anfänger-Themen 13
R Schaltjahr problem Java Basics - Anfänger-Themen 10
S Doppel For Schleife mit Arrays - Problem bei der Ausgabe Java Basics - Anfänger-Themen 4
R Problem mit Code Java Basics - Anfänger-Themen 3
scitex Problem mit JFormattedTextField Java Basics - Anfänger-Themen 2
D Problem mit Installation von JRE Java Basics - Anfänger-Themen 2
_0815_ Problem mit dem Automatischen eintragen in Textdateien Java Basics - Anfänger-Themen 1
L PROBLEM! "Bug" bei Konto-Projekt! Java Basics - Anfänger-Themen 7
H boolean Array Problem Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Anzeige

Neue Themen


Oben