Студенты 2 курса специальности Информационные системы и технологии, Факультета Информатики и прикладной математики, 26 ноября 2017 г. коллективно посетили открытую лекцию на тему «Алгоритмы для задачи коммивояжёра» в ПОМИ РАН, организатором мероприятия выступил старший преподаватель кафедры информатики А. К. Сотавов. Лектор: Александр Куликов, старший научный сотрудник ПОМИ РАН.
В рамках лекции студенты смогли познакомится с множеством разных алгоритмов для классической задачи комбинаторной оптимизации — задачи коммивояжёра. Это задача с бесчисленным количеством практических приложений (доставка, проектирование микросхем, планирование), для которой до сих пор не построено алгоритмов, гарантированно находящих оптимальное решение за разумное время. Рассмотрели для данной задачи точные алгоритмы, приближённые алгоритмы, эвристические алгоритмы. Узнали, как классические алгоритмы (например, 1.5-приближение для задачи коммивояжёра в метрическом пространстве), так и совсем недавние (например, точный алгоритм со временем работы 1.7^n).
 |
 |
 |
 |
 |
