Методы оптимизации - теормин (Методы оптимизации - теормин.pdf)

Методы оптимизациии. Теормин.1. Массовая задача.Формально массовая задача П определяется:1) общим списком всех параметров задачи (свободных параметров, значения которыхне заданы),2) формулировкой свойств, которым должен удовлетворять ответ (решение задачи).2. Индивидуальная задача.Индивидуальная задача I ∈ П получается из П, если всем параметрам присвоитьконкретные значения.3.

Алгоритм решения задачи.Будем говорить, что алгоритм А решает массовую задачу П, если для ∀I ∈ Палгоритм А применим к I (т. е. останавливается за конечное число шагов) и для ∀I ∈П алгоритм А дает решение задачи I.4. Полиномиальные алгоритмы решения массовой задачи.Алгоритмы, решающие произвольную I ∈ П за время, ограниченное полиномом от“размера” I. Полиномиальные задачи - задачи, для которых существуютполиномиальные алгоритмы решения.5.

Задачи распознавания свойств.Массовые задачи, предполагающие ответ “да” или “нет” в качестве решения.6. Кодировка задачи.Введем конечное множество - алфавит ∑ = { i}, а также множество ∑* слов надалфавитом ∑ - произвольных конечных последовательностей, составленных изсимволов алфавита, возможно повторяющихся, = i1 i2...

in, ij ∈ ∑ ∀ij. Число nназывается длиной слова и обозначается | |. Кодировкой задачи П назовемтакое отображение e: П → ∑*, ставящее в соответствие любой индивидуальнойзадаче I ∈ П ее код e(I) = ∈ ∑* (слово из алфавита ∑*), что1) Возможно однозначное декодирование: ∀I1 ≠ I2 e(I1) ≠ e(I2)2) e, e-1 полиномиально вычислимы: существует алгоритм, реализующий e, e-1 иполином p(), для которого ∀I ∈ П время определения e(I), e-1(e(I)) не превосходитp(|e(I)|)3) Кодировка неизбыточна: для любой другой кодировки e’, удовлетворяющейусловиям 1) и 2), найдется полином p’, такой что ∀I ∈ П |e(I)| < p’(|e’(I)|).7.

Временная сложность алгоритма.Алгоритм А решает массовую задачу П, если L(A) = L(П, e) и ∀∈ Σ∗ Аостанавливается. Обозначим tA(σ) – время работы над словом σ (число шагов).Временной сложностью алгоритма А решения массовой задачи П назовемфункциюT ( )=max∈ ∗ :| |( ) ∀ ∈8. Класс полиномиально разрешимых задач (P)P = {L(П, e) | ∃ , решающий П с кодировкой , ∃ () − полином: ( ) < ( )∀ ∈}Если для задачи П существует такая кодировка e, что (П, ) ∈ , то будем называтьП полиномиальной.9.

Недетерминированная машина Тьюринга (НДМТ)Определяется как набор обычных (детерминированных) машин Тьюринга A(S) салфавитом Σ, где S пробегает все множество слов из Σ*: = { ( )} ∈ ∗НДМТ останавливается, когда останавливается первая из ДМТ A(S), принимающаявходное слово. Соответствующее конечное состояние – qY.Язык НДМТ – множество слов, принимаемых хотя бы одной ДМТ.10.

НДМТ решает массовую задачу П с кодировкой еНДМТ решает массовую задачу П с кодировкой е, если L(П, e) = L(Â)∀σ ∈ L(П, ) ∃ ∈ Σ ∗ : ( ) останавливается в∀σ ∈ Σ ∗ \L(П, ) ∀ ∈ Σ ∗ A(S)не останавливается или останавливается в11. Время работы НДМТ Â над словом σМинимальное из времен работы ДМТ A(S) над словом σ с учетом времени прочтенияслова St̂ (σ) =min{ | ∈{|S| + t( )}( ) (σ)}12. Временная сложность НДМТ Â решения массовой задачи ПФункция T (n) =∈max:| |t̂ (σ)13.

Класс недерминированно полиномиальных задач (NP)NP = {L(П, )| ∃ − НДМТ, решающая П с кодировкой , ∃ ( ) − полином:T (n) < (n)∀n ∈ Z }14. Теорема об экспоненциальной оценке временной сложности NP∀П ∈∃ () − полином, ∃ ДМТ : решает П и ( ) < 2 ( ) ∀ ∈15.

Дополнительная массовая задачаДополнительная к П массовая задача П получается из П распознавания свойствзаменой альтернативного вопроса, определяющего ответ в задаче его отрицанием.D(П) = D(П); Y(П) = D(П)\Y(П)16. Классы co-P и co-NPco-P = {П | П ∈ P}co-NP = {П | П ∈ NP}Утверждение: co-P = P.17. Задача, имеющая хорошую характеризациюП имеет хорошую характеризацию, если П ∈ NP ∩ co − NP, П – распознаваниясвойств.18. Полиномиальная сводимостьП’ распознавания свойств с кодировкой e’ полиномиально сводится к П с кодировкойe, если ∀I′ ∈ П′ может быть сведена за полиномиальное от ее длины время кнекоторой I ∈ П с сохранением ответа.19.

