テレポート旅行者、長期にわたる最適な利益の問題

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

質問

私は巡回セールスマン問題全体やスタックオーバーフローについては初めてなので、何か間違っていることを言ったら教えてください。

イントロ:

複数の国 (地域) 内の複数の都市 (ノード) が関与するゲーム用に、利益と時間を最適化した複数取引アルゴリズムをコード化しようとしています。

  • 接続されている 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% リターン ルートの重みが 1.01 になることを意味します)。リターンが0%の場合は…を追加します。2?

その後、最も収益性の高いルートが返されるはずです...

質問：

たいてい、

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

  2. 新しい貿易ルートの開始にどのようにペナルティを課すことができますか?

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

余談ですが、

  1. グラフに対してどのような種類のプルーン/最適化を行うべきですか (または、すべきではありません)?
  2. 私の重み付け方法は正しいでしょうか?不釣り合いな重みになりそうな予感がします。パーセント収益ではなく実際の収益を使用する必要がありますか?
  3. Pythonでコーディングしている場合は、次のようなライブラリがあります。 Python グラフ 私のニーズに適していますか？それとも、特殊な関数を作成することで、多くのオーバーヘッド (グラフ検索アルゴリズムは計算量が多くなる可能性があることを理解しています) を節約できるでしょうか?
  4. A* 検索を使用するのが最善ですか?
  5. 取引データベース内の最短経路ポイントを事前に計算して最適化を最大化する必要がありますか、それともすべてをグラフ検索に任せるべきでしょうか?
  6. 改善できる点はありますか?
役に立ちましたか？

解決

ルーティングの問題 -

私はあなたが在庫と呼ばれる問題のクラスに収まる何かを定義したと思います。私はあなたが商品やコインの両方を持っているので、旅行者は、選択されたルートに沿って売買の両方であると仮定します。のは、最初のすべてが決定的であると仮定しよう - 需要の財の全ての量、利用可能な供給、価格を売買するなど事前に知られています。確率的バージョンは、より困難な（明らかに）なります。

一つの目的は、財布やグッズの制約で利益を最大化することです。旅行者がいない場合は、ホームツアーのようなそのルックスを返すために持っている場合、それはパスのように見えます。あなたはすべてのノードを訪問する旅行者を必要としていないので、それはTSPではありません。それは良いことだ - 最短経路問題は、一般のTSPを解決するよりもはるかに簡単です。

そのためサイドの制約や各ノードで次の手順の限られた選択肢の - 私は、ソリューションの技術で、動的プログラミングの最初の試みを使用して検討したいです。それはあなたが購入し、各段階で、販売やステージの数は限られて何を列挙するのに役立ちます。あなたが意思決定に時間的制約を置くためにも、それは選択肢の状態空間を制限します。

Djikstraのアルゴリズムを提案した人に - あなたは正しいかもしれない - ラベリング規則は、時間、コイン、商品と対応する利益を含める必要があります。それはDjikstraのの仮定は利益の追加複雑で、このために動作しない可能性があることかもしれません。まだそれを通して考えていない。

ここでリンクには、資本の同様の問題にあります予算ます。

グッドラック！

他のヒント

これはあなたが人間と対戦しているゲームである場合は、

私は、データ・スペースの合計サイズが、実際には非常に限られていると仮定します。もしそうなら、私はそれはそれは価値が疑うように、すべてのファンシーな剪定をスローするように傾斜させることでしょう。

その代わり、どのように簡単な幅優先探索はどうですか？

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

ゼロとして旅行時間をマークし、あなたの開始の街を取る

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を加算し、現在の都市は完全な分析を気にしないでください何の貿易を持っていない場合は、

、単に隣人の上に見て、代わりにそれらの分析を実行します。

あなたは余裕のCPUサイクルを持っている場合は、

（とあなたは非常によくかもしれませんが、プレイする人のためのものは何もかなり小さなデータ容量を持つことになります）、あなたはそれが取得するのにかかる時間に追加するすべての都市の分析を実行することができます街ます。

編集：あなたのコメントに基づいて、あなたはゲームがあなたのCPU上で実行されていないとして、利用可能なCPUパワーのトンを持っています。私は私の解決策に立つ：すべてを確認してください。私は強く、それが最適解を計算することになるよりも、それはルートや貿易の情報を取得するために時間がかかります疑います。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top