Хорошая реализация жадного набора обложек для больших наборов данных? - PullRequest
Новая
       8

Хорошая реализация жадного набора обложек для больших наборов данных?

6 голосов
/ 29 октября 2011

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

Set        Cost
(1,2)        1
(1)          1
(1,2,3)      2
(1)          2
(3,4)        2
(4)          3
(1,2)        3
(3,4)        4
(1,2,3,4)    4

Цель состоит в том, чтобы найти хорошее покрытие набора, которое охватывает все числа, и одно, которое пытается минимизироватьОбщая стоимость.Мой набор данных большой, по крайней мере, 30000 наборов (размер варьируется от 5-40 элементов), как это.Есть ли хорошие жадные реализации, чтобы решить это, или я сам по себе, чтобы реализовать это?Я не эксперт в LP, но любые LP-решатели (от numpy / scipy), которые могут решить эту проблему, также приемлемы.

Ответы [ 2 ]

7 голосов
/ 29 октября 2011

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

http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm

Это так просто, что проще всего написать это с нуля.

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

К сожалению, запись в Википедии на самом деле не охватывает покрытие взвешенного набора, как здесь. Расширение простое и описано, например, здесь:

http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture03.pdf

Еще несколько полезных заметок:

http://www.cs.ucr.edu/~neal/non_arxiv/Young08SetCover.pdf http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec20.pdf

1 голос
/ 17 июля 2013

Моя линейная реализация пространства-жадности в c ++ для линейного времени / пространства доступна на github.

https://github.com/martin-steinegger/setcover

Расчет для 40.000.000 комплектов со средним значением. 10 элементов в наборе занимают около 4 минут при вычислении на экземплярах Amazon AWS m2.2xlarge.

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

  1. удалить подмножества, на которые распространяется больший набор с MinHash
  2. удалить все наборы, которые содержат только один элемент, который не является другим набором
...