Formulierungsproblem: Optimale Tour darf sich nicht überkreuzen

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.