mikrocontroller.net

Forum: PC-Programmierung travelling salesman problem


Autor: hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hallo an alle!

Wir müssen uns für die Schule mit dem travelling salesman problem 
außeinander setzten bzw. mit einem Lösungsalgorithmus von Held & Karp 
und diesen in C++ realisiern. Da meine Frage kennt jemand eine Seite 
oder etwas wo man sich darüber informieren kann, denn allzu viel hab ich 
im Internet noch nicht gefunden was ich brauchbar verwerten konnte 
verstand meistens nur bahnhof.

Mit freundlichen Grüßen und Dank im voraus
Hans

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hans schrieb:
> oder etwas wo man sich darüber informieren kann, denn allzu viel hab ich
> im Internet noch nicht gefunden was ich brauchbar verwerten konnte
> verstand meistens nur bahnhof.
Aha... und wir sollen dir das jetzt was hunderte Leute schon beschrieben 
haben nochmal beschreiben ohne zu wissen was du nicht verstanden hast?

Autor: Andreas Kanzler (scavanger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Da kann man aber nun wirklich selber draufkommen...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm.
Für den spezifischen Lösungsansatz von Held und Karp findet sich 
tatsächlich nur sehr wenig im Web (zumindest mit den naheliegenden 
Suchbegriffen). Bisher hab ich nur eine Referenz gefunden, die sich 
zumindest soweit herablässt zu verraten, dass man dabei eine ganze Menge 
'Minimum Spanning Trees' aufbauen muss. Aber Details: Fehlanzeige

Autor: hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
die seite von wiki hab ich natürlich gesehen sowie jede menge andere von 
neuronalen netzen (hopfield) usw aber da wir eigl bisher nur die 
oberfläche und grundbegriffe von c++ angekratzt haben find ich es 
sowieso ein starkes stück das wir das machen müssen..

was ich bisjetzt habe ist das einlesen von städten bzw deren koordinaten 
das umwandeln in dezimal zahl das durch spielen aller möglichkeiten und 
die distanzberechnung mittels wgs84 ellipsoid. start und endpunkt sind 
eben gleich jeder ort einmal und funktioniert soweit gut nur halt bis ca 
14 orte.. danach dauerts schon ganz schön lang deswegn müssen wir jetzt 
das schneller machen..

vom lehrer vorgeschlagen eben held und karp (weiß sonst jemand literatur 
was man eventuell in einer bibliothek finden könnte?) und was ich nicht 
verstehe ist eigl alles ich weiß nicht wie ich das problem anpacken soll 
verstehe auch diese ansätze mit den neuronalen netzten nicht oder die 
schnittebenen usw

deswegn wäre ich über jeden kleine hinweis glücklich

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also ich weis ja nicht wie, womit oder wonach Ihr sucht.
Google liefert mehrere tausend Treffer.
Unter anderem auch:
http://www.cse.wustl.edu/~chen/7102/Karp-TSP.pdf

Man kanns auch mal via http://scholar.google.de probieren.

Und wenn man in der Wikipedia mal den Links folgt, landet man z.B. hier:
http://www.tsp.gatech.edu/concorde/index.html
Da kann man sich den Sourcecode runterladen und mal ins "HELDKARP" 
Verzeichnis schauen.

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... oder auch mal hier reinschauen:
http://www.cs.utoronto.ca/~neto/research/lk
Da drin ist Held&Karp wohl auch implementiert.

Autor: hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
danke der erste nützt mir jetzt mal schon einiges dort kann ich 
zumindest mal reinlesen.. gestern abend hab ich es noch fertig gebracht 
mir den minimum spanning tree zu konstruieren jetzt mal dort reinlesen 
und hoffentlich herausfinden wies weiter geht

Autor: Klaus (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Groß und Kleinscheibung beachten und Satzzeichen benutzen erhöht die 
Lust der Forenteilnehmen deinen hingekotzen Text auch zu lesen...

Die Forenregeln schrieben:
> Wichtige Regeln - erst lesen, dann posten!
>
> Groß- und Kleinschreibung verwenden

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.