Hamiltonkreisproblem

[Lord Adler]

Hallo zusammen ,
wollte fragen, ob mir jmd 'nen Tipp zur folgenden Aufgabenstellugn geben könnte.

Meine Aufgabe ist es die weiter unten stehenden Koordinaten so mit einander zu verbinden, dass die kürzeste Strecke bei rauskommt. Ich sollte da die Hamiltonkreismethode anwenden, hab aber absolut keine Idee, wie ich diese in Java ausdrücken bzw. anwenden soll...
Wäre nett, wenn mir da jemand helfen könnte, thx!

MfG Lord Adler

PS, hier die Koordinaten in einem 2 dimensionalem Array:

int[][] punkte = {
{428,512},
{828,2083},
{2750,1105},
{3120,2605},
{17108,3900},
{2507,2360},
{3690,3820},
{935,2010},
{1953,1826},
{3006,4105},
};

 

[torsch2711]

Hallo,

sop jetzt erstmal kurz eine kleine Zeitreise zurück ins 4.te Semester machen

Boom, und schon auf die nase gefallen: Bitte ersetze die Kanten durch knoten, es war genau anders herum!

Also es gibt Hamiltonkreise und es gibt Eulerkreise (hoffentlich stimmt das noch )
Bei hamiltonkreisen haben die kanten eine gewichtung (bei euler die knoten). Ich glaube in deinem Falle wäre die gewichtung der kanten immer 1.

Das vorgehen wäre jetzt folgendes. Du nimmst alle kanten die du hast (falls ich da gerade eulerkreise und hamiltonkreise verwechsele, nimm die punkte statt kanten). Du gehst von deinem ausgangspunkt jetzt die kante mit der niedrigsten gewichtung (in unserem falle ja eh alle 1) und nimmst diese aus der menge heraus. und merkst dir an deinem weg, die länge 1. jetzt musst du schauen, welche kanten an deinen punkt anstossen. da nimmst du wieder die mit der geringsten gewichtung. und so geht es immer weiter.

Aber um den kürzesten weg zu finden musst du Backtracking machen, da nicht immer die kleinste kante die anstösst auch den kürzesten weg verspricht.
Backtracking bedeutet, dass du auch einen schritt zurückmachen musst und einen anderen weg einschlägst.

Ich glaube, das Resultat eines Hamiltonkreises war der minimale Spannbaum, was die kürzeste Strecke (sprich die strecke mit der geringsten gewichtung repräsentiert!).


Ich setze hier mal ein paar links zu den Hamiltonkreisen auf:

Algorithmus Branch and Bound: http://fuzzy.cs.uni-magdeburg.de/studium/graph/txt/keutel.pdf

Algorithmus: http://www-lehre.inf.uos.de/~graph/skript/Hamiltonkreis.html


Ich hoffe das hilft dir.

Gruss Torsten