WIE komme ich auf dieses Ergebnis mit Überlegungen der Kombinatorik und dem Urnenmodell?

Question

Aufgabe:

Erklärung des symmetrischen Traveller Salesman Problem mit Überlegungen aus der Kombinatorik und dem Urnenmodell

Problem/Ansatz:

Bei dem symmetrischen Traveller Salesmen Problem mit z.B. n = 15 Städten, gibt es (n-1)!/2 Rundreisen. WIE komme ich auf dieses Ergebnis mit Überlegungen der Kombinatorik und dem Urnenmodell?

KONKRETER, beispiel: werden alle Kugeln gezogen?

Z.B Ja (ohne zurücklegen) Permutation P =n! Möglichkeiten

Werden nicht alle Kugeln gezogen?

--> Variation oder Kombination--> Reihenfolge wichtig? Z.B ja

VARIATION Z.B OHNE ZURÜCKLEGEN

V =n!/ (n-k)!

D.h. wie komme ich von den Kombinatorik Formeln auf die oben angegebene Lösung? DANKE VORAB ICH HOFFE ICH HABE DAS PROBLEM VERSTÄNDLICH FORMULIERT ..

Comments

vgl:

https://mathepedia.de/Problem_des_Handlungsreisenden.html

https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Answer 1

ICH HOFFE ICH HABE DAS PROBLEM VERSTÄNDLICH FORMULIERT

Hoffnung ist eine schöne Sache. Majuskeln manchmal auch.

Wenn Du an irgendeinem Ort mit der Rundreise anfängst, gibt es n-1 Orte für den zweite Destination, dann n-2 Orte für die dritte Destination, usw. Und dann davon die Hälfte, weil das TSP ja symmetrisch sein soll, es also nicht auf die Reiserichtung ankommt.

Comments

Danke für die Antwort, diesen Teil hatte ich verstanden...es geht mir darum, ob man das Ganze auf das Urnenmodell projezieren kann (falls möglich), und welcher Fall es dann wäre, um von den allgemein gültigen Kombinatorik Formeln auf die spezifische Lösung des TSP zu kommen (n-1)!/2

Answer 2

Ich würde es NUR mit der Permutation erklären, also n! - und die (n-1) aus der Begründung, daß der "Ausgangsort" schon fix ist.

Comments

Dh Permutation mit einem fixen Ort erklärt (n-1)! = 14!. OK, und die 2 im Nenner? Dadurch dass das symmetrisch ist :-) Gut danke, ich glaube auch nicht dass es eine bessere Erklärung gibt. Die 2 hatte mich verwirrt, weil ich dachte, dass es ja dann um die Reihenfolge geht, weil man ja dann sagt die Distanz von bspw Punkt C nach Punkt D ist gleich mit D nach C. ABER die Entscheindung beeinflusst ja auch den vorherigen Weg Z.B. BC oder BD :-) Super danke!