Алгоритм составления билета

Question

Я пытаюсь написать программу для автоматизации проекта билета.

У нас есть определенное количество абонементов и мы хотим разделить билеты среди группы людей. Есть X количество игр, Y количество проходов сезона и Z количество людей. Каждый из людей Z оценил игры X.

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

Answer 1

Если бы не было каких-либо предпочтений, это было бы проблемой минимального потока с минимальным разрезом. http://en.wikipedia.org/wiki/Maximum_flow_problem, следующим образом:

Создайте исходную вершину A. От A создайте Z вершин, по одному для каждого человека. Емкость может быть бесконечной (или очень, очень большой). Создайте раковину B и создайте X вершин, по одной для каждой игры, связанной с B; мощность должна быть Y (у вас есть Y билет за игру). От каждого человека, ссылка на каждую игру, которую они оценили, с объемом 1.

Если вы посмотрите на ссылку wiki выше, для решения этой основной проблемы существует около 10 алгоритмов. Найдите тот, который вы понимаете и можете реализовать самостоятельно, потому что вам нужно немного его изменить. Я не знаком со всеми из них, но те, о которых я знаю, имеют шаг «выбрать край» или «выбрать путь». Вы должны изменить логику «как выбрать край», чтобы учитывать приоритетный порядок игр. Я не уверен точно, что должен быть заказ (вам, вероятно, потребуется поэкспериментировать), но если вы скажете, что игра с наименьшим рейтингом равна 1, следующая - 2, до X, то оценка, как «рейтинг края» - количество игр, на которые человек уже зарегистрировался, может работать.

Answer 2

Если у вас есть X-игры и Y-ый сезон, то, возможно, есть билеты X * Y, чтобы дать Z людям, не так ли?

Похоже, это можно рассматривать как проблему оптимизации, но для этого вам нужно определить свои основные цели? Я предполагаю, что вы хотите, чтобы каждый человек получал билеты X * Y/Z (разделить их равномерно), но, возможно, нет. Я предполагаю, что вы также хотите максимизировать совокупную удовлетворенность (определенную определенным образом в соответствии с рейтингами) в билетах. Вероятно, вы захотите дать большой штраф в удовлетворении для человека, если он получит более 1 билета за ту же игру. Я считаю, что этот последний аспект может быть причиной того, что подход с прямой тягой не самый лучший, но я мог ошибаться.

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

Answer 3

Я думаю, что это вариант Stable Marriage Problem или Stable Roommates Problem, для которого существуют известные алгоритмы для решения.