Фильтрация списка по ограничениям

Ответ 1

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

Чтобы поддержать выбор набора как минимум размера X (в данном случае 10) из исходного набора элементов длиной Y (в вашем примере 11), вам нужно будет собрать список наборов решений, а не исключать элементы по одному баллу., Набор решений (m, n) - это набор из m элементов, из которых вы должны выбрать сохранение n элементов и исключение остальных. Поскольку большинство правил в вашей системе представляют собой один элемент атрибута x, будет установлено большинство наборов решений в вашем списке (m, 1) - выберите 1 из m элементов, исключите остальные.

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

Цель состоит в том, чтобы очистить список наборов решений при большинстве исключений YX. Поскольку элемент может появляться в нескольких наборах решений, вы также можете добавить для каждого элемента "показатель выживания". Показатель выживания указывает на максимальное количество предметов, которые должны быть устранены, если этот предмет будет сохранен. Он рассчитывается по каждому пункту путем прохождения каждого набора решений (m, n) и добавления к каждому элементу, содержащему mn, к его накопленной оценке.

Давайте посмотрим на ваш пример и создадим его наборы решений:

• Item1 (Категория A, Автор 1)
• Item2 (Категория A, Автор 2)
• Item3 (Категория A, Автор 3)
• Item4 (Категория B, Автор 2)
• Item5 (Категория C, Автор 5)
• Item6 (Категория D, Автор 6)
• Item7 (Категория E, Автор 7)
• Item8 (Категория F, Автор 8)
• Item9 (Категория G, Автор 9)
• Item10 (Категория H, Автор 10)
• Item11 (категория I, автор 11)

Наборы решений, которые мы компилируем (обратите внимание на показатель выживаемости в скобках):

• Набор решений автора (2,1) = {пункт 2 (2), пункт 4 (1)}
• Набор решений категории (3,2) = {пункт 1 (1), пункт 2 (2), пункт 3 (1)}

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

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

Ответ 2

У вас есть список предметов, и вам нужно удалить некоторые из них, чтобы достичь своей цели. Вам нужно проверить, может ли удаление каждого предмета-кандидата дать вам лучшее решение! Попробуйте удалить каждый элемент, который может улучшить ваш список, и посмотрите, достигли ли вы своей цели.

Вот шаги, чтобы решить это с рекурсией:

1. Если заданный размер списка меньше или равен 10, вернуть
2. Составьте список кандидатов для удаления из вашего списка (Item1, Item2, Item3 и Item4 в случае вашего примера). Если список кандидатов пуст, значит, все готово.
3. Удалите каждого кандидата по одному, вызовите рекурсию и затем верните удаленный элемент
4. В случае рекурсии возвращает true, все готово

Вот некоторый псевдокод

bool recurse(list l)
  if (l.size() <= 10) {
    // cannot remove anything
    return false
  candidates = buildCandidateList(l)
  if (candidates.size() == 0)
    // check for top 10 items
    return true
  for each c in candidates {
    remove c from l
    if (recurse(l) == true) 
      // check for top 10 items
      return true
    add c back into l
  }
// just get first 10 items
return false

Это решение основано на возврате с рекурсией. В качестве альтернативы, я думаю, также возможно создать динамическое программирующее решение "снизу вверх", которое дало бы лучший результат с точки зрения времени сложности Big-O.

Ответ 3

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

Наборы решений (как предложено @Assafs) сделают свое дело; однако общий алгоритм набора решений очень неэффективен для общего случая вашей проблемы. Если вам нужно создать полные наборы решений для миллионов записей, просто чтобы избежать случая, когда не хватает элементов ввода, мне кажется излишним.

Более того, описание "топ-10" набора результатов не раскрывает, какой правильный набор результатов установлен во всех случаях. Например, если в приведенном вами примере больше элементов, нет ничего, что указывало бы на то, что удаление элемента 2 является правильным подходом. Не ясно, как мы должны измерить, какие 10 являются "топ-10".

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

Чтобы реализовать это, вам нужно сохранить карту от каждого из уже выбранных вами предметов до предметов, которые были дисквалифицированы. Кроме того, вам нужно сохранить карту от каждого из дисквалифицированных предметов до каждого из предметов, дисквалифицирующих его.
После того, как вы получите набор результатов из своего жадного алгоритма, если у вас меньше 10 результатов, вы просматриваете набор результатов и заменяете элементы, которые дисквалифицируют множество элементов, элементами, которые их дисквалифицируют.
То, как вы решаете, какие элементы проверять первыми, действительно зависит от вас, поскольку, опять же, нет описания того, как определить, что входит в "топ-10". Вы можете исключить предметы с более низким баллом, которые сначала дисквалифицируют более 1 других предметов, или искать предметы, которые дисквалифицируют больше всего, и т.д.
Важно то, что какой бы алгоритм вы ни выбрали, ваш результирующий набор имеет максимум 10 элементов, и поэтому, даже если вы придумали алгоритм O (n ^ 3) с чрезмерным числом оборотов, он все равно является алгоритмом с постоянной операцией 1000 что на самом деле O (1). Построение карт, необходимых для реализации этого, также требует времени O (1) во время работы вашего исходного алгоритма.