Теоретическая информатика в Академическом Университете

Я хочу описать историю одного заносчивого и самовлюбленного студента Академического Университета, коим я, конечно, не являюсь, но хорошо представляю его мысли и переживания. Будем называть этого студента, например, Шурик. На момент поступления Шурика в Академический Университет (АУ), согласно его программистскому резюме, он уже был экспертом в области алгоритмов. Он мастерски владел алгоритмом поиска в глубину, знал несколько методов сортировки массивов, и имел представление о двоичном поиске. Естественно, курс алгоритмов его не интересовал совершенно, да и вообще, мало чему можно научить программиста с пятилетним опытом. Программа теоретической информатики АУ его заинтересовала тем, что в темах по известным ему предметам было слишком много неизвестных ему слов. Но это же Питер, там они и бордюр то странным словом называют, вероятно, и для поиска в глубину красивых слов понавыдумывали. Он тщательно изучил слайды и видеозаписи курсов. Оказалось, что существует какая-то там информатика, которой Шурик не владеет в совершенстве. Шурик собрал книги, носки и пять лет опыта, и отправился в Питер на собеседование. Там он встретили людей, которые могут научить чему-то даже программиста с таким опытом. Это все рушило Шурикову картину мира, в которой знание информатики измерялось количеством написанных классов на C#.
Во время учëбы в магистратуре Шурик занимался исследованиями в области схемной сложности и области экспоненциальных алгоритмов. Это действительно очень интересно и, что не менее важно, полезно для поступления в аспирантуру.
На данный момент Шурик является счастливым аспирантом New York University, использует слово «поребрик», и с глубокой благодарностью вспоминает Академический Университет. А кафедра теоретической информатики АУ и сейчас ведëт набор новых магистрантов.
Сейчас я передаю слово Шурику, который и расскажет об одном своëм исследовании.

Алгоритмы для NP-трудных задач

NP-трудные задачи — это задачи, часто встречающиеся на практике, для которых неизвестны эффективные алгоритмы решения. Исследование таких задач представляет большой интерес, т.к. существование эффективного алгоритма для любой из таких задач влечет существование эффективных алгоритмов для всех NP-трудных задач. И, наоборот, если мы сможем доказать, что хотя бы для одной из таких задач не существует эффективного алгоритма, то это будет означать, что таких алгоритмов не существует и для остальных задач. В магистратуре АУ мы исследовали точные и приближенные алгоритмы решения некоторых NP-трудных задач. Например, нам удалось получить новые алгоритмы решения задачи о максимальной выполнимости, задачи о коммивояжëре, и задачи о кратчайшей общей надстроке. Далее я хочу описать один из этих алгоритмов, а именно алгоритм приближëнного решения задачи о коммивояжëре.

NP-трудная задача оптимизации — это NP-трудная задача, в которой среди всех возможных решений нужно выбрать оптимальное в каком-то смысле решение. Например, найти кратчайший цикл, проходящий через каждую вершину заданного взвешенного графа ровно один раз. Возможно, существует множество способов обойти граф, проходя по каждой вершине ровно один раз, но нас интересуют только те обходы, которые минимальны по весу. Эта задача называется задачей коммивояжëра. Время работы лучших известных алгоритмов для этой задачи в худшем случае примерно равно $2^n$ . Мы занимались ускорением алгоритмов для задач такого рода. Например, алгоритм, который работает за время $1.45^n$ , позволит решать задачу для больших значений n. Интересно заметить, что покупка компьютера, работающего в 1000 раз быстрее, не даст такого ускорения, как новый алгоритм с меньшей экспонентой во времени выполнения. Существование полиномиального алгоритма для этой задачи повлечет равенство классов P и NP, а доказательство отсутствия такого алгоритма будет означать, что эти классы не равны.

Задача коммивояжëра

Гамильтонов цикл графа — это цикл, проходящий по каждой вершине графа ровно один раз. Задача коммивояжёра (ЗК) заключается в поиске гамильтонова цикла минимального веса в заданном взвешенном графе. Обозначим через n количество вершин исходного графа, а через M — максимальный вес ребра. $O^*(\cdot)$ скрывает полиномиальные множители от длины входа, т.е. $poly(n\cdot\log{M})$ . Существует множество методов решения задачи о коммивояжëре на практике, но в этой статье мы будем говорить только о теоретических алгоритмах с доказуемыми оценками на время работы в худшем случае.

Точные алгоритмы решения задачи о коммивояжëре

В 1962 году был разработан алгоритм динамического программирования, решающий ЗК за время $2^n$ , но при этом используя экспоненциальную $(2^n)$ )память. Лучший известный алгоритм, использующий лишь полиномиальную память, имеет время работы $4^n\cdot n^{O(\log{n})}$ . Также известны промежуточные результаты, например, для любого $\sqrt{2}<S<2$ , существует алгоритм решения задачи со временем работы $T^n$ , использующий память $S^n$ , где $T<\frac{4}{S}$ . Известны алгоритмы, решающие задачу за время $2^n\cdot M$ , используя память $O^*(M)$ . Для неориентированного случая ЗК существует Монте-Карло алгоритм со временем работы $1.657^n\cdot M$ и экспоненциально маленькой вероятностью ошибки. Уже более пятидесяти лет открытыми являются следующие вопросы:

Существование алгоритма для ЗК со временем работы $O^*(2^n)=2^n\cdot poly(n\cdot\log{M})$ и полиномиальной памятью.
Существование алгоритма для ЗК со временем работы $O^*(1.99^n\cdot M)$ для общего (ориентированного) случая задачи о коммивояжëре.

Приближëнные алгоритмы решения задачи коммивояжëра

Известно, что в предположении $P\neq NP$ , общая ЗК не может быть приближена с любым полиномиально вычислимым фактором. То есть, в этом предположении, нельзя найти не только 10-приближение оптимального решения, но и даже n!-приближение. Частный случай, в котором веса рëбер графа удовлетворяют неравенству треугольника, называется метрической задачей коммивояжëра. Для неориентированной метрической задачи известно 1.5-приближение. Ещë для этого частного случая известно, что в предположении $P\neq NP$ , нельзя найти полиномиальный алгоритм с приближением лучше $\frac{117}{116}$ (в ориентированном случае — $\frac{220}{219}$ ). Для ориентированной метрической версии задачи фактор приближения был недавно улучшен до $O(\frac{\log{n}}{\log{\log{n}}})$ .

Приближение за экспоненциальное время

Мы предлагаем алгоритм, который для любого фиксированного $\epsilon$ использует $O^*(2^n)$ шагов и полиномиальную память для вычисления $(1+\epsilon)$ -приближения ориентированной метрической задачи коммивояжёра. Как было указано выше, лучшее известное полиномиальное приближение даже для неориентированной метрической версии ЗК — 1.5 (для ориентированной — $O(\frac{\log{n}}{\log{\log{n}}})$ ).
Если $P\neq NP$ , то за полиномиальное время не может быть найдено $\frac{117}{116}$ -приближение неориентированной метрической ЗК.
Если нам необходимо, например, $\frac{1001}{1000}$ -приближение, то мы должны использовать точные алгоритмы, которые требуют либо экспоненциальную память, либо время $4^n\cdot n^{O(\log{n})}$ . Экспоненциальные алгоритмы редко используются на практике, но в любом случае, мы способны их запустить и ждать ответа. Однако, если алгоритм использует экспоненциальную память, то мы не имеем возможности даже запустить алгоритм на входах разумного размера.
Предложенный алгоритм может найти $\frac{1001}{1000}$ -приближение общей ЗК за время $O^*(2^n)$ , используя лишь полиномиальную память.

Разработанный алгоритм использует идею, предложенную для построения полностью полиномиальной приближённой схемы для задачи о рюкзаке в работе Ibarra, Kim. Авторы используют псевдополиномиальный алгоритм для задачи о рюкзаке, работающий за время $O(nW)$ , где n — количество предметов, а W — вместимость рюкзака.
Полностью полиномиальная схема приближения задачи о рюкзаке сначала делит веса всех предметов на $\alpha(\epsilon,n,W)$ , затем вызывает псевдополиномиальный алгоритм. Полученный ответ может не оказаться оптимальным, т.к. некоторые веса не просто поделены на $\alpha$ , но и округлены. Однако простой анализ показывает, что округление не сильно сказывается на результате.

Мы используем похожую идею. Через OPT обозначим оптимальное рещение ЗК. Для того, чтобы получить полиномиальный по памяти приближённый алгоритм, мы сначала разделим веса всех рёбер на достаточно большое число $\alpha$ , затем запустим точный алгоритм, основанный на формуле включений-исключений. Время работы полученного алгоритма будет равно $2^n\cdot OPT /\alpha$ и длина полученного цикла будет не больше $OPT+\alpha n$ . Теперь мы хотим выбрать $\alpha$ так, что $\alpha\ge\frac{OPT}{\textrm{poly(n)}}$ и $\alpha\le\frac{\epsilon OPT}{n}$ . Метрическая версия ЗК может быть приближена за полиномиальное время, то есть, мы можем найти $\beta$ , что $OPT\le\beta\le OPT \cdot\log n$ и взять $\alpha=\frac{\beta\cdot\epsilon}{n\log n}$ . Тогда полученный алгоритм будет иметь время работы $O^*(2^n\epsilon^{-1})$ и использовать память $O^*(\epsilon^{-1})$ . Нам также удалось обобщить этот результат для случая общей (неметрической ориентированной) задачи коммивояжëра.