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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Лекция 1 == '''Задача 1'''. Предложить (неизбыточную) кодиро...)
Строка 1: Строка 1:
-
== [[Методы оптимизации, 01 лекция (от 08 февраля)|Лекция 1]] ==
+
== Задача 1 ==
-
'''Задача 1'''. Предложить (неизбыточную) кодировку для задачи коммивояжёра и оценить длину входа.
 
-
'''Задача 2'''. Дать алгоритм распознавания простоты числа, оценить временную сложность алгоритма. Что такое задача распознавания простоты числа — есть N, на выходе должны получить «да» — N простое, «нет» — N составное.
+
'''Условие.''' Предложить неизбыточную кодировку задачи коммивояжёра. Дать оценку длины входа и сравнить её с <math>m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil</math>.
 +
 
 +
 
 +
'''Решение.''' Пусть m — число городов, B — максимальная длина маршрута, <math>D = \lbrace d_{i,j}\rbrace</math> — матрица расстояний между городами. Будем кодировать m, B и <math>d_{i,j}</math> в двоичном виде. Кроме того, включим в алфавит символ-разделитель #. Таким образом, кодировка будет состоять из двоичных записей чисел m, B и элементов <math>d_{i,j}</math>, между которыми находятся разделители #. При этом можно включать в кодировку не все элементы <math>d_{i,j}</math>, а только те, которые лежат выше главной диагонали матрицы D (поскольку в силу равенств <math>d_{i,j} = d_{j,i}</math> и <math>d_{i,i} = 0</math> матрица D симметрична и имеет нулевую главную диагональ). Кроме того, можно не кодировать и число m, поскольку оно однозначно определяется по числу разделителей между элементами матрицы.
 +
 
 +
Для того чтобы осуществить двоичное кодирование некоторого числа N, необходимо <math>\lfloor \log_2 N \rfloor + 1</math> символов. Таким образом, длина входа задачи коммивояжёра будет равна
 +
 
 +
<math>(\lfloor \log_2 B \rfloor + 1) + 1 + \sum_{1 \leqslant i < j \leqslant m} (\lfloor \log_2 d_{i,j} \rfloor + 1) + \bigl( (m-1) + (m-2) + \ldots + 2 \bigr) \; \leqslant \; \lceil \log_2 B \rceil + \frac{m(m-1)}{2} \max\limits_{1 \leqslant i < j \leqslant m} (\lceil \log_2 d_{i,j} \rceil) + \frac{m(m-1)}{2} + 1.</math>
 +
 
 +
Кодировать число B и верхнюю часть матрицы D надо в любом случае; двоичное кодирование неизбыточно; разделителей мы добавили лишь полиномиальное число (порядка <math>\frac{m^2}{2}</math>). Поэтому кодировка является неизбыточной.
 +
 
 +
Оценка <math>m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil</math> лучше предложенной, но вряд ли достижима.
 +
 
 +
 
 +
 
 +
== Задача 2 ==
 +
 
 +
 
 +
'''Условие.''' Дать алгоритм распознавания простоты числа и оценить его временную сложность.
 +
 
 +
 
 +
'''Решение.''' Будем считать, что исходное число N вводится в двоичном виде. Для того, чтобы проверить его на простоту, будем делить его поочерёдно на 2, 3, ..., N-1 и рассматривать остатки от делений. Если на очередном шаге остаток получился равным нулю, то процесс можно не продолжать — рассматриваемое число не являеся простым; если же мы произвели все деления и не получили ни одного нулевого остатка, то число является простым.
 +
 
 +
Таким образом, в худшем случае (когда рассматриваемое число — простое) получаем N-2 деления.
 +
 
 +
Деление будем производить «столбиком». Пусть мы делим некоторое число a на некоторое число b (с соответствующими битовыми длинами <math>m_a</math> и <math>m_b</math>). Тогда на каждое вычитание двоичных строк потребуется, грубо говоря, <math>2(m_b + 1)</math> битовых операций (непосредственно вычитания плюс проверки); всего же таких итераций будет не больше, чем <math>m_a - m_b + 1.</math>
 +
 
 +
Получаем, что <math>t(m_a, m_b) \leqslant 2(m_b + 1)(m_a - m_b + 1).</math>
 +
 
 +
: <math>2(m_b + 1)(m_a - m_b + 1) \leqslant 2(m+1)m = 2m^2 + 2m.</math>
 +
 
 +
Следовательно, деление «столбиком» имеет сложность <math>O(n^2)</math>.
 +
 
 +
Итого, сложность всего алгоритма равна <math>T(n) = (N - 2) \cdot O(n^2) = O(2^N) \cdot O(n^2) = O(n^2 \cdot 2^n).</math>
 +
 
 +
 
 +
 
 +
== Задача 3 ==
 +
 
 +
 
 +
'''Условие.''' Завершить доказательство утверждения 9 (§3 методички) для случая k = 1, 2.
 +
 
 +
 
 +
'''Решение.''' В том случае, когда дизъюнктивные функции, входящие в КНФ задачи о выполнимости, зависят от одной или двух переменных, их можно представить в виде конъюнкции дизъюнктивных функций трёх переменных следующим образом:
 +
 
 +
# При k = 1:
 +
: <math>y_1 = (y_1 \vee \bar{u}{}_1) \wedge (y_1 \vee u_1) = (y_1 \vee \bar{u}{}_1 \vee \bar{u}{}_2) \wedge (y_1 \vee \bar{u}{}_1 \vee u_2) \wedge (y_1 \vee u_1 \vee \bar{u}{}_2) \wedge (y_1 \vee u_1 \vee u_2).</math>
 +
 
 +
 
 +
# При k = 2:
 +
: <math>y_1 \vee y_2 = (y_1 \vee y_2 \vee \bar{u}) \wedge (y_1 \vee u_1 \vee u).</math>
 +
 
 +
При этом переменные <math>u</math> являются фиктивными, то есть такая замена является эквивалентной (в отличие от замены для случая k = 3). Таким образом, эти три преобразования позволяют полиномиально свести задачу ВЫП к задаче 3-ВЫП.
 +
 
 +
 
 +
 
 +
== Задача 4 ==
 +
 
 +
 
 +
'''Условие.''' Доказать, что задача ПЧ<math>\in co-\mathbb{NP}</math>.
 +
 
 +
 
 +
'''Решение.''' Согласно определению, задача ПЧ будет принадлежать классу <math>co-\mathbb{NP}</math>, если дополнительная к ней задача будет принадлежать классу <math>\mathbb{NP}.</math>
 +
 
 +
Дополнительной к задаче ПЧ является задача распознавания того, является ли число (назовём его N, с битовой длиной n) составным. Для проверки этого будем использовать детерминированные машины Тьюринга, которые «столбиком» делят N на числа, соответственно, от 2 до N-1 и находят остатки от этих делений. Если хотя бы одна из ДМТ выдаст нулевой остаток, вся НДМТ останавливается — число N является составным. Если же все остатки отличны от нуля, N — простое число.
 +
 
 +
Деление «столбиком» имеет сложность порядка <math>O(n^2)</math> (см. [[Методы оптимизации, задачи#Задача 2|Задачу 2]]); длина каждого из слов-подсказок не превышает n, поэтому время их прочтения не больше k*n, где k — некоторый коэффициент. Следовательно, временная сложность всей НДМТ, решающей задачу о том, является ли число составным, также полиномиальна. Таким образом, эта задача принадлежит классу <math>\mathbb{NP}</math>, а задача ПЧ принадлежит классу <math>co-\mathbb{NP}.</math>
 +
 
 +
 
 +
 
 +
== Задача 5 ==
 +
 
 +
 
 +
'''Условие.''' Свести задачу ЛП с ограничениями в канонической форме к основной задаче ЛП.
 +
 
 +
 
 +
'''Решение.''' Другими словами, необходимо задачу <math>\max\limits_{\tilde{A} x = \tilde{b}, \; x \in \mathbb{R}^n, \ x \geqslant \bar{0}} \langle c,x \rangle</math> свести к задаче <math>\max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle.</math>
 +
 
 +
Применим к ограничениям в канонической форме равносильные преобразования:
 +
 
 +
: <math>\tilde{A} x = \tilde{b} \Leftrightarrow \begin{cases} \tilde{A} x \geqslant \tilde{b} \\ \tilde{A} x \leqslant \tilde{b} \end{cases} \Leftrightarrow \begin{cases} - \tilde{A} x \leqslant - \tilde{b} \\ \tilde{A} x \leqslant \tilde{b} \end{cases} \Leftrightarrow \begin{pmatrix} - \tilde{A} \\ \tilde{A} \end{pmatrix} x \leqslant \begin{pmatrix} - \tilde{b} \\ \tilde{b} \end{pmatrix}.</math>
 +
 
 +
Учитывая равносильность условий <math>x \geqslant \bar{0}</math> и <math>- x \leqslant \bar{0}</math>, получаем:
 +
 
 +
: <math>\begin{pmatrix} - \tilde{A} \\ \tilde{A} \\ - E \end{pmatrix} x \leqslant \begin{pmatrix} - \tilde{b} \\ \tilde{b} \\ \bar{0} \end{pmatrix}.</math>
 +
 
 +
Получаем, что <math>\max\limits_{\tilde{A} x = \tilde{b}, \; x \in \mathbb{R}^n, \ x \geqslant \bar{0}} \langle c,x \rangle \; = \;\max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle</math>, где <math>A = \begin{pmatrix} - \tilde{A} \\ \tilde{A} \\ - E \end{pmatrix}, \; b = \begin{pmatrix} - \tilde{b} \\ \tilde{b} \\ \bar{0} \end{pmatrix},</math> то есть мы свели задачу ЛП с ограничениями в канонической форме к основной задаче ЛП.
{{Курс Методы оптимизации}}
{{Курс Методы оптимизации}}

Версия 21:53, 7 июня 2009

Содержание

Задача 1

Условие. Предложить неизбыточную кодировку задачи коммивояжёра. Дать оценку длины входа и сравнить её с m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil.


Решение. Пусть m — число городов, B — максимальная длина маршрута, D = {di,j} — матрица расстояний между городами. Будем кодировать m, B и di,j в двоичном виде. Кроме того, включим в алфавит символ-разделитель #. Таким образом, кодировка будет состоять из двоичных записей чисел m, B и элементов di,j, между которыми находятся разделители #. При этом можно включать в кодировку не все элементы di,j, а только те, которые лежат выше главной диагонали матрицы D (поскольку в силу равенств di,j = dj,i и di,i = 0 матрица D симметрична и имеет нулевую главную диагональ). Кроме того, можно не кодировать и число m, поскольку оно однозначно определяется по числу разделителей между элементами матрицы.

Для того чтобы осуществить двоичное кодирование некоторого числа N, необходимо \lfloor \log_2 N \rfloor + 1 символов. Таким образом, длина входа задачи коммивояжёра будет равна

(\lfloor \log_2 B \rfloor + 1) + 1 + \sum_{1 \leqslant i < j \leqslant m} (\lfloor \log_2 d_{i,j} \rfloor + 1) + \bigl( (m-1) + (m-2) + \ldots + 2 \bigr) \; \leqslant \; \lceil \log_2 B \rceil + \frac{m(m-1)}{2} \max\limits_{1 \leqslant i < j \leqslant m} (\lceil \log_2 d_{i,j} \rceil) + \frac{m(m-1)}{2} + 1.

Кодировать число B и верхнюю часть матрицы D надо в любом случае; двоичное кодирование неизбыточно; разделителей мы добавили лишь полиномиальное число (порядка \frac{m^2}{2}). Поэтому кодировка является неизбыточной.

Оценка m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil лучше предложенной, но вряд ли достижима.


Задача 2

Условие. Дать алгоритм распознавания простоты числа и оценить его временную сложность.


Решение. Будем считать, что исходное число N вводится в двоичном виде. Для того, чтобы проверить его на простоту, будем делить его поочерёдно на 2, 3, ..., N-1 и рассматривать остатки от делений. Если на очередном шаге остаток получился равным нулю, то процесс можно не продолжать — рассматриваемое число не являеся простым; если же мы произвели все деления и не получили ни одного нулевого остатка, то число является простым.

Таким образом, в худшем случае (когда рассматриваемое число — простое) получаем N-2 деления.

Деление будем производить «столбиком». Пусть мы делим некоторое число a на некоторое число b (с соответствующими битовыми длинами ma и mb). Тогда на каждое вычитание двоичных строк потребуется, грубо говоря, 2(mb + 1) битовых операций (непосредственно вычитания плюс проверки); всего же таких итераций будет не больше, чем ma − mb + 1.

Получаем, что t(m_a, m_b) \leqslant 2(m_b + 1)(m_a - m_b + 1).

2(m_b + 1)(m_a - m_b + 1) \leqslant 2(m+1)m = 2m^2 + 2m.

Следовательно, деление «столбиком» имеет сложность O(n2).

Итого, сложность всего алгоритма равна T(n) = (N - 2) \cdot O(n^2) = O(2^N) \cdot O(n^2) = O(n^2 \cdot 2^n).


Задача 3

Условие. Завершить доказательство утверждения 9 (§3 методички) для случая k = 1, 2.


Решение. В том случае, когда дизъюнктивные функции, входящие в КНФ задачи о выполнимости, зависят от одной или двух переменных, их можно представить в виде конъюнкции дизъюнктивных функций трёх переменных следующим образом:

  1. При k = 1:
y_1 = (y_1 \vee \bar{u}{}_1) \wedge (y_1 \vee u_1) = (y_1 \vee \bar{u}{}_1 \vee \bar{u}{}_2) \wedge (y_1 \vee \bar{u}{}_1 \vee u_2) \wedge (y_1 \vee u_1 \vee \bar{u}{}_2) \wedge (y_1 \vee u_1 \vee u_2).


  1. При k = 2:
y_1 \vee y_2 = (y_1 \vee y_2 \vee \bar{u}) \wedge (y_1 \vee u_1 \vee u).

При этом переменные u являются фиктивными, то есть такая замена является эквивалентной (в отличие от замены для случая k = 3). Таким образом, эти три преобразования позволяют полиномиально свести задачу ВЫП к задаче 3-ВЫП.


Задача 4

Условие. Доказать, что задача ПЧ\in co-\mathbb{NP}.


Решение. Согласно определению, задача ПЧ будет принадлежать классу co-\mathbb{NP}, если дополнительная к ней задача будет принадлежать классу \mathbb{NP}.

Дополнительной к задаче ПЧ является задача распознавания того, является ли число (назовём его N, с битовой длиной n) составным. Для проверки этого будем использовать детерминированные машины Тьюринга, которые «столбиком» делят N на числа, соответственно, от 2 до N-1 и находят остатки от этих делений. Если хотя бы одна из ДМТ выдаст нулевой остаток, вся НДМТ останавливается — число N является составным. Если же все остатки отличны от нуля, N — простое число.

Деление «столбиком» имеет сложность порядка O(n2) (см. Задачу 2); длина каждого из слов-подсказок не превышает n, поэтому время их прочтения не больше k*n, где k — некоторый коэффициент. Следовательно, временная сложность всей НДМТ, решающей задачу о том, является ли число составным, также полиномиальна. Таким образом, эта задача принадлежит классу \mathbb{NP}, а задача ПЧ принадлежит классу co-\mathbb{NP}.


Задача 5

Условие. Свести задачу ЛП с ограничениями в канонической форме к основной задаче ЛП.


Решение. Другими словами, необходимо задачу \max\limits_{\tilde{A} x = \tilde{b}, \; x \in \mathbb{R}^n, \ x \geqslant \bar{0}} \langle c,x \rangle свести к задаче \max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle.

Применим к ограничениям в канонической форме равносильные преобразования:

\tilde{A} x = \tilde{b} \Leftrightarrow \begin{cases} \tilde{A} x \geqslant \tilde{b} \\ \tilde{A} x \leqslant \tilde{b} \end{cases} \Leftrightarrow \begin{cases} - \tilde{A} x \leqslant - \tilde{b} \\ \tilde{A} x \leqslant \tilde{b} \end{cases} \Leftrightarrow \begin{pmatrix} - \tilde{A} \\ \tilde{A} \end{pmatrix} x \leqslant \begin{pmatrix} - \tilde{b} \\ \tilde{b} \end{pmatrix}.

Учитывая равносильность условий x \geqslant \bar{0} и - x \leqslant \bar{0}, получаем:

\begin{pmatrix} - \tilde{A} \\ \tilde{A} \\ - E \end{pmatrix} x \leqslant \begin{pmatrix} - \tilde{b} \\ \tilde{b} \\ \bar{0} \end{pmatrix}.

Получаем, что \max\limits_{\tilde{A} x = \tilde{b}, \; x \in \mathbb{R}^n, \ x \geqslant \bar{0}} \langle c,x \rangle \; = \;\max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle, где A = \begin{pmatrix} - \tilde{A} \\ \tilde{A} \\ - E \end{pmatrix}, \; b = \begin{pmatrix} - \tilde{b} \\ \tilde{b} \\ \bar{0} \end{pmatrix}, то есть мы свели задачу ЛП с ограничениями в канонической форме к основной задаче ЛП.


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

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

Календарь

пт пт пт пт пт
Февраль
   08 15 22 29
Март
06 13 20 27
Апрель
04 11 18 25
Май
02   16 23

Материалы
Упражнения || Задачи | Определения | Утверждения | Теоремы || Теормин | Обозначения

Получено с http://esyr.name/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8
Личные инструменты
Разделы