tsp-aenlich problem

dion

hallo...
ich muss dieses problem loschen:
ich bekomme eine landkarte mit N staedte. ich muss strassen machen, so dass alle staedte miteinander angeloscht sind, aber die strassen sind so gleich vie mueglich.

beispiel:
wir haben 4 staedte und:
stadt 1 ist 5km weit von stadt 4
stadt 1 ist 2km weit von stadt 3
stadt 5 ist 8km weit von stadt 3
stadt 5 ist 15km weit von stadt 1
stadt 4 ist 4km weit von stadt 3
stadt 2 ist 5km weit von stadt 5
stadt 2 ist 3km weit von stadt 3
stadt 5 ist 2km weit von stadt 4

wir mussen konstruieren:
2 -> 5
2 -> 3
3 -> 4
1 -> 3

so kann man von jede stadt a zu eine stadt b gehen, und wir haben die minimum strassen gebaut.

ich muss ein algorithm finden, um solche probleme zu loschen.
gibts ein bestimter name fur dieses problem? ich hab gesucht aber nights gefunden.

ich hab gedacht um die kleinste strassen su bauen, bis alle staedte verbunden sind, aber in mine tests das ist nicht immer die beste anword.

irgend eine idee?

Jester

Ich werde nicht ganz schlau aus dem was Du schreibst. Kann es sein, dass es sich um ein MST-Problem(Minimum-Spanning-Tree) handelt?

Vellas

Hi!

TSP ist das "travelling salesman problem". Dabei geht es darum, alle gegebenen Punkte einmal zu besuchen und anschließend zum Startpunkt zurückzukehren.
@dion:
Hier hast du ein paar Links mit Algorithmus-Vorschlägen:
http://en.wikipedia.org/wiki/Travelling_salesman_problem
http://members.pcug.org.au/~dakin/tsp.htm
http://www.jochen-pleines.de/

Greetz

Jester

Vellas: das ist zwar nett, hat aber mit seiner Frage wohl nix zu tun. Was das TSP ist weiß ich auch, aber er hat da was anderes beschrieben.

dion

@Jester: ich wollte eigent wissen wie das Problem heisst. Ich dachte das wurde eine sorte von TSP sein, des wegen habe ich "tsp-aenlich problem" geschrieben. Deine anwort hat mir sehr geholfen. Vielen Dank.

@Vellas: Vielen Dank, aber meine Frage war uber das Problem dass ich bescrieben hab. Ich hab nur TSP gesagt, denn ich dachte, dass es etwas mit TSP zu tun hat.

So, ich werde von hier beginnen und weiter lessen:
http://en.wikipedia.org/wiki/Minimum_spanning_tree

Alle vorschlagen um etwas anderes su lesen wurden mir sehr helfen

Vellas

Hab mir den Link zu Wikipedia nicht angesehen (bzw. nur kurz überflogen), aber da ein Buch für dich vielleicht schon wieder zuviel wäre, solltest du bei google oder so mal gucken. Da im Wiki-Artikel bestimmt auch bestimmte Algorithmen genannt werden, kannst du dort sonst auch gut gezielt nach welchen Suchen.
Eine Seite die ganz gut aussah ist diese:
http://www.people.vcu.edu/~gasmerom/MAT131/mst.html

Greetz

dion

vielen vielen dank
vielleicht kaufe ich auch ein Buch, aber noch nicht. In ein paar Tagen..

C++ Forumbot

Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

1

Zeus

Ja ist ein MST-Problem