Примеры решений задачи коммивояжера
На этой странице вы найдете готовые примеры решенных задач коммивояжера - одной из самых известных задач комбинаторной оптимизации. Эта задача состоит в поиске наилучшего (выгодного, дешевого, краткого и т.п.) маршрута, проходящего через всех указанные города хотя бы по одному разу (чаще всего - с точностью по одному разу) с возвращением в начальный город.
Данная задача относится к классу NP-трудных задач и решение переборными методами (вычисление длин всех возможных маршрутов и их сравнение) практически невозможно (для $n$ городов существует $(n-1)!/2$ маршрутов). Например, если взять 10 городов - найдем 181440 путей, а для 20 - уже $6,1\cdot 10^{16}$.
На практике чаще всего изучают метод ветвей и границ (и его модификации, в том числе алгоритм Литтла), который позволяет на каждом шаге отбрасывать целую группу неоптимальных маршрутов.
Ниже вы найдете несколько решенных данным методом примеров (оформленные разным способом, выбирайте тот, что близок к вашему пособию/методичке/лекциям), а также пример расчетов на поиск оптимального маршрута в MS Excel.
Заказать решение
Если вам нужна помощь с решением оптимизационных задач дискретной математики (задача коммивояжера, задача о ранце, задача раскроя или выбора пути), обращайтесь в МатБюро. Стоимость от 200 рублей, оформление производится в Word, срок от 2 дней.
Задачи коммивояжера с решением
Задача 1. Решите методом ветвей и границ следующую задачу коммивояжера
Задача 2. Решите методом ветвей и границ задачу коммивояжера
Задача 3.Решить задачу коммивояжёра по алгоритму Литтла:
Задача 4. Для задачи коммивояжера задана матрица расстояний между городами. Вычислить длину маршрута (4,3,2,1,4)
Задача 5. Решить задачу коммивояжера в Excel:
Как найти решение задачи коммивояжера онлайн?
Если вам нужно быстро и бесплатно решить задачу коммивояжера, рекомендую следующие сайты-сервисы (скорее всего, полученное в онлайн-калькуляторе решение потребуется дополнить/переоформить перед сдачей):
- Решение задачи коммивояжера онлайн: метод ветвей и границ. Красочные таблицы и пояснения присутствуют.
- Решение задачи методом Литтла. Возможно вывести полный ход решения.
- Онлайн-калькуляторы: метод ветвей и границ и венгерский метод. Выкладки достаточно подробные
