Teleporting Reisende, Optimal Profit im Laufe der Zeit Problem

StackOverflow https://stackoverflow.com/questions/2256589

Frage

Ich bin neu in der ganzen Wander Verkäufer Problem sowie Stackoverflow, so lassen Sie mich wissen, wenn ich etwas sagen, das ist nicht ganz richtig.

Intro:

Ich versuche, Code einen Gewinn / zeitoptimierte Mehrfach Algorithmus für ein Spiel, das mehrere Städte (Knoten) in mehreren Ländern (Bereiche) umfasst, wobei gilt:

  • Die physikalische Zeit zwischen zwei miteinander verbundenen Städte Reise dauert immer gleich ist;
  • Die Städte sind nicht linear verbunden (Sie zwischen einigen Städten in der gleichen Zeit teleportieren können);
  • Einige Länder (Gebiete) haben teleportieren Routen, die den kürzesten Weg durch andere Länder zur Verfügung zu stellen.
  • Der Reisende (oder Händler) eine Grenze für seine Münzengeldbeutel, das Gewicht seiner Ware, und die Menge handelbarer in einer bestimmten Handelsroute. Die Handelsroute können mehrere Städte umfassen.

Frage Parameter:

Es gibt bereits eine Datenbank im Speicher (Python: SQLite), die Geschäfte auf der Grundlage ihrer Quelle Stadt und ihre Zielstadt hält, die kürzesten Pfad Städte dazwischen als Array und der Menge und der limitierende Faktor mit seiner% Rendite auf das Gesamt Kapital (oder in dem Fall, dass keiner der Faktoren beschränkt, dann nur die Methode, die die höchste Gesamtkapitalrendite gibt).

  • Ich versuche, den optimalen Gewinn für ein bestimmtes vorgegebenes Stück der Zeit zu finden (das heißt 30 Minuten)
  • Der Akt der Kreuzung in eine neue Stadt ist eigentlich gleichzeitige
  • Es dauert in der Regel die gleiche definierte Menge an Zeit zu reisen über den Stadtplan (d 2 Minuten)
  • Der Akt des ersten oder jede neue Handel Einleitung nimmt zur gleichen Zeit wie eine Stadtkarte Kreuzung (d 2 Minuten)
  • Mein Ausgangspunkt ist vielleicht nicht wirklich einen gültigen Handel hat (ich würde zu reisen, um den ersten / nächsten / besten)

Pseudo-Lösung So Far

Optimierung

Zuerst stelle ich fest, dass, weil ich eine Grenze für die Zeit es braucht, und ich weiß, wie lange jeder Sprung dauert (einschließlich -1 für intiating den Handel), habe ich die Grafik für alle Gewerke zu begrenzen, deren Hopfen unter oder gleich zu max_hops=int(max_time/route_time) -1. Ich schneide Elemente der Handelsdatenbank, die innerhalb dieser Frist nicht fallen, Beschneiden Städte, die kürzesten Weglängen größer als max_hops haben.

Ich mache einen weiteren Eintrag in die Gewerke Datenbank, die die kürzesten Wege zwischen meiner aktuellen Stadt und den Start Städte aller bestehenden Geschäfte umfasst, die nicht meine aktuelle Stadt sind, und ihnen eine Rendite von 0% ergeben. Ich würde diese, wo die Zahl der Stadt Hopfen weniger als max_hops begrenzen, und ich möchte auch berechnen, ob die aktuelle Stadt in die Ausgangs Stadt sowie dass Trades Shortest-Path-Hopfen würde excede max_hops und entfernen Sie diejenigen, die diese Grenze exceded.

Dann nehme ich die restlichen Gewerke, die nicht (current_city->starting_city) und Handelswege mit Rendite von 0% zwischen allen Ziel und Ausgangs Städte hinzufügen wheres der Hopfen nicht excede max_hops

Dann mache ich eine letzte Pflaume für alle Städte, die nicht im Handel Datenbank sind entweder als Start-Stadt, Zielstadt, oder einen Teil des kürzesten Weg Stadt Arrays.

Graph Suchen Ich bin links mit einem (sehr) kleinen Graph von Geschäften möglich innerhalb der Frist (das heißt 30 Minuten).

Da alle Knoten, die verbunden sind, benachbart sind, die Verbindungen standardmäßig sind alle 1. gewichtet Ich teile die Rendite in% über die Anzahl der Hops im Handel dann die inverse nehmen und fügen Sie + 1 (dies würde bedeuten, ein Gewicht von 1,01 für eine 100% Rückroute). In dem Fall, dass die Rückkehr 0% ist, füge ich ... 2?

Es sollte dann den profitabelsten Weg zurückkehren ...

Die Frage:

Meistens

  1. Wie füge ich die Möglichkeit, mehrere Routen zu nehmen, wenn ich über Geld oder Raum verlassen haben, und halten Wegfindung durch Pfad discrete zu Einzelhandelswege? Aufgrund der Beschaffenheit der Ware an mehreren Preisen und Mengen in der Stadt verkauft werden, gäbe es eine Menge von überschneidenden Strecken sein.

  2. Wie bestrafen ich einen neuen Handelsweg initiieren?

  3. Ist in dieser Situation sogar nützlich Graph suchen?

