hallo!

geht ja echt schnell mit euch...!! großes dankeschön schonmal...!!

erstma@Gausi:
hab ja nie gesagt,dass es ne hausaufgabe is...das hat BenBE (indirekt) gesagt!
es is mehr 'n projekt...haben da mehrere wochen für zeit
und ja,es ist das kürzeste-Wege-Problem!

ich weiß ja auch schon ne menge darüber,u.a. welche lösungsarten es gibt...
z.b. branch & cut,kleinster aufspannender baum
das prinzip dieser lösungswege habe ich ja verstanden,ich
weiß halt nur nich,wie man es in delphi programmiert...

und hierbei brauche ich eure hilfe ^^

ps: ich schau mir grad den link von tilo an...vllt is ja was dabei! =D

ok, dann für ein Projekt.

Branch&cut sagt mir jetzt nix, aber kleinster spannender Baum hat AFAIK nichts mit dem kürzesten Wege-Problem zu tun. Beim MinimalenSpannBaum möchte man erreichen, dass alle Knoten zwar miteinander verbunden sind, aber es keine "Kreise" in dem verbleibenden Graphen gibt. Die Kantensumme in dem Baum soll dabei minimal sein.

Für kürzesteWege würde ich mal nach Dijkstras Algorithmus suchen. Der ist dafür genau das richtige.

Zur Implementierung in Delphi: Das Hauptproblem ist dabei die Verwaltung des Graphen. Du mußt dir eine Datenstruktur TGraph erstellen, in der Knoten und Kanten gespeichert sind. Dabei hat eine Kante einen Start- und einen End-Knoten, sowie eine gewisse Länge. Außerdem benötigst du an den Objekten Kante und Knoten diverse Flags/Markierungen. Stichworte für die Darstellung des Graphen sind dann Adjazenzliste oder Adjazenzmatrix, wobei man die Listenstruktur auch implementieren muss (oder man nimmt TList oder so)

Oder hast du schon die Datenstruktur Graph implementiert? Dann fällt ein Großteil der Arbeit nämlich weg...


Aber ein Kommentar noch: Finden die Lehrer es eigentlich cool, wenn man das einfache "kürzeste Wege Problem" mit Traveling Salesman bezeichnet? Kannst ja mal danach fragen...

Evtl. könntest du den aus diesem Tutorial stammenden Sourcecode modifizieren. Auf alle Fälle ein Anfang, Datenstruktur und Darstellung steht dann bereits.

Cu,
Udontknow

jo danke!!
ihr habt mir schon sehr weitergeholfen!!
das TSP und was damit zusammenhängt hab ich ja schon verstanden...
das blöde is nur...mit dem programmiern hab ichs nich so
wisst ihr vllt,wo es tutorials oder hilfen (vllt auch quelltexte...muss aber nicht sein)
gibt,wie man sich bei delphi zufällige punkte generieren lässt?

thx im vorraus!
bis dann
Showtime

jo danke!!
ihr habt mir schon sehr weitergeholfen!!
das TSP und was damit zusammenhängt hab ich ja schon verstanden...
das blöde is nur...mit dem programmiern hab ichs nich so
wisst ihr vllt,wo es tutorials oder hilfen (vllt auch quelltexte...muss aber nicht sein)
gibt,wie man sich bei delphi zufällige punkte generieren lässt?

thx im vorraus!
bis dann
Showtime