УтвержденияЕсли П ∝ П и П ∝ П , то П ∝ ПЕсли П ∝ П и П ∈ P, то П ∈ PЕсли П′ ∝ П и П ∈ NP, то П′ ∈ NP20. NP-полная задачаМассовая задача П называется NP-полной (универсальной), еслиП ∈ NP и ∀П ∈ NP П′ ∝ ПКласс NP-полных задач – NPC (NP-complete).21. Задача о выполнимости (ВЫП)Выяснить выполнимость КНФ (существует ли набор входных данных, на которых КНФравна 1).22. Теорема КукаВЫП ∈ NPC23. УтвержденияЕсли P ∩ NPC ≠ ∅, то P = NPЕсли NPC ∩ (NP\P) ≠ ∅, то NPC ⊆ NP\P24. Критерий NP-полнотыМассовая задача П NP-полна тогда и только тогда, когда она принадлежит классу NP,и к ней полиномиально сводится какая-либо NP-полная задача.{П ∈ NPC} ⟺ {П ∈ NP и ∃П ∈ NPC: П ∝ П}25. Задача ЦЛНЗадача о существовании целочисленного решения системы линейных неравенств сцелыми коэффициентами. Принадлежит классу NPC.26. Задача БЛНЗадача о существовании булева решения системы линейных неравенств с целымикоэффициентами.

Принадлежит классу NPC.27. Задача 3-ВЫПЧастный случай ВЫП, когда функции от 3-х переменных.28. УтверждениеВЫП ∝ 3 − ВЫП29. УтверждениеЕсли для некоторой NP-полной задачи П дополнительная к ней принадлежит классуNP, то NP = co-NP.30. Класс NP-трудных задачКласс NP-трудных задач объемлет NPC. Он содержит:′1) П распознавания свойств, для которых доказано, что П ∝ П для П′ ∈ NPC, но недоказано, что П ∈ NP2) П оптимизации, для которых соответствующие П распознавания свойтсв NP-полны3) Остальные массовые задачи, к которым сводятся по Тьюринту какие-либо NPполные задачи.31.

NP-эквивалентные задачиП, для которых ∃П ∈ NPC: П′ ∝ П и ∃П ∈ NP: П ∝ П′′32. Класс PSPACEКласс задач, для решения которых существуют алгоритмы, требующие не более чемполиномиальной памяти.33. Псевдополиномиальный алгоритмОбозначим:num(I) – максимальное по модулю число (или 0), фигурирующее при заданиичисловых параметров индивидуальной задачи I|I| = |e(I)| – длину записи I.Алгоритм А решения массовой задачи П называется псевдополиномиальным, еслидля некоторого полинома p() выполненоe(I) < p(|I|, num(I)) ∀I ∈ П34.

Полиномиальное сужение массовой задачиМножество индивидуальных задач, числовые параметры которых не превосходятполинома от длины входа.35. Сильно NP-полная задачаМассовая задача П распознавания свойств называется сильно NP-полной, если ееполиномиальное сужение NP-полно.36. ТеоремаЕсли P ≠ NP, то ни для какой сильно NP-полной задачи не существуетпсевдополиномиального алгоритма.37. Задачи дискретной (комбинаторной) оптимизацииДля оптимизационной постановки задачи П решением каждой I ∈ П являетсяпроизвольная оптимизация Opt П (I) = max fП (I, z)∈ П( )SП – область допустимых значений дискретной (целочисленной) переменной z.fП (I, z): SП → Z – целевая функция задачи I.38. Приближенный алгоритм решенияАлгоритм А называется приближенным алгоритмом решения массовой задачи Поптимизации, если ∀I ∈ П он находит некоторую точку из допустимой областиzA(I) ∈ SП(I), принимаемую за приближенное решение.

Значение fП(I, zA(I)) называетсяприближенным значением оптимума и обозначается A(I).39. Утверждение о погрешностиЕсли P ≠ NP, то ни для какой константы C > 0 не существует полиномиальногоприближенного алгоритма А решения задачи о рюкзаке ЗР с оценкой|Opt ЗР (I) − A(I)| ≤ ∀I ∈ ЗР40. ε-приближенный алгоритмПриближенный алгоритм А решения массовой задачи П называется ε-приближеннымдля некоторого ε > 0, еслиП(||)( )|П ( )|<41. ТеоремаПусть для задачи П оптимизации1) Существует псевдополиномиальный алгоритм ее решения2) ∀I ∈ П |Opt П (I)| < p |I|, num(I) и num(I) < p (|I|, Opt П (I)) для некоторыхполиномов p1 и p23) σ = e(I), I ∈ П, параметры σS, задающие ограничения, и σf, задающие целевуюфункцию, не пересекающиеся и z ∈ SП(σ) функция цели fП(σ, z) линейно зависит отпараметров σf.

Тогда∃ () − полином: ∀ > 0 ∃ε-приближенный алгоритм Аε решения П с временнойсложностью T (|I|) < (|I|, 1⁄ε)42. Полностью полиномиальная приближенная схема (ПППС)Набор алгоритмов из теоремы в пункте 41.43. ТеоремаЕсли для П оптимизации соответствующая ей П распознавания свойств являетсясильно NP-полной, и ∃ ′ () − полином: |Opt П (I)| < ′ num(I) ∀I ∈ П, то, при условиичто P ≠ NP, для П не существует ПППС.44. УтверждениеЕсли P ≠ NP, то ни для какого ε > 0 не существует полиномиального ε-приближенногоалгоритма решения оптимизационной постановки задачи коммивояжера.45.

Основная задача линейного программирования (озЛП)Состоит в нахождении такого решения системы ЛН≤ , которое максимизируетцелевую функцию.46. Каноническая задача ЛПmax,< ,>47. Принцип граничных решенийЕсли задача max < , > имеет решение, то найдется такая подматрица AI∈:матрицы А, что любое решение системы уравнений AIx = bI реализует максимум в∈max:< ,>48. Симплекс-методМетод направленного перебора смежных вершин в направлении возрастанияцелевой функции.49. Функции алгебраической и битовой сложностиФункция алгебраической сложности: оценивает число арифметических операций взависимости от размерности, не учитывает длину кода элементов.Функция битовой сложности: оценивает число арифметических операций с битами(или конечными порциями – по размеру машинного регистра) цифровой записипараметров задачи в зависимости от длины входного слова.50.