社交ゴルファー問題

離散数学において、ソーシャルゴルファー問題( SGP ) は、1998 年 5 月にusenet ニュースグループsci.op-researchに投稿された質問から派生した組み合わせ設計問題です。 ^[1]問題は次のとおりです。32 人のゴルファーが 4 人ずつのグループに分かれて週に 1 回ゴルフをします。これらのゴルファーが、同じグループで 2 人のゴルファーが複数回一緒にプレーすることなく、できるだけ多くの週にわたってプレーするようにスケジュールを設定します。

より一般的には、この問題は数週間にわたってグループでプレーするゴルファーに対して定義できます。解決には、スケジュールの存在を肯定または否定し、そのようなスケジュールが存在する場合は、一意のスケジュールの数を決定して構築することが含まれます。 $n=g\times s$ $g$ $s$ $w$

課題

SGPは主に2つの理由から解決が難しい問題です。^[2]

まず、問題の組み合わせ的性質と高度に対称的な性質から生じる大規模な検索空間です。検索空間には合計でのスケジュールがあります。各スケジュールについて、週、各週内のグループ、各グループ内のプレーヤー、および個々のプレーヤーをすべて並べ替えることができます。これにより、合計で同型性、つまりこれらの対称操作のいずれを介しても同一であるスケジュールが生まれます。その高い対称性により、SGP は制約プログラミングにおける対称性の破れ(対称性の破れの制約) の標準ベンチマークとしてよく使用されます。 $(n!)^{w}$ $(w!)$ $(g!)$ $(s!)$ $(n!)$ $w!\times g!\times s!\times n!$

2 番目は変数の選択です。SGP は、スケジュールの週数を最大化する最適化問題と見なすことができます。したがって、モデル内の初期ポイントやその他の変数が誤って定義されていると、プロセスが検索空間内の解のない領域に導かれる可能性があります。

ソリューション

SGP はシュタイナーシステムS(2,4,32) と呼ばれます。これは、32 人のゴルファーが 4 人ずつのグループに分けられ、任意の 2 人のゴルファーのグループと週の割り当てが一意に識別できるためです。1998 年にこの問題が提案されてすぐに、9 週間の解が見つかり、11 週間の解の存在は不可能であることが証明されました。後者の場合、各プレーヤーは毎週 3 人の異なるプレーヤーとプレーする必要があることに注意してください。11 週間のスケジュールの場合、プレーヤーは合計で他のプレーヤーとグループ化されます。グループには他のプレーヤーが 31 人しかいないため、これは不可能です。^[3] 10 週間の解は、1996 年にすでに発表された結果から得ることができました。 ^[4]これは 2004 年に別の方法を使用して独立して再発見されました。^[5]これが以下に示す解です。 $3\times 11=33$

SGPを解くためのアプローチは数多くあり、具体的には設計理論の手法、^[6]^[7] SAT定式化（命題充足問題）、制約ベースのアプローチ、^[8] メタヒューリスティック手法、基数アプローチなどがある。

基数アプローチは、を底とする数の加算に基づいてゴルファーをグループに割り当てます。^[9] SGPの一般的なケースの変数は、任意の数のゴルファーのグループでプレーするゴルファーとして再定義できます。これらのゴルファーが2人のゴルファーを再グループ化せずにプレーできる最大週数はです。 $k$ $n=s^{k}$ $g=s^{k-1}$ $s$ $k$ $(s^{k}-1)/(s-1)$

アプリケーション

グループで作業することは、能動的な学習と批判的思考力やコミュニケーション能力の発達を促すため、教室では奨励されています。SGPは、学生の交流と社会化を最大限にするために、学部の化学の授業で学生をグループに割り当てたり^[9]、オンライン会議ソフトウェアのブレイクアウトルームに割り当てたりするために使用されてきました^[10]。

SGPはトーナメントのスケジュールを研究するためのモデルとしても使われてきました。^[11]

参照

参考文献

