<<
>>

Задачи покрытия

Задачи покрытия образуют естественный контраст с задачами упаковки. Как пра- вило, для них характерна следующая структура: дан набор объектов, из которого выбирается подмножество, в совокупности достигающее некоторой цели. Требу- ется достичь этой цели с выбором только к объектов.

В этой главе были представлены две основные задачи покрытия.

♦ Задача о вершинном покрытии: для заданного графа G и числа к содержит ли G вершинное покрытие с размером не более к?

♦ Задача покрытия множества: для заданного множества U из n элементов, набора Sl, ..., Sm подмножеств U и числа к существует ли набор из не более чем к таких множеств, объединение которых равно всему множеству U?

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

Еще по теме Задачи покрытия:

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