Mathematische Magie - Lösen des Problems des reisenden Zauberers [geschlossen]

Dies ist zum Teil das Ergebnis eines unglücklichen Austauschs auf Worldbuilding Meta :

@HDE226868 hahahaha. Keine Mathematik erlaubt. – James gestern

Ich werde einen Weg finden! – HDE 226868 gestern

Ich denke ich habe.

Dies basiert auf dem Problem des Handlungsreisenden , bei dem es darum geht, die kürzeste Entfernung zwischen einer bestimmten Anzahl von Punkten zu finden. Das ist, wie Mathematiker schnell herausfanden, viel schwieriger als es scheint.

Das Szenario:

In einer mittelerdähnlichen Welt ist ein Zauberer dafür verantwortlich, ein Netzwerk kleiner Dörfer zu patrouillieren, um die Menschen in der Gegend vor Schaden zu bewahren. Die Dorfbewohner wissen nichts von seinen Fähigkeiten, nur dass er ein exzentrischer alter Mann ist, der herumwandert. Sie wollen auch nicht mit ihm interagieren, weil sie ihn fürchten – insgesamt sind sie ziemlich fremdenfeindlich.

Eines Tages erleidet der Zauberer jedoch einen Anfall von Amnesie. Er erinnert sich an vieles, wer er ist, aber er vergisst, wie man am schnellsten zwischen den Dörfern hin- und herkommt. Er merkt schnell, dass es mehrere Wege von einem Dorf zum anderen gibt, aber nur einer der kürzeste ist.

Wie kann er herausfinden, welche Route er durchfahren soll? Er verwendet eine Annäherung: Reise in das nächstgelegene Dorf, in dem er noch nicht war.

Einige Einschränkungen:

  • Er muss zu Fuß reisen.
  • Er hat vergessen, wie man seine Kräfte einsetzt, bis auf eine: Die Fähigkeit, ungefähr sieben Sekunden lang zehn Fuß in der Luft zu schweben.

Hinweis: Ich hatte nicht vor, Magie zuzulassen. Das heißt, ich habe das ursprünglich nicht angegeben, daher halte ich Cort Ammons Antwort für vollkommen in Ordnung, zumal sie ziemlich clever ist. Zukünftige Antworten: Bitte verwende keine Magie! Danke schön.

Kommentare sind nicht für längere Diskussionen gedacht; diese Konversation wurde in den Chat verschoben .

Antworten (4)

Jeder Zauberer, der sich bewusst ist, dass er Kräfte hat, sollte wahrscheinlich sehr freundlich zu jedem sein, dem er begegnet. Du weißt nie, wen du vielleicht in der Vergangenheit beleidigt hast, also ist es ratsam, Wiedergutmachung zu leisten, bis du dich an mehr erinnerst.

Nachdem Sie zu jedem, den Sie treffen, freundlich sind (zumindest zu den wenigen, die sich Ihnen nähern) und im Allgemeinen versuchen, gutes Karma zu verdienen, werden Sie vielleicht feststellen, dass ein Naturzauberer auf Sie zukommt. Er fragt höflich, warum du ständig drei Meter in die Luft springst, weil es die Streifenhörnchen stört. Wenn sie sich nicht auf den Winter vorbereiten, werden sie verhungern.

Du erklärst dem Naturzauberer deinen Wunsch nach einem Weg zwischen allen Dörfern. Er fängt an, eine Karte und ein paar Zahlen zu kritzeln, aber du schüttelst den Kopf. Du erklärst, dass du nicht weißt warum, aber du bist dir ziemlich sicher, dass du Mathe nicht benutzen darfst. Er hebt eine Augenbraue und fragt: „Alles Mathe?“ Sie zucken mit den Schultern und erwähnen, dass Sie der Meinung sind, dass die Aufgabe wahrscheinlich schwierig genug ist, um einen mathematischen Ansatz zuzulassen. Du denkst, es wäre in Ordnung, wenn wir ein wenig schummeln und den Kompass und das Lineal verwenden, das du bequem zur Hand hast, um den Kreis zu quadrieren, wenn es als Teil der Lösung helfen würde, aber mehr Schummeln kannst du nicht zulassen. Leider haben Sie vergessen, wie man die Quadratur des Kreises macht, also ist es vielleicht nicht so hilfreich für einen Cheat.

Der Naturzauberer klatscht in die Hände und lächelt! "Die Natur macht alle möglichen erstaunlichen Dinge ohne Mathematik!" ruft er aus. Er beschwört etwas Magie herauf und Ameisen strömen aus mehreren Ameisenhaufen hervor. Er erklärt den Ameisen das Problem und gibt ihnen die Aufgabe, den kürzesten Weg für dich zu finden!

Sie danken dem Zauberer für seine Bemühungen und er fordert Sie auf, ein paar Stunden zu warten, bis die Ameisen das Land erkundet und den besten Weg gefunden haben. Er schlängelt sich davon, während Sie darüber nachdenken, wie viele Sieben-Sekunden-Intervalle es dauern wird, um Ihre Füße für ein paar Stunden von diesem von Ameisen verseuchten Boden fernzuhalten.

Ameisen sind erstaunlich gut darin, Wege in euklidischen Räumen zu finden. Tatsächlich sind sie so gut, dass wir ihren pheromonbasierten Ansatz oft in unseren Optimierungsalgorithmen nachahmen; sie funktionieren genauso gut!

Ist das nicht Betrug?
@ HDE226868 Ich verstehe nicht, wie es Betrug ist. Er beantwortet die Frage, die Sie gestellt haben, mit einer absolut praktikablen Lösung: Magie. Sie haben nie angegeben, dass der betreffende Zauberer schließlich keine Ressourcen verwenden kann.
Gut, ich lasse es. Ich dachte, die Implikation sei klar, dass Magie nicht erlaubt sei, aber ich lag falsch. Das werde ich mir notieren. +1 für Einfallsreichtum.
Dieser Ansatz funktioniert gut ohne Magie. Bauen Sie ein maßstabsgetreues Modell und lassen Sie die Ameisen auf das Modell fallen. Ich habe eine ähnliche Lösung gesehen, bei der Wasser mit Matrizen in einem maßstabsgetreuen Modell verwendet wurde (obwohl ich mich nicht erinnere, wie ich verhindern soll, dass sich die Matrizen vermischen).
@ Jim2B Die Ameisen sind immer noch von der Magie bezaubert ... Es sei denn, Sie sammeln die Ameisen von Hand und überreden sie irgendwie, die Ziele Ihres Modells in linearer Reihenfolge zu erreichen ... (Ist Zucker in den Farbstoffen? Woher wissen sie wo als nächstes gehen, oder wo ist eigentlich 'Zuhause'?)
Ich denke, Schleimpilze funktionieren besser als Ameisen. Dann kann er es einfach auf der Karte selbst anbauen, um den kürzesten Weg zu finden . Aber diese Antwort hat nicht wirklich etwas damit zu tun, dass der Typ ein Zauberer ist oder die eine Macht, die er hat. Du hast geschummelt, indem du gesagt hast, dass ein anderer Zauberer mit besseren Kräften auftaucht.
Die Wassermethode verwendet überhaupt keine Ameisen. Es war ein durchsichtiger Kunststoff mit eingeschnittenen Kanälen, die die verschiedenen Pfade darstellten. Der Kanal, bei dem das Wasser zuerst herauskam, war die optimale Lösung , aber ich kann das Video, das ich mir angesehen habe, nicht finden. Es war im Wesentlichen eine analoge Lösung für die TWP, die elegant funktionierte, aber für eine große Anzahl von Stopps schwierig einzurichten war.
Was die Ameisen betrifft, müssen Sie sie nicht bezaubern. Erstellen Sie einfach eine maßstabsgetreue Nachbildung, stellen Sie Lebensmittel an die Orte, die Städte darstellen, und lassen Sie sie nicht den Weg zurückgehen, den sie gekommen sind. Es gibt sogar etwas Literatur über die Methode :) - It's a "thing" en.wikipedia.org/wiki/…

Ich habe gerade mit einer Schnur herumgespielt und bin auf diese gekommen. Ich habe keine Ahnung, wie gut es in allen Fällen funktioniert. Es scheint für den Beispielfall, den ich hatte, zu funktionieren. Wenn jemand weiß, wo ich mehr Informationen über diese Art von Dingen finden kann, würde ich gerne in den Kommentaren hören.

Damit aus dem Weg, weiter mit der Show:

Mithilfe einer Karte (er geht in den örtlichen Kartenladen, der Dorfbewohner rennt weg, er nimmt die Karte) findet er alle Dörfer, die er besuchen muss.

Befestige an jedem Dorf eine Sicherheitsnadel, Schlaufe oder einen Haken. (Ich habe Sicherheitsnadeln verwendet, da ich welche zur Hand hatte)

Führen Sie eine Schnur entlang der Straßen oder Wege zwischen den einzelnen Dörfern. Binden Sie jedes Ende an die Sicherheitsnadel / Schlaufe / Haken.

Fügen Sie jeder Stecknadel ein Etikett mit dem Namen des Dorfes hinzu. Der Grund dafür wird klar werden.

Ihre Karte sollte ungefähr so ​​​​darüber stehen:Dörfer mit Schnur

