Streckenaddition eines Handelsvertreters

Neue Frage »

RudisehrRatlosXXL Auf diesen Beitrag antworten »
Streckenaddition eines Handelsvertreters
Ein HV hat 10 Kunden zu besuchen.

a) Wie viele Möglichkeiten gibt es, diese Tour durchzuführen?

Meine Antwort: 10!

b) Wie viele Additionen von Streckenlängen sind nötig, um die kürzeste Rundstrecke zu finden?

Meine Ideen: Route 1-2-3-4-5-6-7-8-9-10-1 beinhaltet 10 Streckenadditionen (Strecke12 + Strecke23 + Strecke34 + ... + Strecke 10 1

Es gibt 10! verschiedene Routen, also 10! mal 10 Streckenadditionen

Das kann ich jedoch gleich wieder durch 10 teilen, da man ja auch mit der Station 2, 3 usw. anfangen könnte und so wäre 2-3-4-...10-1-2 identisch mit der ersten Variante.

Also bin ich wieder bei 10! Additionen.

Diese teile ich durch 2, weil ja die Umkehrrichtung einer Rundreise identisch wäre.

Also gibt es 10! : 2 Streckenadditionen?

verwirrt

Danke für Bestätigung oder hilfreiche Tipps

Ergänzung: Diese Lösung: Kombinatorische Probleme

finde ich eben nicht richtig...
RudisehrRatlosXXL Auf diesen Beitrag antworten »
RE: Streckenaddition eines Handelsvertreters
Warum gibt es keine Antwort?? unglücklich
 
 
Huggy Auf diesen Beitrag antworten »
RE: Streckenaddition eines Handelsvertreters
Zitat:
Original von RudisehrRatlosXXL
Warum gibt es keine Antwort?? unglücklich

Keine Ahnung. Ist vielleicht zu schnell nach hinten gerutscht.

Deine Überlegungen sind richtig. Allerdings lässt sich die Zahl der benötigten Additionen weiter reduzieren. Arbeitet man z. B. zunächst alle Wege ab, die mit 1->2->3 beginnen, so braucht man für diese Wege die Strecken 1-2 und 2-3 ja nur einmal zu addieren.
Dopap Auf diesen Beitrag antworten »

Man unterscheidet symmetrisches TSP (kurz: keine Einbahnstrassen !) und asymmetrisches TSP.

1.) Beim symmetrischen TSP gibt es 9!/2 Wege gleicher Länge.

[attach]47127[/attach]

symmetrisches Modell mit 4 Knoten


2.) beim asymmetrischen TSP gibt es 9! Wege gleicher Länge.


Dein Problem der Anzahl der Additionen ist davon unberührt, aber mMn in Ordnung.
RudisehrRatlosXXL Auf diesen Beitrag antworten »

Zitat:
Original von Dopap
Man unterscheidet symmetrisches TSP (kurz: keine Einbahnstrassen !) und asymmetrisches TSP.

1.) Beim symmetrischen TSP gibt es 9!/2 Wege gleicher Länge.

[attach]47127[/attach]

symmetrisches Modell mit 4 Knoten


2.) beim asymmetrischen TSP gibt es 9! Wege gleicher Länge.
Das habe ich jetzt nicht so gaaaanz verstanden...

Aber

Zitat:
Original von Dopap
Dein Problem der Anzahl der Additionen ist davon unberührt, aber mMn in Ordnung.


Darüber freue ich mich jetzt mal!
Danke! Freude
Dopap Auf diesen Beitrag antworten »

besser:
es gibt ... Routen die sich in der Länge der Route unterscheiden.
Neue Frage »
Antworten »



Verwandte Themen