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

Для подведения итогов в изучении методов решения ЗК протестируем наиболее оптимальные алгоритмы на компьютере по следующим показателям: количество городов, время обработки, вероятность неправильного ответа. Данные занесём в таблицу.

*- ЗК с таким количеством городов методом лексического перебора современный компьютер не смог бы решить даже за всё время существования Вселенной.

Как видим по результатам этой таблицы, алгоритм лексического перебора можно применять лишь в случае с количеством городов 5...12. Метод ветвей и границ можно применять всегда.

Глава 2. Практическая реализация задачи коммивояжёра

Решить задачу коммивояжёра, то есть построить оптимальный кольцевой маршрут для орграфа (рис.) с вершинами . Стоимость единицы пути равна 10. Пропускные способности дуг (расстояния между населёнными пунктами) указаны в таблице:

Решение задачи коммивояжёра методом ветвей и границ

d(x) - минимальная стоимость тура

Стоимость маршрута, не содержащего путь {2,3} будет не менее 63.

табл. 2.1.7
-
	-	0		0
	0	-	0
		-	-
		0		-

Стоимость маршрута содержащего путь {2,3} будет не менее 58. Для дальнейшего решения выбираем путь содержащий граф с вершинами {2,3}.

Стоимость маршрута, не содержащего путь {4,2} будет не менее 62.Стоимость маршрута содержащего путь {4,2} будет не менее 63. Для дальнейшего решения выбираем путь не содержащий граф с вершинами {4,2}.

Поучаем путь {2,3}{3,4}{4,1}{1,5}{5,2}стоимость которого равна (10+20+14+10+8)*10=620.

Решение задачи с помощью программы «Нахождение оптимального маршрута»