Блог

У меня есть набор наборов элементов: {1}, {2}, {2,3}, {13,7}, {7,2,18} . И ограничения (элемент => максимальное количество элементов): count(1)<=10, count(2)<=2, count(3)<=5, count(7)<=1, count(13)<=10, count(18)<=10 (не более 2 от 2 общего количества). Мне нужно найти наилучшее подмножество начального набора, которое соответствует пределу. Например, {2}, {2,3}, {7,2,18} не подходит, потому что у 2 него всего 3, а у limit только 2 2 .

Внутренние наборы неизменяемы, например {7,2,18} , не могут быть разделены. Внутренние наборы могут быть любого размера (но на практике они составляют около 1-5 элементов)

Определение «наилучшего» в моем случае довольно расплывчато. Я согласен с подмножеством, в котором больше всего наборов. Или подмножество, в котором больше всего элементов.

В настоящее время у меня есть это (для случая «подмножество, имеющее большинство наборов»):

• вычисление текущих итогов по элементу ( {1=>1, 2=>3, 3=>1, 7=>2, 13=>1, 18=>1}
• найдите элементы, на которые влияет функция limit ( {2, 7} )
• найти наборы, содержащие затронутые элементы ( {2}, {2,3}, {13,7}, {7,2,18} )
• сгенерируйте все подмножества этого меньшего набора (2 ^ 4, 16 подмножеств, включая пустые)
• вычислите ограничения для каждого подмножества
• остановитесь с первым подобранным подмножеством

Моя проблема: я не уверен, является ли мое решение оптимальным, и оно имеет экспоненциальную сложность.

Есть ли лучшее решение?

(На практике это редкое условие, когда элемент достигает предела)

Дорогостоящий шаг для вас — вычислить все разделы набора наборов, чтобы увидеть, какие разделы допустимы с точки зрения ограничений. Вы генерируете O (2 ^ n) дерево (с n числом начальных подмножеств), а затем просматриваете все листья.

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

 place initial state (= set with all subsets) S in queue Q 
do
   pop first state from Q
   if valid, return it: it is an optimal answer
      else,
         for each subset I in the current state S
             push state S-I (that is, that does not include subset I) to Q
while Q is not empty
if this line is reached, return "no answer possible"
  

Обратите внимание, что в худшем случае (= нет возможного ответа) это так же плохо, как и то, что у вас было раньше. Но если нужно удалить несколько подмножеств, они будут найдены в O(2 ^ r) , где r — минимальное количество подмножеств, которые необходимо удалить, чтобы получить оптимальный ответ.

Вы можете еще больше ускорить процесс, если будете избегать повторного просмотра состояний: (недопустимое) состояние с r удаленными подмножествами будет достигнуто 2^r раз. Однако обратите внимание, что это компромисс между пространством и временем: чем больше кэш посещенных состояний, тем больше памяти вам понадобится.

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