Eine Randbemerkung,

  1. Welche Arten von Pflaumen / Optimierungen an der grafischen Darstellung soll ich (oder soll ich nicht) machen?
  2. Ist meine Gewichtungsmethode richtig? Ich habe das Gefühl, es wird mir disproportional Gewichte geben. Soll ich die tatsächliche Rendite statt prozentualer Rendite verwenden?
  3. Wenn ich Codierung in Python sind Bibliotheken wie python-Graph geeignet für meine Bedürfnisse? Oder wäre es rette mich eine Menge Aufwand (wie ich sie verstehe, Graph Suchalgorithmen können rechenintensiv sein), um eine spezialisierte Funktion zu schreiben?
  4. Bin ich am besten aus A mit * Suche?
  5. Should I Shortest-Path Punkte in der Handelsdatenbank werden Vorberechnung und Optimierungen maxing oder sollte ich sie alle auf das Diagramm-Suche lassen?
  6. Können Sie sich etwas merken, dass ich verbessern könnte?
War es hilfreich?

Lösung

Ich glaube, Sie etwas, das passt in eine Klasse von Problemen genannt Inventar definiert haben - Routing-Probleme. Ich gehe davon aus, da Sie sowohl Waren als auch Münze haben, ist der Reisende sowohl Kauf und Verkauf entlang der gewählten Route. Lassen Sie uns zunächst, dass alles davon ausgehen, ist deterministisch - alle Warenmengen in Nachfrage, Angebot zur Verfügung, Kauf- und Verkaufspreise, etc. werden im Voraus bekannt. Die stochastische Version wird schwieriger (offensichtlich).

Ein Ziel wäre es, die Gewinne auf dem Geldbeutel mit einer Einschränkung zu maximieren und den Waren. Wenn die Reisende wie eine Tour zu Hause sein Aussehen zurückgeben müssen, wenn nicht, es sieht aus wie ein Pfad. Da Sie nicht die Reisenden benötigt haben jeden Knoten zu besuchen, ist es nicht ein TSP. Das ist gut - kürzester Weg Probleme sind in der Regel viel einfacher als TDL zu lösen.

Aufgrund der Nebenbedingung und die begrenzten Auswahl an den nächsten Schritte an jedem Knoten - halte ich würde dynamisch mit der Programmierung ersten Versuch einer Lösungstechnik. Es wird Ihnen helfen, aufzuzählen, was Sie kaufen und verkaufen in jeder Phase und es gibt nur eine begrenzte Anzahl von Stufen. Auch, weil Sie setzen eine Zeitbeschränkung auf die Entscheidung, dass der Staat Raum von Möglichkeiten begrenzt.

Für diejenigen, die Djikstra Algorithmus vorgeschlagen - können Sie richtig sein - die Kennzeichnungskonventionen müssten die Zeit umfassen, Münze, und Waren und entsprechende Gewinne. Es kann sein, dass die Annahmen von Djikstra der nicht für diesen mit der zusätzlichen Komplexität des Gewinns arbeiten. Noch nicht durch das gedacht.

Hier ist ein Link zu einem ähnlichen Problem in der Hauptstadt Budgetierung.

Viel Glück!

Andere Tipps

Wenn dies ein Spiel, wo Sie gegen Menschen spielen Ich würde die Gesamtgröße des Datenraumes übernehmen ist eigentlich ziemlich begrenzt. Wenn ja würde ich Beschneiden alle Lust zu werfen geneigt sein, wie ich bezweifle, es lohnt sich.

Stattdessen wie etwa eine einfache Breitensuche?

Erstellen Sie eine Liste aller Städte, markieren Sie sie nicht besuchte

Nehmen Sie Ihren Ausgang, markieren Sie die Reisezeit als Null 

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

O (): Die äußere Schleife ausführt Städte * maximalen Zeiten Hopfen. Die innere Schleife führt einmal pro Stadt. Keine Speicherzuordnungen benötigt werden.

Nun, für jede Stadt Blick auf, was Sie hier kaufen und verkaufen können dort. Wenn sie auf einem Handel die Rendite Bezifferung nicht vergessen, dass das Wachstum ist exponentiell, nicht linear. Zweimal der Gewinn für den Handel, das doppelt so lange dauert, ist nicht ein gutes Geschäft! Sehen Sie, wie Sie die interne Rendite zu berechnen.

Wenn die aktuelle Stadt keinen Handel hat nicht mit der vollen Analyse stören, einfach die Nachbarn Überblicke und die Analyse auf sich stattdessen läuft, für jede Bewegung eines zu der Zeit hinzugefügt wird.

Wenn Sie CPU-Zyklen zu Ersatz (und man könnte sehr gut, alles für einen Menschen zu spielen bedeutet einen ziemlich kleinen Datenraum hat) können Sie die Analyse auf jeder Stadt laufen können in der Zeit des Hinzufügen es braucht, um das zu bekommen Stadt.

Edit: Basierend auf Ihrem Kommentar haben Sie Tonnen von CPU-Leistung zur Verfügung, da das Spiel nicht auf Ihrer CPU läuft. Ich stehe zu meiner Lösung: Überprüfen Sie alles. Ich kann es stark wird länger dauern, vermuten, dass die Route und den Handel Informationen zu erhalten, als es die optimale Lösung berechnen wird zu.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top