https://www.wikicshse.ru/index.php?action=history&feed=atom&title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_%28%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82%29 2026-06-06T17:07:38Z История изменений этой страницы в вики MediaWiki 1.45.3 https://www.wikicshse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=2229&oldid=prev 2015-10-20T07:42:15Z

<p>Migrated current public revision from wiki.cs.hse.ru</p> <p><b>Новая страница</b></p><div>{{Карточка_проекта<br /> |name=Задача коммивояжера <br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> |is_archived=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * Визуализация на python<br /> * Библиотека Lemon для алгоритмов на графах<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * 4: Алгоритм работает на графе до 20 вершин<br /> * 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * 8: Метод ветвей и границ с линейным программированием<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> <br /> +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не получается добиться точного решения?<br /> <br /> Приближённый путь:<br /> * 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * 6: 2-приближение с помощью эйлерова цикла<br /> * 8: 3/2-приближение с использованием поиска паросочетания<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> <br /> +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не удаётся получить лучшего решения, чем описанные?</div>

imported>Ira dolgaleva