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

Что я хотел бы сделать, так это разделить группу из (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 поставил меня на правильный путь, предоставив мне правильный поисковый запрос (большое спасибо!) — с тех пор я довольно много читал о проблеме социального игрока в гольф.

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


algorithm combinatorics solver constraint-programming disjoint-sets
person mezzopiano    schedule 26.09.2015    source источник
comment
Re Один и тот же набор элементов можно разделить только один раз на группы по три без перекрывающихся пар: что не так с ((A B D), (C E F)) и ((A B E) (C D F)) и еще как минимум с шестью? В заявленном вопросе не указывается, почему вы исключили эти комбинации.   -  person David Hammen    schedule 27.09.2015
comment
@DavidHammen пара AB находится в одной группе в обоих разделах. В вопросе ОП говорилось, что никакая пара элементов не находится в одной и той же группе дважды   -  person A.S.H    schedule 27.09.2015
comment
Большое спасибо, вы двое! @DavidHammen: Вы совершенно правы в том, что я мог бы использовать любой из ваших примеров вместо того, который я дал. Я уточню это в вопросе.   -  person mezzopiano    schedule 27.09.2015
comment
@a-s-h: Вы совершенно правильно поняли мое намерение, спасибо за разъяснение! Еще раз спасибо за ваши усилия и внимание к вопросу.   -  person mezzopiano    schedule 27.09.2015
comment
Вы можете поискать по ключевым словам: комбинаторные схемы, ортогональные массивы.   -  person jkff    schedule 27.09.2015
comment
@jkff Спасибо! Ваши указатели были чрезвычайно полезны, не могли бы вы немного расширить свой комментарий и дать ответ? В последние дни я читал о комбинаторике и нашел несколько параллелей с моим вопросом, но я никогда не сталкивался с областью комбинаторного проектирования. Прав ли я, думая, что то, о чем я прошу, - это парный сбалансированный дизайн? Знаете ли вы какие-либо ресурсы в этой области, которые были бы доступны компьютерным ученым, или какие-либо библиотеки?   -  person mezzopiano    schedule 27.09.2015

Ответы (2)


arrow_upward
8
arrow_downward

Эта проблема изучается под названием социальная задача игрока в гольф. Литература имеет нетривиальный объем, но есть три основных подхода:

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

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

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

person David Eisenstat    schedule 27.09.2015
comment
вау, большое спасибо за быстрый и исчерпывающий ответ! Ваш указатель был чрезвычайно полезен при поиске дополнительной литературы и указателей на реализации. Я тоже посмотрел Справочник по комбинаторным проектам, похоже, мне просто нужно погрузиться в математику :-). На данный момент я проголосовал за ваш ответ (желая сделать это несколько раз), вернусь и добавлю свои выводы в качестве комментария, когда я немного прочитаю. - person mezzopiano; 28.09.2015

arrow_upward
0
arrow_downward

Пусть 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

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

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

person Ante    schedule 27.09.2015