Грубая сила сложности Set Cover
Мы можем решить проблему покрытия наборов, сформировав все возможные комбинации наборов и проверив, является ли это минимальным решением. Теперь у нас может быть не более 2^n таких комбинаций множеств, где 'n' - номер множества.
Таким образом, сложность этого подхода должна быть O(2^n). Тем не менее, Википедия говорит, что "сложность Задачи Обложки множеств - это m^n, где m - размер юниверса, а n - количество наборов в коллекции".
Может кто-нибудь объяснить, как сложность O(m^n), а не O(2^n)?
Заранее спасибо.
2 ответа
Ты почти прав; Сложность алгоритма грубой силы составляет O(m 2^n) с учетом зависящих от модели логарифмических коэффициентов, потому что управление этими наборами не является бесплатным. O(m^n), вероятно, исходит из того, что для каждого из m элементов мы выбираем один из не более чем n наборов, которым он должен быть покрыт. Самое милостивое возможное объяснение, которое я могу предложить, состоит в том, что первоисточник установил границу O(m^k) для случаев покрытия множеств, где каждый элемент принадлежит не более чем к множествам, особый случай, рассматриваемый в контексте алгоритмов аппроксимации (есть k-приближение полиномиального времени).
Кажется довольно просто для меня.
Проблема визуализации:
- Представьте себе вселенную как набор путей (набор узлов).
- Представьте коллекцию как подмножество путей во вселенной.
- Для каждого узла во вселенной существует по крайней мере 1 путь, частью которого он является.
def Set Cover = минимальный путь, необходимый для размещения всех узлов.
Решение грубой силы:
a = find number of unique nodes in universe
b = find all path permutations as list
c = find b elements where number of unique nodes equals a
d = order c by path count and pick first
Поиск всех перестановок - это не O(m^n), а O(n!), И это было бы крайне неэффективно, если бы вселенная была большой. Однако вам не нужны все перестановки пути, вы можете просто найти перестановки пути до размера x, где x перечисляет от 1 до a. Однако я предполагаю, что вы поняли идею.