Nehmen Sie nun den längsten Pfad auf. Halten Sie es so hoch, dass die beiden Sicherheitsnadeln an jedem Ende auf gleicher Höhe sind.

Schütteln Sie das Netz aus, nehmen Sie dann die unterste Aufhängeschlaufe und heben Sie sie auf und halten Sie sie hoch, sodass die Stifte an beiden Enden auf gleicher Höhe mit den Stiften der ersten Schlaufe sind.

Wiederholen Sie diesen Vorgang, bis Sie die Mindestanzahl von Strings übrig haben.

Haken Sie die Saiten, die Sie über der Linie halten, aus dem Netz aus. Das war ein bisschen schwierig, sie alle zu entwirren.

Sie sollten jetzt eine einzelne Reihe von Sicherheitsnadeln haben, die jede Stadt verbindet.Abgeschlossener Weg

Die Nachteile dieser Methode:
Die Einrichtung dauert ziemlich lange.
Sie müssen eine Karte stehlen.
Es ist sehr einfach, mit dem Netz in einem vollständigen Knoten zu enden.
Ich bin nicht davon überzeugt, dass es Ihnen immer die richtige Antwort geben wird. (Aber es scheint nah)

Ich bin mir nicht sicher, ob es funktionieren wird, aber +1, um tatsächlich etwas zu bauen, um es auszuprobieren.
Das ist eine tolle Idee! Nun, um es in Pseudocode umzuwandeln.

Er sollte eine Variation eines genetischen Algorithmus verwenden . Dies ist eine Technik, die natürliche Evolutionspfade nachahmt, um Probleme zu lösen, die ansonsten äußerst schwierig sind.

Nehmen wir an, es gibt vier Dörfer, zwischen denen sich jeweils drei Pfade unterschiedlicher Länge befinden.

Beim ersten Mal wählt der Assistent zufällig aus: AB1 -> BC2 -> CD3 -> DA1

Das nächste Mal wählt er andere Routen: AB2 -> BD3 -> DC1 -> CA2

Und beim dritten Mal: ​​AC3 -> CD2 -> DB3 -> BA1

Jetzt holt er alle seine Notizen heraus und wie lange er für jeden Weg gebraucht hat, und er beginnt, die besten Routen zu kombinieren und zu mischen. Er verwirft diejenigen, die viel zu lange gedauert haben, und behält und mischt nur die Muster, die relativ schneller waren. Dann beginnt er wieder bei Schritt 1, aber mit seinen neuen gemischten Mustern, und wiederholt dies mehrmals.

Irgendwann wird er eine Reihe sehr guter Pfade haben – sie werden nicht unbedingt optimal sein, aber sie werden nahe beieinander liegen.

Ein Punkt, für den ich fast eine ganze Antwort geschrieben habe: Der Assistent will eigentlich nicht den optimalen Pfad, selbst wenn einer existiert. Es ist eine schlechte Idee, Punkte immer in der gleichen Reihenfolge und ungefähr mit der gleichen Rate zu überprüfen, wenn Sie über einen langen Zeitraum patrouillieren. Es macht Sie weniger wachsam, ermöglicht es intelligenten Feinden, Sie vorherzusagen, und kann in regelmäßigen Abständen zu seltsamen Interaktionen mit anderen Dingen führen. Es ist also besser , mehrere gute Pfade zu haben und zwischen ihnen oder ihren Kombinationen zu variieren , als der optimale Pfad. Immer den gleichen Weg zu gehen, wird Sie auch für die Dorfbewohner ziemlich seltsam aussehen lassen.

Ein einfacher Algorithmus, den ich für eine relativ kleine Anzahl von Stopps verwende, ist dieser:

  1. Finden Sie die Entfernung von jeder Stadt zu jeder anderen Stadt.
  2. Nehmen Sie die Stadt, deren kürzeste Entfernung zu einer anderen die größte in der Gruppe ist – bezeichnen Sie diese als Stadt 1.
  3. Wählen Sie die kürzeste Route zur nächsten Stadt - bestimmen Sie diese Stadt 2.
  4. Wählen Sie von Stadt 2 aus die Route zur nächsten noch nicht besuchten Stadt aus.
  5. Wiederholen Sie Schritt 4 nach Bedarf

Dies gibt nicht die optimale Antwort , aber es gibt eine gute. Wenn die Anzahl der Städte kleiner ist (z. B. < 10), ist es manchmal offensichtlich, wie die Route verkürzt werden kann.

Es stellt sich heraus, dass mein selbst entwickelter Ansatz eine Variante des Minimum-Spanning-Tree-Ansatzes ist .

Mathematische Magie - Lösen des Problems des reisenden Zauberers [geschlossen]
AntwortenHierDatenschutz-Bestimmungen1y, 0v