next up previous
Next: Элементы теории Up: TSP Previous: TSP

Введение

TSP (Traveling Salesman Problem) - ЗК (Задача Коммивояжёра) - одна из задач линейного программирования, принадлежащая к числу $ \mathbf{NP}$-полных задач. Постановка задачи такова: имеется связный граф, ориентированный или неориентированный, из $ \mathbf n$ вершин, соединённых рёбрами. Каждое из рёбер имеет числовую стоимость. Требуется построить маршрут (замкнутый обход), проходящий через каждую вершину графа строго по одному разу так, чтобы минимизировать общую суммарную стоимость маршрута. Предполагается, что хотя бы один замкнутый обход существует.



Бродников А.П. 2006-11-05
Используются технологии uCoz