Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Колмогоровский семинар по сложности вычислений и сложности определений
21 мая 2012 г. 13:00–14:30, г. Москва, Главное здание МГУ, ауд. 16-04
 


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

Головнев Александр

Количество просмотров:
Эта страница:227

Аннотация: Для частных случаев задачи о коммивояжёре известны полиномиальные приближённые алгоритмы. В предположении $P!=NP$ для общей задачи о коммивояжёре такие алгоритмы не существуют. При необходимости решить задачу с некоторой константной точностью, то мы вынуждены использовать точные алгоритмы. Задача о коммивояжёре может быть решена точно за время $2^n$ с использованием экспоненциальной памяти или за время $4^n$ с полиномиальной памятью. Открытым вопросом является существование алгоритма с временем работы $2^n$ и лишь полиномиальной памятью. В докладе мы разберём частичный ответ на этот вопрос: за $2^n$ шагов с использованием лишь полиномиальной памяти может быть найдено любое константное приближение задачи о коммивояжёре. Также мы поговорим о точных и приближённых алгоритмах решения задачи о кратчайшей надстроке.
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024