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

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

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

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

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

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

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

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

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

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

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

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

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

и 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-полной в сильном смысле.