^ ハーヴェイ、ワーウィック。「問題010：ソーシャルゴルファー問題」。www.csplib.org 。 2021年9月6日閲覧。
^ Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). 「ソーシャルゴルファー問題の再考」。 van den Herik, Jaap; Rocha, Ana Paula; Steels, Luc (編)。エージェントと人工知能: 第 11 回国際会議、ICAART 2019、チェコ共和国プラハ、2019 年 2 月 19 ～ 21 日、改訂選定論文。 Springer International Publishing。 pp. 72 ～ 99。doi :10.1007/978-3-030-37494-5_5。ISBN 978-3-030-37494-5。
^ トリスカ、マルクス。「ソーシャルゴルファー問題」。www.metalevel.at。
^シェン・ハオ（1996年）。「ブロックサイズ4、グループサイズ2または 3の分解可能なグループ分割設計の存在」上海交通大学ジャーナル。1 （1）：68-70。MR 1454271。
^ Aguado, Alejandro. 「ソーシャルゴルファー問題に対する10日間の解決策」（PDF）。数学パズル。 2021年9月9日閲覧。
^ Lardeux, Frédéric; Monfroy, Eric (2015). 「SAT におけるソーシャルゴルファー問題の表現的モデリング」Procedia Computer Science . 51 : 336–345. doi : 10.1016/j.procs.2015.05.252 .
^ Triska, Markus; Musliu, Nysret (2012年4 月)。「ソーシャルゴルファー問題に対する改良型 SAT 定式化」。Annals of Operations Research。194 ( 1): 427–438。doi :10.1007/s10479-010-0702-5。
^ Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). 「制約プログラミングによるソーシャルゴルファー問題の解決 (シーケンシャルおよびパラレル)」。Rocha, Ana; Steels, Luc; van den Herik, Jaap (編)。第11 回国際エージェントおよび人工知能会議の議事録。科学技術出版。pp. 29–39。doi : 10.5220 / 0007252300290039。ISBN 978-989-758-350-6。
^ ab Limpanuparb, Taweetham; Datta, Sopanant; Tawornparcha, Piyathida; Chinsukserm, Kridtin (2021). 「ACAD-Feedback: 自己、同僚、講師、グループフィードバックの割り当て、収集、分析、配布のためのオンラインフレームワーク」。Journal of Chemical Education。98 ( 9): 3038–3044。doi : 10.1021/ acs.jchemed.1c00424。
^ ミラー、アリス; バー、マシュー; カバナ、ウィリアム; ヴァルコフ、イヴァイロ; パーチェス、ヘレン C (2021). 「ブレイクアウトグループ割り当てスケジュールと隣接グループサイズのソーシャルゴルファー問題」. Symmetry . 13 (13). doi : 10.3390/sym13010013 .
^ Lambers, Roel; Rothuizen, Laurent; Spieksma, Frits CR (2021). 「トラベリングソーシャルゴルファー問題：バレーボールネーションズリーグの事例」。Stuckey, Peter J. (編)。制約プログラミング、人工知能、オペレーションズリサーチの統合：第18回国際会議、CPAIOR 2021、オーストリア、ウィーン、2021年7月5～8日、議事録。Springer。pp . 149–162。doi :10.1007/978-3-030-78230-6_10。ISBN 978-3-030-78230-6。

外部リンク

Wolfram コミュニティ: ソーシャルゴルファー問題の解決とグラフの可視化に対する基数アプローチ
Wolfram Mathworld: ソーシャルゴルファー問題

[1] ハーヴェイ、ワーウィック。「問題010：ソーシャルゴルファー問題」。www.csplib.org 。 2021年9月6日閲覧。

[2] Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). 「ソーシャルゴルファー問題の再考」。 van den Herik, Jaap; Rocha, Ana Paula; Steels, Luc (編)。エージェントと人工知能: 第 11 回国際会議、ICAART 2019、チェコ共和国プラハ、2019 年 2 月 19 ～ 21 日、改訂選定論文。 Springer International Publishing。 pp. 72 ～ 99。doi :10.1007/978-3-030-37494-5_5。ISBN 978-3-030-37494-5。

[3] トリスカ、マルクス。「ソーシャルゴルファー問題」。www.metalevel.at。

[4] ^シェン・ハオ（1996年）。「ブロックサイズ4、グループサイズ2または 3の分解可能なグループ分割設計の存在」上海交通大学ジャーナル。1 （1）：68-70。MR 1454271。

[5] Aguado, Alejandro. 「ソーシャルゴルファー問題に対する10日間の解決策」（PDF）。数学パズル。 2021年9月9日閲覧。

[6] Lardeux, Frédéric; Monfroy, Eric (2015). 「SAT におけるソーシャルゴルファー問題の表現的モデリング」Procedia Computer Science . 51 : 336–345. doi : 10.1016/j.procs.2015.05.252 .

[7] ^ Triska, Markus; Musliu, Nysret (2012年4 月)。「ソーシャルゴルファー問題に対する改良型 SAT 定式化」。Annals of Operations Research。194 ( 1): 427–438。doi :10.1007/s10479-010-0702-5。

[8] Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). 「制約プログラミングによるソーシャルゴルファー問題の解決 (シーケンシャルおよびパラレル)」。Rocha, Ana; Steels, Luc; van den Herik, Jaap (編)。第11 回国際エージェントおよび人工知能会議の議事録。科学技術出版。pp. 29–39。doi : 10.5220 / 0007252300290039。ISBN 978-989-758-350-6。

[ACAD-Feedback-9] Limpanuparb, Taweetham; Datta, Sopanant; Tawornparcha, Piyathida; Chinsukserm, Kridtin (2021). 「ACAD-Feedback: 自己、同僚、講師、グループフィードバックの割り当て、収集、分析、配布のためのオンラインフレームワーク」。Journal of Chemical Education。98 ( 9): 3038–3044。doi : 10.1021/ acs.jchemed.1c00424。

[10] ミラー、アリス; バー、マシュー; カバナ、ウィリアム; ヴァルコフ、イヴァイロ; パーチェス、ヘレン C (2021). 「ブレイクアウトグループ割り当てスケジュールと隣接グループサイズのソーシャルゴルファー問題」. Symmetry . 13 (13). doi : 10.3390/sym13010013 .

[11] Lambers, Roel; Rothuizen, Laurent; Spieksma, Frits CR (2021). 「トラベリングソーシャルゴルファー問題：バレーボールネーションズリーグの事例」。Stuckey, Peter J. (編)。制約プログラミング、人工知能、オペレーションズリサーチの統合：第18回国際会議、CPAIOR 2021、オーストリア、ウィーン、2021年7月5～8日、議事録。Springer。pp . 149–162。doi :10.1007/978-3-030-78230-6_10。ISBN 978-3-030-78230-6。