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

в 10:15, , рубрики: академический университет, Алгоритмы, задача коммивояжëра, Учебный процесс в IT, метки: ,

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

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

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

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

Гамильтонов цикл графа — это цикл, проходящий по каждой вершине графа ровно один раз. Задача коммивояжёра (ЗК) заключается в поиске гамильтонова цикла минимального веса в заданном взвешенном графе. Обозначим через n количество вершин исходного графа, а через M — максимальный вес ребра. Теоретическая информатика в Академическом Университете скрывает полиномиальные множители от длины входа, т.е. Теоретическая информатика в Академическом Университете. Существует множество методов решения задачи о коммивояжëре на практике, но в этой статье мы будем говорить только о теоретических алгоритмах с доказуемыми оценками на время работы в худшем случае.
image

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

В 1962 году был разработан алгоритм динамического программирования, решающий ЗК за время Теоретическая информатика в Академическом Университете, но при этом используя экспоненциальную Теоретическая информатика в Академическом Университете)память. Лучший известный алгоритм, использующий лишь полиномиальную память, имеет время работы Теоретическая информатика в Академическом Университете. Также известны промежуточные результаты, например, для любого Теоретическая информатика в Академическом Университете, существует алгоритм решения задачи со временем работы Теоретическая информатика в Академическом Университете, использующий память Теоретическая информатика в Академическом Университете, где Теоретическая информатика в Академическом Университете. Известны алгоритмы, решающие задачу за время Теоретическая информатика в Академическом Университете, используя память Теоретическая информатика в Академическом Университете. Для неориентированного случая ЗК существует Монте-Карло алгоритм со временем работы Теоретическая информатика в Академическом Университете и экспоненциально маленькой вероятностью ошибки. Уже более пятидесяти лет открытыми являются следующие вопросы:

  1. Существование алгоритма для ЗК со временем работы Теоретическая информатика в Академическом Университете и полиномиальной памятью.
  2. Существование алгоритма для ЗК со временем работы Теоретическая информатика в Академическом Университете для общего (ориентированного) случая задачи о коммивояжëре.

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

Известно, что в предположении Теоретическая информатика в Академическом Университете, общая ЗК не может быть приближена с любым полиномиально вычислимым фактором. То есть, в этом предположении, нельзя найти не только 10-приближение оптимального решения, но и даже n!-приближение. Частный случай, в котором веса рëбер графа удовлетворяют неравенству треугольника, называется метрической задачей коммивояжëра. Для неориентированной метрической задачи известно 1.5-приближение. Ещë для этого частного случая известно, что в предположении Теоретическая информатика в Академическом Университете, нельзя найти полиномиальный алгоритм с приближением лучше Теоретическая информатика в Академическом Университете (в ориентированном случае — Теоретическая информатика в Академическом Университете). Для ориентированной метрической версии задачи фактор приближения был недавно улучшен до Теоретическая информатика в Академическом Университете.

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

Мы предлагаем алгоритм, который для любого фиксированного Теоретическая информатика в Академическом Университете использует Теоретическая информатика в Академическом Университете шагов и полиномиальную память для вычисления Теоретическая информатика в Академическом Университете-приближения ориентированной метрической задачи коммивояжёра. Как было указано выше, лучшее известное полиномиальное приближение даже для неориентированной метрической версии ЗК — 1.5 (для ориентированной — Теоретическая информатика в Академическом Университете).
Если Теоретическая информатика в Академическом Университете, то за полиномиальное время не может быть найдено Теоретическая информатика в Академическом Университете-приближение неориентированной метрической ЗК.
Если нам необходимо, например, Теоретическая информатика в Академическом Университете-приближение, то мы должны использовать точные алгоритмы, которые требуют либо экспоненциальную память, либо время Теоретическая информатика в Академическом Университете. Экспоненциальные алгоритмы редко используются на практике, но в любом случае, мы способны их запустить и ждать ответа. Однако, если алгоритм использует экспоненциальную память, то мы не имеем возможности даже запустить алгоритм на входах разумного размера.
Предложенный алгоритм может найти Теоретическая информатика в Академическом Университете-приближение общей ЗК за время Теоретическая информатика в Академическом Университете, используя лишь полиномиальную память.

Разработанный алгоритм использует идею, предложенную для построения полностью полиномиальной приближённой схемы для задачи о рюкзаке в работе Ibarra, Kim. Авторы используют псевдополиномиальный алгоритм для задачи о рюкзаке, работающий за время Теоретическая информатика в Академическом Университете, где n — количество предметов, а W — вместимость рюкзака.
Полностью полиномиальная схема приближения задачи о рюкзаке сначала делит веса всех предметов на Теоретическая информатика в Академическом Университете, затем вызывает псевдополиномиальный алгоритм. Полученный ответ может не оказаться оптимальным, т.к. некоторые веса не просто поделены на Теоретическая информатика в Академическом Университете, но и округлены. Однако простой анализ показывает, что округление не сильно сказывается на результате.

Мы используем похожую идею. Через OPT обозначим оптимальное рещение ЗК. Для того, чтобы получить полиномиальный по памяти приближённый алгоритм, мы сначала разделим веса всех рёбер на достаточно большое число Теоретическая информатика в Академическом Университете, затем запустим точный алгоритм, основанный на формуле включений-исключений. Время работы полученного алгоритма будет равно Теоретическая информатика в Академическом Университете и длина полученного цикла будет не больше Теоретическая информатика в Академическом Университете. Теперь мы хотим выбрать Теоретическая информатика в Академическом Университете так, что Теоретическая информатика в Академическом Университете и Теоретическая информатика в Академическом Университете. Метрическая версия ЗК может быть приближена за полиномиальное время, то есть, мы можем найти Теоретическая информатика в Академическом Университете, что Теоретическая информатика в Академическом Университете и взять Теоретическая информатика в Академическом Университете. Тогда полученный алгоритм будет иметь время работы Теоретическая информатика в Академическом Университете и использовать память Теоретическая информатика в Академическом Университете. Нам также удалось обобщить этот результат для случая общей (неметрической ориентированной) задачи коммивояжëра.

Автор: AlexGl

Источник

Поделиться

* - обязательные к заполнению поля