0 Daumen
468 Aufrufe

Ich lese ein Buch mit dem Titel Komplexitätstheorie. Als Beispiel für ein Problem wird das Traveling Salesman Problem kurz erklärt. Folgender Satz ist dann exakt so zu finden (bzgl. den Distanzen zwischen den einzelnen Orten):

Die Distanzen stammen aus ℕ ∪ {∞}, wobei der Wert ∞ andeutet, dass es keine direkte Verbindung zwischen den betrachteten Orten gibt.

Also meinem Verständnis nach bedeutet diese Vereinigung ja einfach, dass für die Distanzen alle natürlichen Zahlen und "Unendlich" eingesetzt werden kann. Soweit so gut. Aber diese Erklärung des Autors, dass "Unendlich" hier andeutet, dass es da keine direkte Verbindung zwischen den Orten geben soll, verstehe ich einfach nicht.


Was soll in diesem Kontext denn "direkt" oder "indirekt" sein? Wie kann ich das mit der Unendlichkeit dann herleiten? 

Avatar von

2 Antworten

+1 Daumen
dass "Unendlich" hier andeutet, dass es da keine direkte Verbindung zwischen den Orten geben soll

Man hätte auch jedes andere Zeichen, das keine natürliche Zahl bezeichnet, verwenden können. Zum Beispiel -1 oder ♫ oder ♥. Der Autor hat sich dagegen entschieden und verwendet stattdessen das Zeichen ∞.

Was soll in diesem Kontext denn "direkt" oder "indirekt" sein?

direkt: Man kommt von A nach B ohne das man einen dritten Knoten besuchen muss.

indirekt: Man kommt von A nach B indem man mindestens einen weiteren Knoten besucht.

Wie kann ich das mit der Unendlichkeit dann herleiten?

Herleiten kann man das nicht. Man kann höchstens begründen, warum man sich dafür entschieden hat, für den Sachverhalt "Es gibt keine direkte Verbindung zwischen A und B" das Zeichen ∞ zu verwenden, und eben nicht -1, ♫ oder ♥. Die Begründung wäre dann so etwas wie "Das Zeichen ∞ hat üblicherweise die Bedeutung 'Unendlich' und es dauert unendlich lange um direkt von A nach B zu kommen, weil man nie ankommt."

Avatar von 107 k 🚀
+1 Daumen

Wie kann ich das mit der Unendlichkeit dann herleiten? 
"Herleiten"  kannst du das gar nicht. Das ist einfach eine Annahme in

dem Modell, und das ist ja auch ganz sinnvoll. Denn es soll ja der kürzeste

Weg gefunden werden und wenn von A nach B gar kein Weg existiert, dann

kann der Salesman nicht unmittelbar (also ohne Zwischenstationen über

andere Orte) von A nach B reisen und statt:

"Der Weg ist nicht vorhanden" kann man ja auch sagen:

"Er ist unendlich lang" kommt also für eine möglichst kurze Rundreise

nicht infrage.  Da vermutlich alle Entfernungen durch eine

Matrix verwaltet werden, muss aber ein Eintrag für den

Weg von A nach B in der Matrix sein, also kommt da ∞ hin.

Avatar von 289 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community