5

都市建設ゲームを設計していて、問題が発生しました。

Sierra のCaesar IIIのゲーム メカニクスを想像してみてください。それぞれに 1 つの市場がある多くの都市地区があるとします。有向加重グラフで接続された距離にあるいくつかの穀倉地帯があります。違い: 人 (ここでは車) は交通渋滞を形成する単位です (ここではグラフの重みが続きます)。

注: Ceasar ゲーム シリーズでは、人々は食料を収穫していくつかの大きな穀倉に備蓄しましたが、多くの市場 (小さな店) は穀倉から食料を取り出して市民に届けました。

タスク: 各地区に食料をどこから調達すべきかを伝えると同時に、時間を最小限に抑え、都市の道路の混雑を最小限に抑えます。

マップの例

グラフ図の例

黄色の地区にはそれぞれ 7 個、7 個、4 個のリンゴが必要であるとします。青みがかった穀倉には、それに応じて 7 個と 11 個のリンゴがあります。

エッジの重みがそれらの長さに比例するとします。次に、解決策は、端に示されている灰色の数字のようなものになるはずです。たとえば、第 1 地区は第 1 穀倉から 4 個のリンゴを、第 2 穀倉からは 3 個のリンゴを取得しますが、最後の地区は第 2 穀倉からのみ 4 個のリンゴを取得します。

ここでは、最初に垂直道路が最大まで占有され、次に残りの労働者が斜めの経路に送られます。

質問

どの実用的で非常に高速なアルゴリズムを使用する必要がありますか? 輻輳ゲームについて説明している論文 ( Congestion Games: Optimization in Competitionなど) を見ていましたが、全体像をつかむことができませんでした。

4

6 に答える 6

6

最大フロー問題を調べたいと思います。この場合、それは2部グラフのように見えます。これにより、物事を視覚化しやすくなります。

于 2010-05-10T18:50:02.763 に答える
4

別の回答で説明されている増分更新の問題に対処し、コンピューターにとっても安価になる可能性がある1つの方法は、グローバルに最適なソリューションを忘れることです。各村人にアリコロニー最適化のようなものに参加させましょう。

例の右下の黄色のノードの人々が、右端の黄色のノードの人々がの「価格」を入札できるようにすることで、右端の黄色のノードの人々を絞り出さないようにすることを検討してください。右側の青いノードからリソースを購入します。これにより、右下の黄色のノードの一部のリソースが、左側の青いノードまで少し長く歩くようになります。

于 2010-05-10T22:13:39.473 に答える
4

これはマルチソースマルチシンク最大フロー問題であり、リンクで説明されているようにスーパーソースとスーパーシンクを作成することで簡単な最大フロー問題に簡単に変換できます。最大フロー問題には多くの効率的な解決策があります。

于 2010-05-10T19:08:36.243 に答える
2

Larry と mathmike に同意します。確かに、この問題はネットワーク フローの特殊化のようです。

別の注意点として、最終的なアルゴリズムが各市場のリソース (穀倉) へのスパニング ツリーを見つけ、最初に最短経路に基づいてそれらのリソースを貪欲に消費し、次に次のリソースの山に移動する場合、問題はより簡単になる可能性があります。

渋滞を最小化しようとするのではなく、最初に最大容量まで道路を使用する (道路効率を最大化する) という観点から考えると役立つ場合があります。

これは問題の根源に行き着きます。一般に、グラフの問題では最適に近い解を見つける方が簡単であり、ゲーム開発の観点からは、最適に近い解で十分である可能性があります。

編集: ウィキペディアへの mathmike のリンクも頂点容量の最大フロー問題について話していることを指摘したいと思います。

于 2010-05-10T19:17:29.587 に答える
0

注意しなければならないことは、ゲームが継続的であるということです。時間 t に解 X があり、いくつかの小さな変化が発生した場合 (たとえば、プレイヤーが別の道路を建設したり、都市の 1 つが人口を増やしたりした場合)、Max Flow アルゴリズムが与える解は大幅に変化する可能性がありますが、 d は、おそらく t+1 での解が X に類似することを望んでいます。時間ステップごとにまったく異なる解は非現実的です (マップの南端に 1 つの新しい道路が建設され、すべてのルートが自動的に再計算されます)。

私はいくつかのアルゴリズムを使用して初期ソリューションを計算します (または、地震で道路の 25% が破壊されるなどの大きな変化が発生した場合)、ほとんどの場合、増分的に更新するだけです。つまり、ソリューションに対して何らかの形式の有効な変換を定義します (たとえば、ある都市が現在とは異なる穀倉から 1 食料ユニットを取得しようとする場合) - 更新を試み (予想される混雑をシミュレートします)、更新された解決策が既存の解決策よりも優れている場合は、更新された解決策を維持します。各ゲーム ターンまたはある単位時間の後に、このステップを N 回実行します。

これは、計算効率が高く (毎秒フル Max Flow を実行する必要がない)、より現実的でスムーズな動作の変化が得られます。

于 2010-05-10T21:52:12.787 に答える
0

行動を駆動するための理想的な解決策を見つけるよりも、行動をモデル化して妥当な解決策をもたらすダイナミクスを持つ方が楽しいかもしれません。各旅行を個別に計画するとします。あなたが運転手で、A 地点から B 地点に移動する必要がある場合、どのように移動しますか? あなたはいくつかのことを考慮するかもしれません:

  1. この時間帯の典型的な交通状況を知っているので、通常は混雑している道路を迂回する方法を見つけようとします。ドライバーは必ずしも現在の交通状況について完全な情報を持っているわけではありませんが、時間の経過とともに傾向を学習して特定する可能性があるため、これをさまざまな時点での平均交通量としてモデル化できます。

  2. 曲がり角の多い、長くて分かりにくいルートは好きではありません。旅行を計画するとき、多くのエッジを持つ人にペナルティを課すことがあります。

  3. モデルに速度制限と信号機が含まれている場合、低速制限や信号機の多い長いストレッチは避けたいと思います。たとえ交通量が多いとしても、長い旅行には高速道路や高速道路を好む.

問題を純粋な最適化としてではなく、行動面から考察することから発展する興味深いダイナミクスが他にもあるかもしれません。実生活では、交通が最適なソリューションに収束することはめったにないため、交通工学における課題の大部分は、ドライバーの意思決定で発揮される自然なダイナミクスからより良いソリューションを促進するインセンティブ、ペナルティ、および設計を考え出すことです。

于 2010-05-11T02:05:22.650 に答える