制約プログラミング言語Essenceを解説した論文“ESSENCE: A constraint language for specifying combinatorial problems” (2008)を読み解くシリーズの第3回です。

今回は、論文の中でしばしば出てくるSGPについて調べていきたいと思います。

SGP(ソーシャルゴルファー問題)とは

SGPで検索すると(私には)お馴染みの配管用炭素鋼鋼管というのがモリモリ出てきます。が、それではなくSocial Golfer Problem(ソーシャルゴルファー問題)だそうです。

詳しくは

を見ていただければ良いのですが、英語で書かれているのと、私自身の理解を深めることがこの記事の目標のひとつなので、自分なりに説明してみたいと思います。

SGPのルール

32人のゴルファーが4人ずつのグループで週に1回ゴルフをする。

良いですね、ゴルフ。しかも毎週。 4人ずつのグループであればゴルフじゃなくて麻雀でも良さそうですが。

32人だとぴったり8グループ作れるので丁度良い人数です。

どの2人のゴルファーもグループ内で2回以上一緒にプレーしない。

少しわかりにくいですね。 どの2人と言われても、この2人がどこから出てきた人数なのか全く理解できませんが、要するに、同じ人と2回以上一緒にプレーしない。自分を中心に考えたときに、一度同じグループになった人とは二度と一緒のグループにならない、ということです。

これらのゴルファーが可能な限り多くの週にわたってプレーできるようにスケジューリングする

ソーシャルゴルファーという理由がなんとなく理解できました。ゴルフ大好き仲良し32人組なのでしょう。

プレーする回数を最大化したいということなので、組み合わせ最適化問題ぽいこともわかりました。

ここで、少し考えを巡らせてみます。

このルールを私(ゴルファー)中心に考えると、毎週違う3人とグループを組んでプレーするので、10週目には違う30人とプレーしたことになります。

仮に11週目に突入したとすると、その時は33人の違う人とプレーすることになるので、前提の32人を超えてしまい矛盾します。なので、11週は絶対に不可能なことはすぐにわかります。

では10週が答えなのかというと、今のところは謎です。

仮に10週が正解だとすると、1人だけ一緒にプレーしていない人が出てきそうですが良いのでしょうか？

ということで次回に続きます(たぶん)。