Formulierungsproblem: Optimale Tour darf sich nicht überkreuzen

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?

pli

http://www.algo.informatik.tu-darmstadt.de/lehre/2004ws/graphalgo/
Ganz gutes Skript zum Thema Graphenalgos, wenn auch nicht sehr ausfuerhlich. Vll kann dir das helfen.