Traveling Salesman

[Gast]

Kann mir bitte einer in einfachen Worten erklären, wie man z.B. beim Traveling Salesman Problem ausrechnet, wie viele Möglichkeiten es für eine Anzahl n von Städten und Wegen gibt? Ich steh gerade voll auf dem Schlauch!

[Pinoccio]

Kann mir bitte einer in einfachen Worten erklären, wie man z.B. beim Traveling Salesman Problem ausrechnet, wie viele Möglichkeiten es für eine Anzahl n von Städten und Wegen gibt? Ich steh gerade voll auf dem Schlauch!Maximal (n-1)!. Im Ersten Schritt hats du (n-1) mögliche Ziele, im zweiten (n-2) usw. Wenn nun nicht jede Stadt mit jeder Verbunden ist, werden es weniger Kombination.

mfg Sebastian

[Monger]

Angenommen du hast 4 Städte die dein Handelsvertreter besuchen muss. Jede Stadt hat jeweils eine kürzeste Route zu jeder anderen Stadt.

Vorausgesetzt du hast zwischen jeder Stadt die jeweils kürzesten Routen berechnet (was ja eigentlich das wirkliche Problem der Wegfindung ist), wählst du dir eine Stadt als Anfangsstadt. Von da aus hast du drei mögliche Wege, weil du noch drei verbleibende Städte hast. Wenn du eine weitere Stadt festlegst, verbleiben dir noch zwei weitere Städte, und zuletzt noch eine.


Lange Rede, kurzer Sinn: Dein Aufwand beträgt O( n) -> (n-1)!

(Wie immer bitte ich die anderen Leser dieses Forums, meinen soeben verzapften Schwachsinn zu korrigieren.)

[Gast]

Ah, danke!

Also hätte ich bei 6 Städten bereits (6-1)! also 120 Möglichkeiten?

Hab ich das so richtig verstanden? Und wie wäre es, wenn jede Stadt mit jeder verbunden wäre? (n)!?

[Neomi]

Hab ich das so richtig verstanden? Und wie wäre es, wenn jede Stadt mit jeder verbunden wäre? (n)!?

Das ist bereits der Fall, in der jede Stadt mit jeder anderen verbunden ist. Die Zahl der möglichen Wege ist von einer Stadt aus (n-1)!. Wenn man von jeder beliebigen Stadt aus starten kann, gibt es n! Möglichkeiten insgesamt.

[Monger]

Ah, danke!

Also hätte ich bei 6 Städten bereits (6-1)! also 120 Möglichkeiten?

Hab ich das so richtig verstanden? Und wie wäre es, wenn jede Stadt mit jeder verbunden wäre? (n)!?

Eine Stadt braucht nicht mit sich selbst verbunden zu sein, deshalb gibt es maximal n-1 Wege. Aber ich denke, ansonsten hast du es verstanden.