Задача

Как вы помните из главы, посвященной ЖР-полноте, задача покрытия множества базируется на множестве U из n элементов и списке S1, ..., Sm подмножеств U; покры- тием множества называется совокупность этих множеств, объединение которых равно всему множеству U.

В версии задачи, которая рассматривается здесь, с каждым множеством S. вес w. > 0. Требуется найти покрытие множества C с минимальным общим весом

∑>

f⅛ес

Стоит заметить, что по сложности эта задача по крайней мере не уступает версии задачи покрытия множества с принятием решения, которая встречалась ранее; если назначить все w = 1, то минимальный вес покрытия множества не пре- восходит к в том, и только в том случае, если существует совокупность не более чем к множеств, покрывающая U.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии