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

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

Версия от 08:45, 8 июня 2009; 194.88.210.254 (Обсуждение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Задача 1
2 Задача 2
3 Задача 3
4 Задача 4
5 Задача 5

Задача 1

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

Решение. Пусть m — число городов, B — максимальная длина маршрута, $D = {d i, j}$ — матрица расстояний между городами. Будем кодировать m, B и $d i, j$ в двоичном виде. Кроме того, включим в алфавит символ-разделитель #. Таким образом, кодировка будет состоять из двоичных записей чисел m, B и элементов $d i, j$ , между которыми находятся разделители #. При этом можно включать в кодировку не все элементы $d i, j$ , а только те, которые лежат выше главной диагонали матрицы D (поскольку в силу равенств $d i, j = d j, i$ и $d i, 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 (с соответствующими битовыми длинами $m a$ и $m b$ ). Тогда на каждое вычитание двоичных строк потребуется, грубо говоря, $2(m b + 1)$ битовых операций (непосредственно вычитания плюс проверки); всего же таких итераций будет не больше, чем $m a - m b + 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 (n 2)$ .

Итого, сложность всего алгоритма равна $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.

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

При 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).$

При 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 (n 2)$ (см. Задачу 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},$ то есть мы свели задачу ЛП с ограничениями в канонической форме к основной задаче ЛП.