Нахождение перекрывающихся множеств - PullRequest
Новая
       3

Нахождение перекрывающихся множеств

3 голосов
/ 04 октября 2010

Я пишу Цифровой фонтан систему на C #. Часть этой системы создает мне наборы целых чисел, мне нужно найти комбинации наборов, которые могут создать мне набор из одного предмета. Какой самый быстрый способ сделать это? 

Set A: 1,2,3,4,5,6
Set B: 1,2,3,4,6
Set C: 1,2,3
Set D: 5,6

Solutions:
A - B => 5
A - (C + D) => 4

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

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

Nb. Решения в C # получают бонусные оценки;)

1 Ответ

1 голос
/ 04 октября 2010

Я думаю, что некоторые хорошие решения могут быть получены с помощью некоторой модификации использования жадного набора обложек (алгоритм http://en.wikipedia.org/wiki/Set_cover_problem).

[псевдокод] так: 

1. sort sets by size descending
2.
foreach set in sets do:
  uncovered = set.size
  while uncovered > 1
    current_set = the biggest set that covers no more than (uncovered - 1) and was not used before to cover set
    uncovered = uncovered - covered_by_set(set)
    collect current_set to some array
  end
end

edit:

  • вы можете пропустить цикл foreach для последнего набора
  • это даст вам не более одного решения для каждого из наборов (исправить это вы можетеЗамените задачу непосредственно на проблему множества покрытий и используйте жадное покрытие множеств), например, если вы массив [1,3,4], вам нужно найти решение проблемы SCV для всех его подмножеств, имеющих размер = 2: [1,3], [1,4], [3,4]. Это усложнит задачу
  • иными способами, которые вы можете рассмотреть, являются алгоритмы эволюции (представление здесь будет очень простым, обрабатывайте указанное число как бит,функция пригодности должна вырасти ближе к 1), но это все равно не решает проблему добавления нового набора после вычислений (возможно, когда у вас лучшая популяция из последней проблемы, а затем после добавления нового набора просто добавьте новое место в хромосому)
...