Как (эффективно) генерировать непересекающиеся множества, используя пары элементов только один раз?

То, что я хотел бы сделать, это разделить группу (n) элементов на группы одинакового размера (группы размера m, и для простоты предположим, что остатков нет, т.е. n делится на m). Делая это несколько раз, я хотел бы убедиться, что ни одна пара предметов не входит в одну группу дважды.

Чтобы сделать это немного более конкретным, для построения групп из двух из шести предметов A..F, один раз мог разбить набор пять раз по-разному:

  • (A, B), (C, D), (E, F)
  • (A, C), (B, E), (D, F)
  • (A, D), (B, F), (C, E)
  • (A, E), (B, D), (C, F)
  • (A, F), (B, C), (D, E)

Один и тот же набор элементов можно разбить только один раз на группы по три без перекрывающихся пар:

  • (A, B, C), (D, E, F)

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

Теперь мой вопрос таков: есть ли способ сделать это эффективно? Есть ли уловки, чтобы ускорить генерацию этих наборов?

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

То, что я ищу, это трюки, чтобы ускорить процесс. Любые идеи приветствуются, в частности (но не ограничиваясь ими):

  • Оптимизация и эвристика для уменьшения количества возможностей, которые необходимо учитывать перед решением (например, из приведенных выше примеров ясно, что первый раздел может быть сделан просто произвольно, а первый набор каждого раздела [первый столбец выше). ] может быть сгенерировано автоматически).
  • Существуют ли варианты возврата, которые могут справиться с огромным количеством кандидатов? (т.е. не нужно заранее генерировать все возможности)
  • Другие алгоритмы, подходы или математические понятия, которые я должен рассмотреть?

Любые идеи и предложения приветствуются. Большое спасибо за рассмотрение этого!

Обновить

Итак, это было какое-то время, но я потратил на это гораздо больше времени и хотел вернуться к вам. @david-eisenstat поставил меня на правильный путь, дав мне правильный поисковый запрос (большое вам спасибо!) - с тех пор я довольно много читал о проблеме социального гольфиста.

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

Источник

2 ответа

Решение

Эта проблема изучается под названием Social Golfer Problem. Литература имеет нетривиальные размеры, но существует три основных подхода:

  1. Методы локального поиска, которые могут обрабатывать случаи, когда много пар отсутствуют.

  2. Полные методы поиска, такие как ваше сокращение до точного покрытия. Из того, что я помню, исследование здесь вращается вокруг эффективных методов нарушения симметрии, из которых ваша идея исправить первый ряд, вероятно, является самой простой.

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

Источник

Позволять n=m*kраздел имеет m группы с k Предметы.

После x разделы, каждый элемент находится в группе с x*(k-1) другие предметы. После создания t-1 разделы, в следующем разделе A можно выбрать для:

second element : n -   (t-1)*(k-1)   - 1  items
third element  : n - 2*(t-1)*(k-1)   - 2  items
fourth element : n - 3*(t-1)*(k-1)   - 3  items
...
k'th element   : n -   (t-1)*(k-1)^2 - (k-1)  items

Создавать t'th раздел нам нужен:

n - (t-1)*(k-1)^2 - (k-1) > 0
=>
t < (n - k + 1) / ((k-1)^2) + 1

Количество возможных разбиений уменьшается с квадратом длины группы. Это означает, что не так много возможных разделов:-)

Я бы пошел с некоторым жадным подходом. Сохраните для каждого набора элементов доступные элементы и создайте новый раздел, добавив первый доступный элемент в группу.

Источник
Другие вопросы по тегам