Traveling Salesman Problem

[KenTry]

Hallo alle Zusammen,

ich habe hier eine Aufgabe zum Traveling Salesman Problem und ich habe ein paar Probleme:
Ich habe mir erstmal drei Klassen erstellt:

Location --> Dort möchte ich die Punkte speichern
Trip --> Dort möchte ich die vordefinierten Reiserouten stecken
TSP --> Dort möchte ich später die Berechnung

Jetzt mein erstes Problem:
Welche Methoden gebe ich welcher Klasse (erstmal nur die Methodenköpfe, den Code versuche ich dann selber) ?

Mein Problem ist, dass ich nicht weis wie ich anfangen soll 🙁

Ich würde mich sehr freuen wenn ihr mir ein paar Tipps geben könnt 🙂

Mfg KenTry

 

[Jango]

Jetzt mein erstes Problem:
Welche Methoden gebe ich welcher Klasse (erstmal nur die Methodenköpfe, den Code versuche ich dann selber) ?

Das Eine schließt das Andere ein...
Papier und Bleistift nehmen und ein Konzept erstellen. Danach in Code umsetzen.

Mein Problem ist, dass ich nicht weis wie ich anfangen soll 🙁

Wenn nicht du, wer dann?

 

[turtle]

Traveling Saleman Problem?

Da gibt es tausende Links, mit Quellcode (z.B. Travelling salesman problem - Wikipedia, the free encyclopedia)
Das ist ein NP-vollständiges Problem und daher die korrekte, optimale Lösung, "nur" für kleine Graphen lösbar. Eine optimale Lösung kann leicht über brute-force Methoden, also Erzeugung ALLER möglichen Wege und Suchen des kürzesten Weges lösbar.

 

[Helgon]

Hab mir grad den Wiki Artikel angeschaut und erinnert mich ein wenig an den *-Algo

A* search algorithm - Wikipedia, the free encyclopedia

Vielleicht hilfts

 

[Marco13]

class TSP
{
    Trip compute(Location source) { ... }
}

?! :bahnhof: