Методы оптимизации, 01 лекция (от 08 февраля)

Материал из eSyr's wiki.

Методы оптимизации

МО в хороших университетах для студентов по специальности прикл. математика --- 6 семестров, но у нас полугодовой курс, но это будет предлагать самостоятельную работу, будут давать задачи, их решение висит на сайте, но рекоммендуется рисовать их самостоятельно. В Америке по статистике 70 процентов функционально неграмотны. Это не есть обязательая мера. Для всех, кто хочет сдавать досрочно это обязтельная мера, а также для тех, кто обучается 4 года.

Курс для этого потока непохож на те, которые читаются для 1/2 потоков, там годовой курс, и попросили сделать упор на дискру.

Теория сложности

Лекции 4 будет занимать, основной набор задач по этой теме, эта же тема будет продолжаться в курсе ИО.

Литература

• М Гэри, Д. Джонсон. «Вычислительные машины и трудно решаемые задачи», М., Мир, 1982 год
• Х. Пападимитриу, К.  Сталиц, «Комбинаторная оптимизация», М. Мир, 1985 год

Что такое теория сложности

В чём цель прикладная? Если мы псомотрим, как двигалась научная мысль, то увидим, что сначала люди решали дискретные задачи. Если надо почитать площать, длину, то разбивали на кусочки. Но так считать тяжело. Потом Ньютон придумал флюксии, появился анализ… При этом забыли, что дискретные задачи решать сложно.

В конце 60-х годов народ понял, что переборные алгоритмы для существующих задач это сложно. И выяснилось, что да, есть задачи, для которых можно построить алгоритмы, есть задачи, для которых нельзя построить алгоритмы, и возникло направление, которое пыталось доказать по задаче, можно ли найти непереборный алгоритм или нет. На жтом и возникла теория сложности, которая хоть эту задачу не решает, но позволяет классифицировать задачи. В книжке Гэри-Жжонсона приводиться более 550 труднорешаемых задач, они все перечисляются по одной, поскольку основной резултат теории сложности такой: если удасться найти для однофй из этих задач найти непереборный алгоритм или доказать, что такого алгоритма построить нельзя, то это верно и для всех остальных. Задачи разного плана: теория графов, сети, головоломки, оптимизация БД…

Термины

Основное понятие — массовая задача (П)

1. Задача характеризуется списком параметров (имеются в виду свободные параметры задачи) (конкретные параметры → I)
2. Требования к решению. Задача поставлена ⇔ поставлены требования к решению.

Классической задачей, модельной задачей, массовой задачей, основной задачей является задача коммивояжёра.

Формулировка: имеется набор городов C = {c₁, …, c_n}, имеются расстояния между городами, полагаем, что они больше нудя: {d_ij = d(ci, cj)} > 0 | ci, cj ∈ C}. Коммивояжр должен выйти из города, обойти все, затратив наименьшее расстояние. Другое название — поиск гамильтонова цикла.

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

В данном случае C, {d_ij} — параметры задачи, требования к решению — найти такое &pi: {1, …, m} → {&pi₁, …, &pi_m} ↔ Невозможно разобрать выражение (неизвестная ошибка): \min_{T_{1}} \sum_{j=1}^{m-1} d(c_{\pi(i)}, c_{\pi(i+1)}) + d(c_{\pi(m)}, c_{\pi(1)) .

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

Можно сказать, что зачем нам кольцевая задача (альтернатива — бездомный коммивояжёр), но это столь же сложная задача.

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

Если спросить у человека, что проще — построить минимальную связывающую сеть или закольцевать, то немногие ответят, что связать просто, а закольцевать сложно.

Если же теперь на вход подаём какие-то численные значения, то получаем индивидуальную задачу. Можно сказать, чего проще, у нас конечные множества, можно перебрать все варианты. Чтобы рассеить все иллюзии, достаточно сказать, что число вариантов для m городов равно m!. Табличка:

У телефонной сети была задача обхода автоматов и вытаскивания из них жетонов, совершенно нерешаемая задача. В книге Гэри-Джонса есть замечательная картинка, в которой босс даёт сотруднику задачу, он пытается её решить, придумывает алгоритмы, но они все переборные.

Кроме первичных понятий будем использовать понятие алгоритма (A), понимать под этим формально следующее:

Алгоритм (А) — программа для машины Тьюринга.

Алгоритм А решает массовую задачу П, если для любои индивидуальнй задачи алгоритм применим, т. е. останавливается за конечное число шагов, и даёт решение: A решает П, если &forallI ∈ П А применим и даёт решение I.

Мы будем заниматься массовыми задачами распознавания свойств.

П — задача распознавания свойств, если в качестве требования к решению является ответ «да» или «нет».

Большинство задач без особых качественных изменений записываются в виде задач распознавания свойств, например, для задачи коммивояжёра: мы должны задать число B, которое является критической длиной маршрута, и вопрос выглядит таким образом: «существует ли маршрут длины ≤ B?».

Задачи в этих постановках по сложности эквивалентны, то есть, если будет найде алгоритм для задачи распознавания свойств, то \, не сильно увеличив сложность алгоритма, можно указать алгоритм для исходной задачи.

Также будут применяться следующие обозначения:

• D — множество значений параметров задачи
• Y — множество значений параметров, для которых соответствующая индивидуальная задача имеет ответ «да»

Этот набор (D, Y) полностью характеризует задачу распознавания свойств. Например, для задачи коммивояжёра:

• D = {C = {c₁, …, c_n}, {d_ij = d(ci, cj)} > 0 | ci, cj ∈ C}, B}, d_ij, B ∈ Z₊

Если есть алгоритм, который останавливается за конечное число шагов, то для того, чтобы найти сложность алгоритма, нужно связать количество шагов с длиной входного слова. Для того, чтобы формализовать размер задачи, с каждой проблемой П нужно свзяать некую схему кодирования (кодировку) для задания параметров.

Схема кодирования (кодировка): необходимо ввести алфавит Σ — множество, состоящее из конечного числа символов , Σ^* — множество слов для алфавита, слово — конечный набор букв, слово будем обозначать &sigma = {σ_i, σ_j, σ_k, …}. Кодировка — e: П → Σ^*, ∀I ⇒ e(I) = σ ∈ Σ^* — отображение массовой задачи в множество слов, индивидуальная задача отображается в слово.

Можно сказать, что отображение параметров задачи. Отображение должно удовлетворять следующим свойствам:

• Возможность декодирования однозначного: ∀I₁ ≠ I₂, e(I₁) ≠ e(I₂)
• Само кодирование и процесс декодирования должны быть полиминальной сложностиЮ e, e^-1 — полиномиальные вычисления
• Неизбыточность кодировки: для любой другой кодировки, удовлетворяющей свойствам 1 и 2 найдётся такой полином от n, что для любого натурального n найдётся такая задача I, что длина входа задачи I: — не существует кодировки, которая на порядок лучше

Обычно встречаемся с кодировкой чисел. Какие бывают кодировки: двоичная. Например, есть число N, в двоичной кодировке получаем число N₂ = (1, 0, …, 1), |N₂| = log₂ N, можно взять другую систему: |N₁₀| = log₁₀ N, и в данном случае порядок соответствует.

Другая кодировка: кодирование палочками, длина слова |N₁| = N = 2^{log₂ N}, и эта кодировка избыточная, так как в этом случае получаем не полином а экспоненту.

Задача 1. Предложить (неизбыточную) кодировку для задачи коммивояжёра и оценить длину входа.

В книге Гэри-Джонсона есть оценка, которая выглядит следующим образом:

Просьба: задачи решать-сдавать, не списывать (лектор готова брать листочки, где указаны максимум 5 человек).

Всем этим задачам (выявления свойств) соответствует Σ*, части их соответствует ответ «да», будем назыать эти слова правильными. Множество правильных слов — язык.

Язык — множество слов, соответствующих правильным решениям: L(Π, e) = у(Н) = {σ ∈ Σ* | Σ — алфавит e, σ = e(I), I ∈ Y}

С любым алгоритмом А, который решают задачу распознавания свойств, связывается язык: A ⇒ L(A) = {σ ∈ Σ* | Σ — алфавит A и A(&sigmal) = q_Y}

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

Время работы алгоритма А, если есму подали на вход слово σ — t_A(σ).

t_A(σ) — число шагов до остановки.

Определение 2. Временна'я сложность алгоритма A решения задчи П — функция T_A(.): T_A =

Задача 2. Дать алгоритм распознавания простоты числа, оценить временную сложность алгоритма. Что такое задача распознавания простоты числа — есть N, на выходе должны получить «да» — N простое, «нет» — N составное.

Классы сложности задач

Определение 3. Класс полиномиально разрешимых задач = {L(Π, e) | ∃ A решающий Π с кодировкой e, ∃p(.) — полином:

Будем говорить просто: задача принадлежит классу полиномиальных задач: П ∈ P — ежели для неё существует алгоритм с полиномиальной сложностью.

Труднорешаемые задачи — задачи, для которых нет полиномиального алгоритма.

Слово о полиномиальных и экспоненциальных алгоритмах: если есть алгоритм, который имеет полиномиальную сложность, но степено например порядка 7. Это ничем не лучше экспоненты. Но опыт показывает, что через некоторое время появляется алгоритм, который решает задачу с приемлемыми степенями полинома.

Ежели задача не принадлежит классу полиномиальных (П ∉ P), то есть три возможности:

• П неразрешима алгоритмически, то есть, нет алгоритма, который не решает любую индивидауальную задачу. Пример: 10-я проблема Гильберта по многочлену с целыми коэфициентами g необходимо найти, имеет ли уравнение g = 0 целочисленные решения. Было доказано (Матюясевич Ю. М.), что эта проблема алгоритмически неразрешима.
• Запись решения имеет экспоненциальную сложность
• Нет полиномиального алгоритма. Для любой подобной задачи доказано, что не существует полиномиальное решение задачи на МТ, допускающей бесконечный алфавит