Социальная проблема гольфиста

В дискретной математике социальная проблема игрока в гольф ( SGP ) представляет собой задачу комбинаторного проектирования , полученную на основе вопроса, опубликованного в группе новостей Usenet sci.op-research в мае 1998 года. ^[1] Проблема заключается в следующем: 32 игрока в гольф играют в гольф один раз в неделю в группах по 4 человека. Запланируйте, чтобы эти игроки играли в гольф в течение как можно большего количества недель, при этом ни один из двух игроков в гольф не играл бы вместе в группе более одного раза.

В более общем смысле эту задачу можно определить для любого $n=g\times s$ гольфисты, которые играют в $g$ группы $s$ игроки в гольф для $w$ недели. Решение включает в себя либо подтверждение, либо отрицание существования расписания и, если такое расписание существует, определение количества уникальных расписаний и их построение.

Проблемы

ПМГ представляет собой сложную проблему, которую необходимо решить по двум основным причинам: ^[2]

Во-первых, это большое пространство поиска, обусловленное комбинаторным и высокосимметричным характером задачи. Всего существует $(n!)^{w}$ расписания в пространстве поиска. Для каждого графика недели $(w!)$ , группы в течение каждой недели $(g!)$ , игроки в каждой группе $(s!)$ и отдельный игрок $(n!)$ все можно переставить. Это приводит к тому, что в общей сложности $w!\times g!\times s!\times n!$ изоморфизмы, расписания, которые идентичны посредством любой из этих операций симметрии. Из-за своей высокой симметрии SGP обычно используется в качестве стандартного эталона нарушения симметрии в программировании с ограничениями ( ограничения, нарушающие симметрию ).

Во-вторых, это выбор переменных. ПМГ можно рассматривать как задачу оптимизации, позволяющую максимизировать количество недель в расписании. Следовательно, неправильно определенные начальные точки и другие переменные в модели могут привести процесс к области в пространстве поиска без решения.

Решения

SGP представляет собой систему Штейнера S(2,4,32), поскольку 32 игрока в гольф разделены на группы по 4 человека, и как групповые, так и недельные задания любых двух игроков в гольф могут быть однозначно идентифицированы. Вскоре после того, как задача была предложена в 1998 году, было найдено решение за 9 недель, а существование решения за 11 недель оказалось невозможным. В последнем случае обратите внимание, что каждый игрок должен играть с 3 уникальными игроками каждую неделю. Для расписания длительностью 11 недель игрок будет сгруппирован в общей сложности $3\times 11=33$ другие игроки. Поскольку в группе всего 31 игрок, это невозможно. ^[3] Решение на 10 недель можно было получить на основе результатов, уже опубликованных в 1996 году. ^[4] Он был независимо переоткрыт другим методом в 2004 году. ^[5] какое решение представлено ниже.

10-недельное решение проблемы социального игрока в гольф (Агуадо, 2004 г.)
	Группа 1	Группа 2	Группа 3	Группа 4	Группа 5	Группа 6	Группа 7	Группа 8
Неделя 01	0,1,2,3	4,5,22,23	6,7,20,21	8,25,26,27	9,10,11,24	12,13,15,30	14,28,29,31	16,17,18,19
Неделя 02	0,4,8,28	1,6,18,23	2,7,17,22	3,5,26,31	9,13,14,27	10,15,19,21	11,25,29,30	12,16,20,24
Неделя 03	0,11,14,21	1,7,10,28	2,15,20,25	3,13,22,24	4,9,18,31	5,16,27,30	6,8,19,29	12,17,23,26
Неделя 04	0,18,24,27	1,9,19,26	2,8,11,16	3,10,17,25	4,7,12,29	5,6,14,15	13,20,23,28	21,22,30,31
Неделя 05	0,6,13,26	1,4,11,15	2,9,21,28	3,8,14,23	5,12,18,25	7,19,24,30	10,16,22,29	17,20,27,31
Неделя 06	0,7,25,31	1,5,24,29	2,12,14,19	3,18,28,30	4,6,10,27	8,13,17,21	9,15,16,23	11,20,22,26
Неделя 07	0,5,19,20	1,14,22,25	2,23,27,29	3,4,16,21	6,9,17,30	7,11,13,18	8,10,12,31	15,24,26,28
Неделя 08	0,15,17,29	1,13,16,31	2,4,26,30	3,6,11,12	5,7,8,9	10,14,18,20	19,22,27,28	21,23,24,25
Неделя 09	0,9,12,22	1,8,20,30	2,5,10,13	3,7,15,27	4,14,17,24	6,16,25,28	11,19,23,31	18,21,26,29
Неделя 10	0,10,23,30	1,12,21,27	2,6,24,31	3,9,20,29	4,13,19,25	5,11,17,28	7,14,16,26	8,15,18,22

