10

スポーツチームの管理シミュレーター（ホッケーやサッカーなど）で使用できる適切なアルゴリズムを探しています。シミュレーターのいくつかの機能：

  • チームはさまざまなフォーメーションでプレーできます（例：サッカーの4-4-2）。
  • チームの各プレーヤーは、フォーメーションの各ポジションでどれだけ優れているかを数値で評価します。
  • チームを選択できるさまざまな能力のチームプレーヤーのプールがあります

最強のチームとフォーメーションをプログラム的かつ効率的に決定するために使用できるアルゴリズムは何ですか？

4

3 に答える 3

11

問題をグラフでモデル化し、異なるフォーメーションの数が少ないことに気付いた場合、問題は最大加重二部マッチングであり、ハンガリーのアルゴリズムで解決できます....

2 部グラフで問題をモデル化するには、選手を一方の部分に配置し、位置を他方の部分に配置します (サッカーなど)。選手のプールと 11 の位置を形成し、すべての選手をすべての位置に接続し、対応するエッジを設定します。位置に対応するプレーヤーの評価として重み付けします。

あとは、この完全な 2 部グラフで最大 (加重) マッチングを見つけるだけです。(コードは wiki リンクで入手できます)。

フォーメーションの数は限られていると思います。フォーメーションごとに、対応するマッチング グラフとその最大重みマッチングを見つけることができ、最終的にすべての可能なフォーメーション (すべてのグラフ) で最大値を取得します。

于 2012-05-29T20:26:51.853 に答える
4

遺伝的アルゴリズムや山登り法など、最適化のための既存のAIツールを使用してヒューリスティックなアプローチを試すことができます。
私のお気に入りなので、山登り法について詳しく説明します。

とのG = (V,E)ような状態グラフとして問題を表します。 また、フォーメーションの効用関数とします。 グラフを生成したくないので、次のような関数にします。V = {all possible states }E = {(u,v) | swapping one player you can move from u to v }
u:V->R
next:V->2^Vnext(v) = {all possible formation that you can get by changing one player }

山登り法の考え方は、ランダムなフォーメーションから開始し、行き詰まったときに可能な限り最善の変更を貪欲に行うことです。新しいランダムなフォーメーションからアルゴリズムを再開します。

1. best<- -INFINITY
2. while there is more time
3. choose a random matching
4. NEXT <- next(s)
5. if max{ u(v) | for each v in NEXT} < u(s): //s is a local maximum
   5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it.
   5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
   6.1. s <- max { NEXT }
   6.2. goto 4.
7. return best //when out of time, return the best solution found so far.

この山登り法のバリエーション（ランダムな再起動を伴う山登り法）はいつでもアルゴリズムであることに注意してください。つまり、より多くの時間が与えられるとより良くなり、無限の時間が与えられると、グローバルな最大値が見つかります。

于 2012-05-29T19:12:13.663 に答える
2

問題に適用できる単純なヒューリスティックは貪欲アルゴリズムです。その説明はhttp://en.wikipedia.org/wiki/Greedy_algorithmにあります。

もう 1 つの解決策は、2 つのダミー ノード (開始と終了) を作成し、プレーヤーのプールを順序付けられたグラフと見なすことです (最初にゴールキーパー、次に右サイドのディフェンダーなど)。エッジは、検討中のポジションに対するプレーヤーの評価で構成されます。このシナリオでは、A* アルゴリズムを適用できるシナリオがあります。その説明はhttp://en.wikipedia.org/wiki/A*_search_algorithmにあります(最大化の問題は最小化に過ぎないことを覚えておいてください)。逆関数の）。

于 2012-05-29T19:11:07.893 に答える