# Traveling Salesman Problem



## KenTry (3. Nov 2012)

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 (3. Nov 2012)

KenTry hat gesagt.:


> 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.




KenTry hat gesagt.:


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



Wenn nicht du, wer dann?


----------



## turtle (3. Nov 2012)

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 (3. Nov 2012)

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 (3. Nov 2012)

```
class TSP
{
    Trip compute(Location source) { ... }
}
```
?! :bahnhof:


----------

