Как решить эту вариацию школьниц kirkkmans

Question

Я пытаюсь реализовать приложение, которое назначает студентов в l лабораторий в g лабораторных группах.Ограничения:

1: студенты должны работать с новыми студентами для каждой лаборатории.2: все студенты должны быть руководителями лаборатории один раз.

2 не может быть решен, если ученики не могут быть разделены поровну на группы.Поэтому приемлемо, если «странные» ученики никогда не станут руководителями лаборатории.

Я испробовал два подхода, но пока не доволен .:

1. Поиск по Табу, который решает 1, но имеет проблемы с решением 2 (я на самом деле сначала решаю 1, а затем пытаюсь решить 2, что может быть неправильным подходом, любые предложения)

2. Простое решение, где я делюучащиеся в #labs в массиве [0..6] [7..14] [15..21], а затем поверните (с 0,1,2 дюйма) и транспонируйте матрицу, повторите это для #labs разс увеличенным вращением (1,2,4) и (2,4,6).Для 21 студента в 3 лабораториях с 7 лабораторными группами результат выглядит следующим образом:

   • лабораторная работа 1: [0, 7, 14], [1, 8, 15], [2, 9,16], [3, 10, 17], [4, 11, 18], [5, 12, 19], [6, 13, 20]
   • lab 2: [6,12, 18], [0, 13, 19], [1, 7, 20], [2, 8, 14], [3, 9, 15], [4, 10, 16], [5, 11, 17]
   • lab 3: [5, 10, 15], [6, 11, 16], [0, 12, 17], [1, 13, 18], [2, 7, 19], [3,8, 20], [4, 9, 14]

руководители лабораторий - это первая колонка для лаборатории 1, вторая для лаборатории 2 ...

Это решение работает достойно, но, например, не подходит для 12 студентов в 3 лабораториях или 150 студентов в 6 лабораториях.Любые предложения?

2, кажется, обрабатывает такое же количество случаев или комбинаций, и молниеносно по сравнению с 1. Может быть, я должен получить благородную цену: -)

Answer 1

Одно ограничение № 1 обычно называют проблемой социального игрока в гольф.(Пусть параметры g - это количество групп, а s - размер каждой группы, а w - количество недель. Группировка - это разделение игроков в гольф g * s на g групп размера s. Определите, можно ли найти w группчто каждая пара игроков в гольф сгруппирована не более одного раза.) Проблема социального игрока изучалась в литературе по комбинаторной оптимизации, и подходы бывают трех типов (вы можете использовать свою любимую поисковую систему, чтобы найти исследовательские статьи):

1. Локальный поиск.Это эффективно, когда w значительно ниже максимально допустимого значения. У Доту и Ван Хентенрика есть статья, в которой применяется поиск по табу для решения задачи социального игрока в гольф.

2. Завершите поиск.Это необходимо, когда w выше или чуть ниже максимально допустимого значения, но не очень хорошо масштабируется.

3. Алгебраические конструкции.Так был решен пресловутый случай g = 8 s = 4 w = 10.К сожалению, для многих наборов параметров не существует известной конструкции.

Чтобы назначить руководителей лабораторий, вычислите максимальное соответствие между учащимися и группами лабораторий, где есть преимущество.между студентом и лабораторной группой, если этот студент принадлежит к этой лабораторной группе.