Formulierungsproblem: Optimale Tour darf sich nicht überkreuzen

TheToast

Hi,

ich arbeite grade an dem Problem des Handlugnsreisenden, und ich weiß, dass sich die Optimale Tour nicht überkreuzen darf, denn wenn man diese Überkreuzung auflöst und "im Kreis" wieder verbindet, ergibt das immer eine kürzere Route, ich weiß im Prinzip wieso das so ist, aber wenn ich das so hinschreibe gibt das sicherlich Abzüge, wegen der Formulierung.

Ich will nicht, das irgendjemand meine Hausaufgabe macht, ich brauch nur irgendeinen Ansatz, vielleicht gibts da eine Mathematische egel für, mit einem Namen oder so...

TGGC

Offensichtlich ist das eine schlechte Formulierung, denn ich kann mir beim besten Willen nicht vorstellen, was du meinst!?

Bye, TGGC (Keine Macht den Dummen)

Hmm... es tut mir leid, aber ich muss TGGC zustimmen...

BF_31

Ich verstehe es zwar auch nicht, aber für alle nachfolgenden Poster die sich mit dem Problem beschäftigen wollen:

MSN-Suche

TheToast

Okay, da habt ihr schon das Problem...

Okay, hier ein Bild:

http://thetoast.cybton.com/problem.gif

Ich hoffe, das Problem wird klar, die nicht überkreuzende Strecke ist ganz offentsichtlich die kürzere, aber wie erklär ich das?

ser1al

Und warum ist das so?

TGGC

Wer sagt das, diese Strecke kürzer ist? Wer sagt, das für den 2. Fall Kanten existieren müssen? Ein Graph definiert keine Anordnung in der Ebene, also kann ich quasi jeden Graph so aufzeichnen, das sich etwas "überkreuzt" (bzw. überkreuzen muss), nach deiner Definition.

BTW: Kann es sein, das du die Graphentheorie nicht so ganz verstanden hast?

Bye, TGGC (Wähle deine Helden)

Hmmm, wenn die beiden Punkte nah aneinanderliegen, könnte die 'Kreuzung' der kürzere Weg sein - weil Du dann von A nach B nur Innenkurve fährst. :p

finix

TheToast schrieb:

Ich hoffe, das Problem wird klar, die nicht überkreuzende Strecke ist ganz offentsichtlich die kürzere, aber wie erklär ich das?

Ich denke die "Formulierung" die du suchst hat etwas mit planaren Graphen zu tun.

Du solltest dir allerdings TGGCs Einwände nochmal anschauen.
Und vor allem Stichworte wie "Gewicht" und "gerichtet" nicht von deinen Nachforschungen ausschließen...

Richtig. In unserer Stadt gibt es drei Punkte A,B,C.
Die Hypothenusenstrecke AC ist auf einem Gesamtweg von ca. 10 km letztlich tatsächlich 700 m länger als über die Tangenten AB-BC, weil sie derart kurvenreich ist.
Es kommt also wirklich drauf an, ob Dein Problem ein rein Abstraktes ist, oder doch einen Bezug zu einem wirklichen Tourenproblem hat.
Im zweiten Fall gehst Du zu naiv ran...

TheToast

Also es ist rein abstrakt, bei mir zählt tatsächlich Gewicht ist die Länge und ich meinte anscheinend einen planaren Graphen... Es geht also wirklich um Luftlinie.

Ich kenn mich halt nicht so damit aus...

Und zu Bitsy: Innenkurven zählen nicht

Das mit dem überkreuzen hatte ich auch irgendwo gelesen, ich finds nur grade nichtmehr...

Also bitte für nächste Antworten beachten: Rein Abstrakt und Gewicht entspricht der Länge

Ein Graph:

A +--------+ B
   \      /
    \    /
     \  /
      \/
      /\
     /  \
    /    \
   /      \
C +--------+ D

Kürzeste Rundereise überschneidet sich (nach deiner Definition).

Bye, TGGC (Wähle deine Helden)[/quote]

TheToast

Ist in diesem Fall Strecke ABDCA nicht kürzer?

Ok, ich kanns einfach nicht genau definieren, man möge mir verzeihen...

Wenn jemand versteht, was ich meine, dann möge er mir antworten...

TheToast schrieb:

Ist in diesem Fall Strecke ABDCA nicht kürzer?

Zwischen B und D besteht keine Kante. Daher keine gültige Lösung.

Bye, TGGC (Keine Macht den Dummen)

TheToast

Ok, dann kommt für TGGC noch dazu: Kanten gibt es zwischen allen Orten.

Kann noch bitte jemand alle meine Beiträge auf Rechtschreibfehler überprüfen?

finix

TGGC|^work schrieb:

Ein Graph:
A +--------+ B
   \      /
    \    /
     \  /
      \/
      /\
     /  \
    /    \
   /      \
C +--------+ D
Kürzeste Rundereise überschneidet sich (nach deiner Definition).

Mathematisch gesehen immer noch ein planarer Graph

finix

TheToast schrieb:

Ok, dann kommt für TGGC noch dazu: Kanten gibt es zwischen allen Orten.

Stilvoller: es ist ein vollständiger Graph.

TheToast

finix schrieb:

Stilvoller: es ist ein vollständiger Graph.

Gut, das mein ich, danke

Du musst das schon genau definieren, sonst kann das keiner wissen. Die Sprache ist viel redundanter als Mathematik, daher kannst die den rechtschreibvergleich sparen.

Zu deiner Behauptung: Stimmt wegen Dreiecksungleichung. Hat mit Graphentheorie nichst zu tun.

Bye, TGGC (Keine Macht den Dummen)

TheToast

TGGC|^work schrieb:

Du musst das schon genau definieren, sonst kann das keiner wissen. Die Sprache ist viel redundanter als Mathematik, daher kannst die den rechtschreibvergleich sparen.

Zu deiner Behauptung: Stimmt wegen Dreiecksungleichung. Hat mit Graphentheorie nichst zu tun.

Bye, TGGC (Keine Macht den Dummen)

Die Rechtschreibung war nur ein Scherz.

Das war unter anderem mit meiner Frage gemeint, was genau das ist, und wie und wo das Problem definiert ist oder in welchen Bereich das gehört. Hätt ich das genauer definieren können und beschrieben können, wär meine Frage irgendwie sinnlos geworden...

Ok, ich weiß, was die Dreiecksungleichung ist, aber wie genau kann man die darauf anwenden? Ist der Punkt der Kreuzung dann der, der der langen Seite gegenüber liegt?