こんにちは素晴らしいコミュニティです！
私は現在、暇なときに小さなゲームを書いています。それは、プレイヤーがいくつかの星を制御できる大きな銀河で行われます。これらの星では、それぞれいくつかの (0..*) の入力を持つ建物を構築し、いくつかの出力を生成できます。これらの建物には最大容量/スループットがあり、その入力を縮小すると出力も同じ量だけ縮小されます。すべての建物のスループットを最適化 (または概算) する予算編成アルゴリズムを見つけたいと考えています。ある種の最大フローの問題のように思えますが、私が読んだフロー最適化アルゴリズムのどれも、異なるタイプの入力または依存する出力を持っていません。
私が遊んでいるおもちゃ「テック ツリー」は次のとおりです。
Solar plant - None => 2 energy output.
Extractor - 1 energy => 1 ore output
Refinery - 1 energy, 1 ore => 1 metal
Shipyard - 1 metal, 2 energy => 1 ship
私は準最適なアルゴリズムを喜んで受け入れ、入力/出力にサイクルがないことを保証します (それらは構築から構築への DAG を形成します)。アイデアは、プレイヤーの介入なしに、合理的なスループットと技術ツリーの複雑さを許可することです。数百または数千の星のスケールでは、プレイヤーが予算戦略を手動で定義できるようにすることは楽しくなく、それを生きていないプレイヤーに明確な違いを与えるためです。アドバンテージ。
私の現在の戦略は、DAG を構築し、リソースに全体的な順序を与えることです (船は金属よりも優れています。鉱石はエネルギーよりも優れています)。次に、各リソースをループして、最も「子孫」の建物を見つけます。そのリソースを生成し、その入力から再帰的に貪欲に取得できるようにします (造船所は 2 つのエネルギーと 1 つの金属を取得し、次に製油所は 1 つのエネルギーと 1 つの鉱石を取得するなど)、グラフ内の「嘘つき」を見つけます (ソーラー プラントは 4 エネルギーを提供します。最大値が 2 の場合)、生産を縮小し、変化を前方に伝播します。DAG のすべてが解決されたら、ターミナル要素 (造船所) をグラフから削除し、建物の最大スループットから各エッジの「現在のスループット」を差し引きます。次に、次のタイプのリソースに対してプロセスを繰り返します。もっと良い方法がないか、私よりもはるかに賢い人たちに聞いてみようと思いました。:)