2017-01-26 2 views
2

Я создаю генератор группы, где студенты подают предпочтения, кому они хотели бы быть в группе: 1 - лучший, 2 - второй и т. Д. Затем у меня есть метод, в котором будут сопоставляться хорошие два ученика, это основано на предпочтениях и как часто вы были вместе с этим человеком в прошлом. Он просто возвращает целое число. Если число низкое, то вы хорошо подобраны, если он высок, не так много.Алгоритм генерации групп?

Размер группы передается и группы создаются.

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

BTW излишек студентов распространяется только через первую пару групп.

+2

Максимальный вес соответствия. –

+0

@ Aᴍɪʀ Спасибо, это определенно похоже на то, что я могу использовать, хотя я стараюсь ** свести к минимуму ** значение между учениками, но это не должно быть проблемой. Но не могли бы вы рассказать? Как моя ситуация соответствует алгоритму? – Martin

+0

Что вы хотите оптимизировать? Я имею в виду, каковы характеристики лучшей комбинации? предпочтения студентов? или «доброта» студентов в группах? –

ответ

2

Имитированный отжиг хорошо подходит для таких проблем оптимизации. Энергия - это сумма ученических рядов для каждого другого учащегося в группе, и вы хотите свести ее к минимуму, сдержанность в том, что все группы равны (плюс выдумка для излишков студентов).

Вам нужно поиграть с программой, чтобы получить график температуры и охлаждения. Но если вы не настаиваете на идеальном результате, вы должны легко получить хороший результат.

2

Вы можете использовать грубую силу для создания всех «хороших групп» (группы, которые хорошо выигрывают).

Затем используйте линейное целочисленное программирование, где у вас есть переменная Gi, которая равна 1 или 0, что означает, что i-я группа G существует или нет.

Целевая функция для максимизации - это сумма переменных Gi. Ограничения заключаются в том, что Gi + Gj = 0 для любых двух групп Gi и Gj, если обе группы содержат один и тот же ученик.

Редактировать: я нашел способ сделать это точно с помощью линейного целочисленного программирования.

Maximize sum(Cij * Xij) (стоимость студентов спаривания я и J, умноженный на 1 или 0 на основу, если они в паре или нет, Xij = 1 or 0)

ограничения для каждой группы, Gk = SUM(Gk.ij) == group size

ограничение, SUM(Gk.ij) over all k & j == 1 (каждый студент в одной группе)

Смежные вопросы