12. Задачи оптимизации и задачи принятия решения (распознавания). Задачи, np-полные в сильном и слабом смыслах. Примеры.

Задачи оптимизации и задачи принятия решения (распознавания).

I – множество входных данных

S – множество допустимых решений

Пусть f=φ(σ) – некоторая характеристика допустимого решения σ S,fR

Задача оптимизациизаключается в нахождении такого допустимого решения σ*S, такого что для любых σ €S:

φ(σ*)<= φ(σ) – задача минимизации

φ(σ*)=> φ(σ) – задача максимизации

ответ: σ*, либо значение φ(σ*)=f*

Задача принятия решения– это задача, на выходе которой может быть только одно из двух значений «да»/ «нет» (0/1)

Каждой задачи оптимизации поставить в соответствии задачу принятия решения:

Пусть существует задача оптимизации P(opt); алгоритм решенияA(opt)(x)= φ(σ*), гдеxI

Составим алгоритм A(dec) (x,f), гдеxI,fR, который решает задачу принятия решения:

иP(opt) соответствующийP(dec), то говорят чтоP(opt) тоже, т.к.P(opt) не прощеP(dec)

Пример: T

NP-полнота в сильном и слабом смыслах.

Рассмотрим задачу оптимизации Т

σ – допустим решение задачи Т

φ(σ) – характеристика решения σ

Обозначим :

• opt(x)= φ(σ*) – характеристика оптимального решения

• α(x)= φ(σ*) – характеристика находимого …..

Алгоритм α решает задачу Т с погрешностью р, если для любых х: α(x) <=p*opt(x)+c, где с – константа (для задач минимизации)

NPC:

• NP-полные в слабом смысле

• NP-полные в сильном смысле

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

Если такого алгоритма и константы р не существует, то задача считается NP-полной в сильном смысле.

13. Приближенные алгоритмы для задачи об упаковке в контейнеры.

Задача «об упаковке в контейнеры»

Пусть имеется набор предметов с весами: а(1)…а(n); a(i)€ [0,1]. Задача заключается в том, чтобы разместить эти n предметов в контейнеры, так чтобы суммарный вес предметов в одном контейнере не превышал 1 и число контейнеров было минимальным.

Данная задача является NP-полной.

1. Первый подходящий.

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

Пример:

А1:

Вес: 0,3 0,5 0,3 0,3 0,3 0,6

К1: 0,3 0,5

К2: 0,3 0,3 0,3

К3: 0,6

Утверждение: для любых х: А1(х)<=1,7opt(x)+2

Следствие: задача об упаковке в контейнеры является NP-полной в слабом смысле.

2. 1. Отсортировать множество весов по убыванию

2. Выполнить алгоритм А1 для получившегося множества весов.

Утверждение: для любых х: А2(х) <=11/9*opt(x)+4

14. Приближенный алгоритм для евклидовой задачи коммивояжера.

Утверждение: задача коммивояжера в общем виде является NP-полной в сильном смысле.

Задача коммивояжера «на плоскости» (с неравенством треугольника);

Алгоритм Кристофидиса (Ak)

1. выбрать вершину – корень

2. построить минимальное остовное дерево

3. построить прямой обход дерева

Получившиеся последовательность вершин образует искомый гамильтонов цикл.

Утверждение: для любых х : Ak(x)<=2opt(x)

Следствие: задача коммвояжера является NP-полной в слабом смысле.

Пример: