Задача о покрытии множества

[geomath]

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

Ничего кроме жадного алгоритма мне в голову не приходит. Но он позволяет отбросить по факту не больше 10% точек, т.е. экономия копеечная, а хочется больше.

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

[grizzly]

Ниже обычный для такой задачи жадный алгоритм, как я себе представляю. А какой у Вас?

Алгоритм.
1) Взять наименьшее множество из семейства и для каждой точки этого множества посчитать, скольким множествам в семействе она принадлежит.
2) Выбрать лидера первой точкой искомого множества.
3) Удалить из данного семейства все множества, содержащие выбранную точку. С полученным семейством вернуться в п.1).

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

[geomath]

Хорошо, спасибо, попробую.

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

[grizzly]

geomath в сообщении #1366373 писал(а):

Жадный алгоритм у меня такой

Ну так у Вас почти то же самое. Тогда или какая-то слишком специфическая система множеств (и тогда нужно смотреть на её природу) или где-то ошибка в алгоритме. Потому как 10% экономии по Вашим словам означает, что множества практически не пересекаются между собой.

[geomath]

Возможно, но не думаю, что они так уж не пересекаются. Точек у меня сотни, подмножеств - сотни тысяч, где каждое состоит их десятков точек.

[grizzly]

geomath в сообщении #1366385 писал(а):

Точек у меня сотни, подмножеств - сотни тысяч, где каждое состоит их десятков точек.

Мне странно, что Вы рассчитывали в таких условиях сэкономить намного больше 10%. И жадный алгоритм вряд ли будет хорош здесь. Должны быть специальные алгоритмы, задача наверняка рассматривалась. Но я не знаю.

[g______d]

Ищите по названию “Hitting set problem”.

[geomath]

geomath в сообщении #1366373 писал(а):

Хорошо, спасибо, попробую.

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

g______d в сообщении #1366402 писал(а):

Ищите по названию “Hitting set problem”.

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

[geomath]

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