Примеры решений задачи коммивояжера

На этой странице вы найдете готовые примеры решенных задач коммивояжера - одной из самых известных задач комбинаторной оптимизации. Эта задача состоит в поиске наилучшего (выгодного, дешевого, краткого и т.п.) маршрута, проходящего через всех указанные города хотя бы по одному разу (чаще всего - с точностью по одному разу) с возвращением в начальный город.

Данная задача относится к классу 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:

Решение

Как найти решение задачи коммивояжера онлайн?

Если вам нужно быстро и бесплатно решить задачу коммивояжера, рекомендую следующие сайты-сервисы (скорее всего, полученное в онлайн-калькуляторе решение потребуется дополнить/переоформить перед сдачей):