Подскажите, эффективный алгоритм для задачи о покрытии

[kishkin]

Всем привет!

Столкнулся с задачей, которая свелась к задаче о покрытии, но размерность задачи (если так можно выразиться) не позволяет решать ее перебором - слишком долго.

Сразу же пришла на ум жадная эвристика, но закрались сомнения, вдруг есть что-то получше. Погуглил нашел очень много книг на эту тему. Сейчас читаю. Но, может, кто-то уже сталкивался и посоветует?

Заранее спасибо.

[maxal]

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

Но если, например, если вашу задачу можно свести к поиску клики или независимого множества в графе - могу порекомендовать ПО Стаса Бусыгина: http://www.stasbusygin.org/

[kishkin]

Точно, ошибся!

Имелась в виду Set Cover Problem. Сам не знаю, почему SAT написал.

За ссылочку благодарен.