Существует множество подходов к решению ПМГ, а именно методы теории дизайна , ^[6]^[7]Формулировки SAT ( проблема пропозициональной выполнимости ), подходы, основанные на ограничениях , ^[8] метаэвристические методы и поразрядный подход.

счисления . При основе системы счисления игроки в гольф распределяются по группам на основе сложения чисел в системе $k$ . ^[9] Переменные в общем случае ПМГ можно переопределить как $n=s^{k}$ гольфисты, которые играют в $g=s^{k-1}$ группы $s$ гольфисты на любое количество $k$ . Максимальное количество недель, в течение которых эти игроки в гольф могут играть без перегруппировки двух игроков, равно $(s^{k}-1)/(s-1)$ .

Приложения

Работа в группах поощряется в классах, поскольку она способствует активному обучению и развитию критического мышления и коммуникативных навыков. SGP использовался для распределения студентов по группам на курсах химии бакалавриата. ^[9] и переговорные комнаты в программном обеспечении для онлайн-конференций ^[10] максимизировать взаимодействие и социализацию учащихся.

SGP также использовался в качестве модели для изучения планирования турниров. ^[11]

См. также

Ссылки

^ Харви, Уорвик. «Задача 010: Проблема социальных игроков в гольф» . www.csplib.org . Проверено 6 сентября 2021 г.
^ Лю, Кэ; Леффлер, Свен; Хофстедт, Петра (2019). «Возвращение к проблеме социального игрока в гольф». Ин ван ден Херик, Яап; Роча, Ана Паула; Стилз, Люк (ред.). Агенты и искусственный интеллект: 11-я Международная конференция, ICAART 2019, Прага, Чехия, 19–21 февраля 2019 г., Пересмотренные избранные статьи . Международное издательство Спрингер. стр. 72–99. дои : 10.1007/978-3-030-37494-5_5 . ISBN 978-3-030-37494-5 .
^ Триска, Маркус. «Социальная проблема игрока в гольф» . www.metalevel.at .
^ Шен, Хао (1996). «Существование разрешимых групповых планов с размером блока четыре и размером группы два или три». Журнал Шанхайского университета Цзяотун . 1 (1): 68–70. МР 1454271 .
^ Агуадо, Алехандро. «Решение проблемы социальных игроков в гольф за 10 дней» (PDF) . Математические головоломки . Проверено 9 сентября 2021 г.
^ Лардо, Фредерик; Монфрой, Эрик (2015). «Выразительное моделирование проблемы социального игрока в гольф в SAT» . Procedia Информатика . 51 : 336–345. дои : 10.1016/j.procs.2015.05.252 .
^ Триска, Маркус; Муслиу, Нисрет (апрель 2012 г.). «Улучшенная формулировка SAT для решения проблемы социального игрока в гольф». Анналы исследования операций . 194 (1): 427–438. дои : 10.1007/s10479-010-0702-5 .
^ Лю, Кэ; Леффлер, Свен; Хофстедт, Петра (2019). «Решение проблем социальных игроков в гольф с помощью последовательного и параллельного программирования с ограничениями». В Роче, Ана; Стилс, Люк; ван ден Херик, Яап (ред.). Материалы 11-й Международной конференции по агентам и искусственному интеллекту . Публикации по науке и технологиям. стр. 29–39. дои : 10.5220/0007252300290039 . ISBN 978-989-758-350-6 .
^ Jump up to: ^а ^б Лимпанупарб, Тавитам; Датта, Сопанант; Таворнпарча, Пиятида; Чинсуксерм, Кридтин (2021). «ACAD-обратная связь: онлайн-платформа для назначения, сбора, анализа и распространения обратной связи от самих себя, коллег, инструкторов и групп» . Журнал химического образования . 98 (9): 3038–3044. doi : 10.1021/acs.jchemed.1c00424 .
^ Миллер, Элис; Барр, Мэтью; Кавана, Уильям; Вальков, Ивайло; Покупка, Хелен С. (2021). «График распределения секционных групп и проблема социального игрока в гольф с размерами соседних групп» . Симметрия . 13 (13). дои : 10.3390/sym13010013 .
^ Ламберс, Роэл; Ротуизен, Лоран; Спиксма, Фриц Ч.Р. (2021). «Проблема путешествующего социального игрока в гольф: пример Лиги волейбольных наций». В Стаки, Питер Дж. (ред.). Интеграция программирования с ограничениями, искусственного интеллекта и исследования операций: 18-я Международная конференция, CPAIOR 2021, Вена, Австрия, 5–8 июля 2021 г., Материалы . Спрингер. стр. 149–162. дои : 10.1007/978-3-030-78230-6_10 . ISBN 978-3-030-78230-6 .

