2.4. Упаковка рюкзака

У нас имеется набор объектов объемом стоимости

-В задаче оптимизации мы хотим упаковать рюкзак объемом так, чтобы его стоимость была максимальной.

-В задаче принятия решения нас интересует, можно ли добиться, чтобы суммарная стоимость упакованных объектов была по меньшей мере .

Эта задача возникает при выборе стратегии вложения денег: объемом здесь является объем различных вложений, стоимостью — предполагаемая величина дохода, а объем рюкзака определяется размером планируемых капиталовложений.

5. Задача о суммах элементов подмножеств.

Пусть у нас есть множество объектов различных размеров и некоторая положительная верхняя граница L.

В задаче оптимизации необходимо найти набор объектов, сумма размеров которых наиболее близка к L и не превышает этой верхней границы.

В задаче принятия решения нужно установить, существует ли набор объектов с суммой размеров L.

Это упрощенная версия задачи об упаковке рюкзака.

5. Задача планирования работ

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

Задача оптимизации требует установить порядок работ, минимизирующий накладываемые штрафы.

В задаче принятия решений мы спрашиваем, есть ли порядок работ, при котором величина штрафа будет не больше Р.

5. Задача о клике

Пусть дан граф G = G(V,E), где V – множество из n вершин, а E – множество ребер. Будем понимать под кликой максимальный по количеству вершин полный подграф в графе в G.

Задача состоит в определении клики в заданном графе G

Поскольку в полном графе на m вершинах имеется m(m-1)/2 ребер, то проверка, является ли данный граф полным, имеет сложность O (). Очевидно, что если мы рассматриваем подграф с m вершинами в графе G с вершинами (m < n), то всего существует различных подграфов. Если в задаче о клике количество вершин клики фиксировано, то перебирающий алгоритм имеет полиномиальную сложность:

Однако в общем случае придется проверять все подграфы с количеством вершин m = (2, n) на их полноту и определить максимальное значения m для которого в данном графе G существует полный подграф, что приводит к оценке в худшем случае:

http://www.lektorium.tv/course/?id=22758

1. Задача изоморфизма подграфу.

Даны 2 графа и . Пусть Требуется ответить на вопрос: Найдется ли в графе подграф H, изоморфный графу ?

2. Задача о клике.

Дан граф G с m вершинами и целое положительное число n.

Граф называется кликой, если каждая вершина в нем связана ребром с каждой. Количество вершин в клике назовем ее мощностью.

Найдется ли в данном графе G клика мощности не менее, чем n?

3. Вершинное покрытие.

Дан граф G с m вершинами и целое положительное число n.

Вершинным покрытием называется подмножество вершин графа , такое, что любое ребро графа G инцидентно хотя бы одной вершине множества Z.

Существует ли вершинное покрытие не более, чем из n вершин.

4. Разбиение.

Дано множество положительных целых чисел .

Можно ли разбить его на 2 подмножества так, чтобы суммы чисел в обоих подмножествах были равны?

5. Гамильтонов цикл.

6. Задача коммивояжера.

7. Трехмерное сочетание.

Даны 3 множества А, В, С. Мощности их равны m, но их множества не пересекаются. Рассмотрим множество троек . Трехмерным сочетанием называется подмножество , в котором никакие две разные тройки не имеют ни одной равной координаты.

Кроме класса NP-полных проблем рассматривают еще класс NP- трудных проблем.

Проблема Т называется NP-трудной, если она удовлетворяет условию: Если то R сводится к Т за полиномиальное время.

Это условие совпадает со 2-м условием для NP-полных проблем. Следовательно, NP- полная проблема – это NP- трудная, принадлежащая классу NP.

В отличие от класса NPC, в котором находятся много известных и практически важных задач, в промежуточном классе NPI известно значительно меньше таких задач. Одна из них – задача «Изоморфизма 2-х графов».