スポンサーリンク

ソーシャル・ゴルファー問題とは,「全員が皆とペアになれるグループ分け」の組み合わせ最適化問題 (Social Golfer Problem, SGP)

「全員が皆とペアになれるグループ分け」の組み合わせを考えてみよう。

問題設定

全部で32人いるとして,これを毎週グループに分ける。

グループに分ける際,各メンバーが他の人とできるだけ多く組めるようにし,
最終的には他の全員とペアになれるようにしたい。

つまり,できるだけ重複が少なく,できるだけ新しい人と組めるようにして,
メンバー間の交流が促進されるようなグループ分けをしたい。

「ソーシャル・ゴルファー問題」という名前で,有名な未解決問題

こういう問題のことを,ソーシャル・ゴルファー問題という。

組み合わせ最適化問題で,一般解は存在せず,未解決問題。


ただし32人の場合とか,12人の場合に限って,何周あれば全員が全員と組めるかというテーブルが作成されている。

参考資料

Social Golfer(ソーシャルゴルファー問題) | LocalSolver例題集 | LocalSolver製品概要 | LocalSolver | MSI株式会社
https://www.msi-jp.com/localsolver/qu...

  • あるゴルフクラブには32人のソーシャル・ゴルファーが在籍しています。
    • 各ゴルファーは週に一度、通常4組に分かれて、プレイします。
  • この問題は交流の最大化を可能にする10週間のプレイ・スケジュールを組立てます。
    • すなわち、可能な限り、重複したグループ分けを少なくすることです。
  • 一般的なこの問題は、交流の最大化を含め、p週間におけるnゴルファーのm組のスケジューリングを行います。


The Social Golfer Problem
http://www.logic.at/prolog/sgp/sgp.html

  • The Social Golfer Problem (SGP) is a combinatorial optimisation problem. The task is to schedule g × p golfers in g groups of p players for w weeks such that no two golfers play in the same group more than once. An instance of the SGP is denoted by the triple g-p-w.
  • 12人を4グループ3人ずつに分割した場合,6週で全組み合わせを網羅できる。そのパターンの組み方を掲載している


Social Golfer Problem -- from Wolfram MathWorld
http://mathworld.wolfram.com/SocialGo...

  • In general, it is an unsolved problem. A table of known results is maintained by Harvey.


Scott R. Schultz - Social Golfer Templates
http://faculty.mercer.edu/schultz_sr/...

  • Each golfer is paired with one and only one golfer each round. This is known as a perfect pairing.