Внешние ссылки

Сообщество Wolfram: подход Radix к решению проблемы социального игрока в гольф и визуализация графов
Wolfram Mathworld: задача социального игрока в гольф

[1] Харви, Уорвик. «Задача 010: Проблема социальных игроков в гольф» . www.csplib.org . Проверено 6 сентября 2021 г.

[2] Лю, Кэ; Леффлер, Свен; Хофстедт, Петра (2019). «Возвращение к проблеме социального игрока в гольф». Ин ван ден Херик, Яап; Роча, Ана Паула; Стилз, Люк (ред.). Агенты и искусственный интеллект: 11-я Международная конференция, ICAART 2019, Прага, Чехия, 19–21 февраля 2019 г., Пересмотренные избранные статьи . Международное издательство Спрингер. стр. 72–99. дои : 10.1007/978-3-030-37494-5_5 . ISBN 978-3-030-37494-5 .

[3] Триска, Маркус. «Социальная проблема игрока в гольф» . www.metalevel.at .

[4] Шен, Хао (1996). «Существование разрешимых групповых планов с размером блока четыре и размером группы два или три». Журнал Шанхайского университета Цзяотун . 1 (1): 68–70. МР 1454271 .

[5] Агуадо, Алехандро. «Решение проблемы социальных игроков в гольф за 10 дней» (PDF) . Математические головоломки . Проверено 9 сентября 2021 г.

[6] Лардо, Фредерик; Монфрой, Эрик (2015). «Выразительное моделирование проблемы социального игрока в гольф в SAT» . Procedia Информатика . 51 : 336–345. дои : 10.1016/j.procs.2015.05.252 .

[7] Триска, Маркус; Муслиу, Нисрет (апрель 2012 г.). «Улучшенная формулировка SAT для решения проблемы социального игрока в гольф». Анналы исследования операций . 194 (1): 427–438. дои : 10.1007/s10479-010-0702-5 .

[8] Лю, Кэ; Леффлер, Свен; Хофстедт, Петра (2019). «Решение проблем социальных игроков в гольф с помощью последовательного и параллельного программирования с ограничениями». В Роче, Ана; Стилс, Люк; ван ден Херик, Яап (ред.). Материалы 11-й Международной конференции по агентам и искусственному интеллекту . Публикации по науке и технологиям. стр. 29–39. дои : 10.5220/0007252300290039 . ISBN 978-989-758-350-6 .

[ACAD-Feedback-9] Jump up to: ^а ^б Лимпанупарб, Тавитам; Датта, Сопанант; Таворнпарча, Пиятида; Чинсуксерм, Кридтин (2021). «ACAD-обратная связь: онлайн-платформа для назначения, сбора, анализа и распространения обратной связи от самих себя, коллег, инструкторов и групп» . Журнал химического образования . 98 (9): 3038–3044. doi : 10.1021/acs.jchemed.1c00424 .

[10] Миллер, Элис; Барр, Мэтью; Кавана, Уильям; Вальков, Ивайло; Покупка, Хелен С. (2021). «График распределения секционных групп и проблема социального игрока в гольф с размерами соседних групп» . Симметрия . 13 (13). дои : 10.3390/sym13010013 .

[11] Ламберс, Роэл; Ротуизен, Лоран; Спиксма, Фриц Ч.Р. (2021). «Проблема путешествующего социального игрока в гольф: пример Лиги волейбольных наций». В Стаки, Питер Дж. (ред.). Интеграция программирования с ограничениями, искусственного интеллекта и исследования операций: 18-я Международная конференция, CPAIOR 2021, Вена, Австрия, 5–8 июля 2021 г., Материалы . Спрингер. стр. 149–162. дои : 10.1007/978-3-030-78230-6_10 . ISBN 978-3-030-78230-6 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]