7

私は巡回セールスマン問題全体とスタックオーバーフローに慣れていないので、正しくないことを言ったら教えてください。

イントロ：

複数の国（エリア）内の複数の都市（ノード）が関与するゲームの利益/時間最適化マルチトレードアルゴリズムをコーディングしようとしています。ここで、

  • 接続された2つの都市間を移動するのにかかる物理的な時間は常に同じです。
  • 都市は直線的に接続されていません（同時にいくつかの都市間でテレポートできます）。
  • 一部の国（地域）には、他の国を経由する最短経路を利用できるテレポートルートがあります。
  • 旅行者（またはトレーダー）は、小銭入れ、商品の重量、および特定の交易路で取引できる数量に制限があります。交易路は複数の都市にまたがることができます。

質問パラメータ：

メモリ内にデータベース（python：sqlite）がすでに存在し、ソース都市と宛先都市、配列と金額としての中間の最短パス都市、および総資本に対する％リターン（またはいずれの要因も制限されていない場合は、総資本に対して最大の利益をもたらす方法だけです）。

  • 特定のプリセット時間（つまり30分）に対して最適な利益を見つけようとしています
  • 新しい都市に渡るという行為は実際には同時です
  • 通常、都市地図を移動するのに同じ定義された時間（つまり2分）かかります
  • 最初の取引または新しい取引を開始する行為は、1つの都市地図を横断するのと同じ時間（つまり2分）かかります
  • 私の出発点は実際には有効な取引がない可能性があります（最初/最も近い/最良のものに移動する必要があります）

これまでの疑似ソリューション

最適化

まず、所要時間に制限があり、各ホップにかかる時間（トレードを開始するための-1を含む）がわかっているため、ホップが。以下のすべてのトレードにグラフを制限できることに気付きましたmax_hops=int(max_time/route_time) -1。この制限時間内に収まらない貿易データベースの要素を切り取り、最短経路の長さが。より大きい都市を剪定しますmax_hops。

私は、現在の都市と、現在の都市ではないすべての既存の取引の開始都市との間の最短経路を含む取引データベースに別のエントリを作成し、それらに0％のリターンを与えます。これらをシティホップの数が、未満の場所に制限します。max_hopsまた、現在の都市から開始都市に加えて最短パスホップを取引する都市が超過するかどうかを計算し、max_hopsこの制限を超えた都市を削除します。

次に、そうでない残りの取引を(current_city->starting_city)取得し、ホップが超過しないすべての目的地と開始都市の間で0％のリターンで取引ルートを追加しますmax_hops

次に、取引データベースに開始都市、目的地都市、または最短経路都市配列の一部として含まれていないすべての都市について、最後の整理を行います。

グラフ検索 制限時間内（つまり30分）に実行可能な取引の（はるかに）小さいグラフが残ります。

接続されているすべてのノードが隣接しているため、接続はデフォルトですべて加重1になります。％returnをトレードのホップ数で割ってから、逆数を取り、+ 1を加算します（これは、 100％帰路）。リターンが0％の場合は…2？

その後、最も収益性の高いルートを返す必要があります...

質問：

多くの場合、

  1. お金やスペースを残したときに複数のルートを取る機能を追加して、単一の貿易ルートに個別のパスを介してルートを検索し続けるにはどうすればよいですか？市内で複数の価格と数量で販売されている商品の性質上、重複するルートが多数あります。

  2. 新しい交易路の開始にペナルティを課すにはどうすればよいですか？

  3. この状況でグラフ検索はさらに役立ちますか？

ちなみに、

  1. グラフに対してどのような種類の整理/最適化を行う必要がありますか（または行わないでください）？
  2. 私の重み付け方法は正しいですか？私はそれが私に不釣り合いな重みを与えるだろうと感じています。パーセンテージリターンの代わりに実際のリターンを使用する必要がありますか？
  3. Pythonでコーディングしている場合、 python-graphなどのライブラリは私のニーズに適していますか？それとも、特殊な関数を作成するためのオーバーヘッドを大幅に節約できますか（私が理解しているように、グラフ検索アルゴリズムは計算量が多くなる可能性があります）。
  4. A *検索を使用するのが最善ですか？
  5. トレードデータベースの最短経路ポイントを事前に計算して最適化を最大化する必要がありますか、それともすべてをグラフ検索に任せる必要がありますか？
  6. 私が改善できることは何か気づきましたか？
4

2 に答える 2

2

これが人間と対戦するゲームである場合、データ領域の合計サイズは実際には非常に限られていると思います。もしそうなら、私はそれが価値があるとは思えないので、すべての派手な剪定を捨てる傾向があります.

代わりに、単純な幅優先検索はどうでしょうか?

すべての都市のリストを作成し、それらを未訪問としてマークします

出発都市を取り、移動時間をゼロとしてマークします

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(): 外側のループは、都市 * 最大ホップ回数を実行します。内側のループは都市ごとに 1 回実行されます。メモリ割り当ては必要ありません。

ここで、各都市について、ここで購入できるものとそこで販売できるものを見てください。取引の収益率を計算するときは、成長は線形ではなく指数関数的であることを覚えておいてください。2 倍の時間がかかる取引で 2 倍の利益が得られるのは得策ではありません。内部収益率の計算方法を調べてください。

現在の都市に交易がない場合は、完全な分析を行う必要はありません。代わりに隣の都市を調べて分析を実行し、各移動の時間を 1 ずつ追加します。

CPU サイクルに余裕がある場合 (人間がプレイするものは、データ スペースが非常に小さい場合があります)、都市に到達するまでの時間を追加して、すべての都市で分析を実行できます。

編集: コメントに基づいて、ゲームが CPU で実行されていないため、大量の CPU パワーを利用できます。私は自分の解決策を支持します：すべてをチェックしてください。最適解を計算するよりも、ルートと貿易情報を取得する方が時間がかかると強く思います。

于 2010-02-13T05:48:11.720 に答える
1

在庫と呼ばれる問題のクラスに適合するものを定義したと思います-ルーティングの問題。商品とコインの両方を持っているので、旅行者は選択したルートに沿って売買の両方を行っていると思います。まず、すべてが決定論的であると仮定しましょう - 需要のある商品の量、利用可能な供給、売買価格などはすべて事前にわかっています。確率的バージョンはより難しくなります (明らかに)。

目的の 1 つは、財布と商品を制約して利益を最大化することです。旅行者が家に帰らなければならない場合はツアーのように見え、そうでない場合は道のように見えます。旅行者がすべてのノードを訪問する必要がないため、これは TSP ではありません。これは良いことです。一般に、最短経路の問題は TSP よりもはるかに簡単に解決できます。

側面の制約と、各ノードでの次のステップの選択肢が限られているため、動的計画法の最初の試みを解決手法として使用することを検討します。各ステージで売買するものを列挙するのに役立ちます。ステージの数は限られています。また、決定に時間的制約を課すため、選択肢の状態空間が制限されます。

Djikstra のアルゴリズムを提案した人にとっては (あなたの言う通りかもしれませんが)、ラベル付けの規則には、時間、コイン、商品、およびそれに対応する利益を含める必要があります。利益の複雑さが増すと、Djikstra の仮定はこれには当てはまらない可能性があります。それはまだ考えていません。

これは、資本予算編成における同様の問題へのリンクです。

幸運を ！

于 2010-02-15T20:31:52.817 に答える